Sequence mixed graphs

A mixed graph can be seen as a type of digraph containing some edges (or two opposite arcs). Here we introduce the concept of sequence mixed graphs, which is a generalization of both sequence graphs and iterated line digraphs. These structures are proven to be useful in the problem of constructing d...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2017-03, Vol.219, p.110-116
Main Authors: Dalfó, C., Fiol, M.A., López, N.
Format: Article
Language:English
Subjects:
Algebra
Degree/diameter problem
Diameter
Grafs, Teoria de
Graph theory
Graphs
Line digraph
Matemàtiques i estadística
Mean distance
Mixed graph
Moore bound
Sequence graph
Studies
Àlgebra
Àlgebra lineal i multilineal
Àrees temàtiques de la UPC
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A mixed graph can be seen as a type of digraph containing some edges (or two opposite arcs). Here we introduce the concept of sequence mixed graphs, which is a generalization of both sequence graphs and iterated line digraphs. These structures are proven to be useful in the problem of constructing dense graphs or digraphs, and this is related to the degree/diameter problem. Thus, our generalized approach gives rise to graphs that have also good ratio order/diameter. Moreover, we propose a general method for obtaining a sequence mixed digraph by identifying some vertices of a certain iterated line digraph. As a consequence, some results about distance-related parameters (mainly, the diameter and the average distance) of sequence mixed graphs are presented.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2016.10.030