Back to Search
Start Over
A variant of the McKay-Miller-Siran construction for Mixed Graphs
- Source :
- Repositorio Abierto de la UdL, Universitad de Lleida, Recercat. Dipósit de la Recerca de Catalunya, instname
- Publication Year :
- 2016
- Publisher :
- Elsevier B.V., 2016.
-
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 Siraň in [McKay, B., M. Miller and J. Siraň, 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-Siraň construction in order to obtain large mixed graphs of diameter 2, i.e. graphs containing both directed arcs and undirected edges.
- Subjects :
- Computer-aided design
0102 computer and information sciences
02 engineering and technology
Voltage assignment
01 natural sciences
Combinatorics
Indifference graph
Pathwidth
Chordal graph
Disseny assistit per ordinador
0202 electrical engineering, electronic engineering, information engineering
Discrete Mathematics and Combinatorics
Network design
Mathematics
Discrete mathematics
Applied Mathematics
020206 networking & telecommunications
Degree diameter problem
Degree/Diameter Problem
Metric dimension
010201 computation theory & mathematics
Odd graph
Maximal independent set
Mixed graphs
Graph product
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- Repositorio Abierto de la UdL, Universitad de Lleida, Recercat. Dipósit de la Recerca de Catalunya, instname
- Accession number :
- edsair.doi.dedup.....20e72335c94a1dbf117ee87721a9a32a