Sequence Mixed Graphs

Dalfó, Cristina; Fiol, Miguel Angel; López Lorenzo, Ignacio

doi:https://doi.org/10.1016/j.dam.2016.10.030

View/Open

025343.pdf (365.2Kb)

Issue date

2017

Author

Dalfó, Cristina

Fiol, Miguel Angel

López Lorenzo, Ignacio

Suggested 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.

Abstract

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.

URI

http://hdl.handle.net/10459.1/59089

DOI

https://doi.org/10.1016/j.dam.2016.10.030

Is part of

Discrete Applied Mathematics, 2017, num. 219, p. 110-116

Collections

Except where otherwise noted, this item's license is described as cc-by-nc-nd (c) Elsevier, 2017