Sequence Mixed Graphs

View/ Open
Issue date
2017Suggested citation
Dalfó, Cristina;
Fiol, Miguel Angel;
López Lorenzo, Ignacio;
.
(2017)
.
Sequence Mixed Graphs.
Discrete Applied Mathematics, 2017, num. 219, p. 110-116.
https://doi.org/10.1016/j.dam.2016.10.030.
Metadata
Show full item recordAbstract
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.
Is part of
Discrete Applied Mathematics, 2017, num. 219, p. 110-116European research projects
Collections
Related items
Showing items related by title, author, creator and subject.
-
An improved upper bound for the order of mixed graphs
Dalfó, Cristina; Fiol, Miguel Angel; López Lorenzo, Ignacio (Elsevier B.V., 2018)A mixed graph G can contain both (undirected) edges and arcs (directed edges). Here we derive an improved Moore-like bound for the maximum number of vertices of a mixed graph with diameter at least three. Moreover, a ... -
An improved Moore bound and some new optimal families of mixed Abelian Cayley graphs
Dalfó, Cristina; Fiol, Miguel Angel; López Lorenzo, Ignacio; Ryan, Joe (Elsevier, 2020)We consider the case in which mixed graphs (with both directed and undirected edges) are Cayley graphs of Abelian groups. In this case, some Moore bounds were derived for the maximum number of vertices that such graphs can ... -
On mixed almost Moore graphs of diameter two
López Lorenzo, Ignacio; Miret, Josep M. (Josep Maria) (Electronic Journal of Combinatorics, 2016-04-01)Mixed almost Moore graphs appear in the context of the Degree/Diameter problem as a class of extremal mixed graphs, in the sense that their order is one less than the Moore bound for mixed graphs. The problem of their ...