|
Title:
|
A variant of the McKay-Miller-Siran construction for Mixed Graphs
|
|
Author:
|
López Lorenzo, Ignacio; Pérez Rosés, Hebert; Pujolàs Boix, Jordi; Zdimalovà, Maria
|
|
Notes:
|
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 [5], 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. |
|
Subject(s):
|
-Network design
-Degree/Diameter Problem
-Mixed graphs
-Voltage assignment
-Disseny assistit per ordinador
-Computer-aided design |
|
Rights:
|
cc-by-nc-nd (c) Elsevier B.V., 2016
http://creativecommons.org/licenses/by-nc-nd/4.0/
|
|
Document type:
|
Article
acceptedVersion |
|
Published by:
|
Elsevier B.V.
|
|
Share:
|
|
