A variant of the McKay-Miller-Siran construction for Mixed Graphs
MetadataShow full item record
The Degree/Diameter Problem is an extremal problem in graph theory with applications in network design. One of the main research areas in the Degree/Diameter Problem consists of finding large graphs whose order approach the theoretical upper bounds as much as possible. In the case of directed graphs
there exist some families that come close to the theoretical upper bound asymptotically. In the case of undirected graphs there also exist some good constructions for specific values of the parameters involved (degree and/or diameter). One such construction was given by McKay, Miller, and ˇSir´aˇn in , which produces large graphs of diameter 2 with the aid of the voltage assignment technique. Here we show how to re-engineer the McKay-Miller-ˇSir´aˇn construction in order to obtain large mixed graphs of diameter 2, i.e. graphs containing both directed arcs and undirected edges.
Is part ofElectronic Notes in Discrete Mathematics, 2016, vol. 54, p. 151-156
European research projects
Except where otherwise noted, this item's license is described as cc-by-nc-nd (c) Elsevier B.V., 2016
Showing items related by title, author, creator and subject.
López Lorenzo, Ignacio; Pérez Rosés, Hebert; Pujolàs Boix, Jordi (Elsevier, 2017-11-20)This paper investigates the upper bounds for the number of vertices in mixed abelian Cayley graphs with given degree and diameter. Additionally, in the case when the undirected degree is equal to one, we give a construction ...
López Lorenzo, Ignacio; Pérez Rosés, Hebert; Pujolàs Boix, Jordi (Elsevier B.V., 2016-09-26)We give an upper bound for the number of vertices in mixed abelian Cayley graphs with given degree and diameter.
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 ...