Paper Info
Title
A variant of the McKay-Miller-Širáň construction for mixed graphs.
Abstract
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 Širáň in [McKay, B., M. Miller and J. Širáň, A note on large graphs of diameter two and given maximum degree, J Comb Theo Ser B 74 (1998), 110-118], 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-Širáň construction in order to obtain large mixed graphs of diameter 2, i.e. graphs containing both directed arcs and undirected edges.
Year
DOI
Venue
2016
10.1016/j.endm.2016.09.027
Electronic Notes in Discrete Mathematics
Keywords
Field
DocType
Network design,Degree/Diameter Problem,mixed graphs,voltage assignment
Discrete mathematics,Odd graph,Indifference graph,Combinatorics,Chordal graph,Graph product,Pathwidth,Degree diameter problem,Mathematics,Metric dimension,Maximal independent set
Journal
Volume
ISSN
Citations 
54
1571-0653
0
PageRank 
References 
Authors
0.34
3
4
Name
Order
Citations
PageRank
Nacho López1439.42
Hebert Pérez-rosés25311.04
Jordi Pujolàs3245.98
Mária Zdímalová410.70