Loading...
Loading...

Go to the content (press return)

An improved upper bound for the order of mixed graphs

Author
Dalfo, C.; Fiol, M.; López, N.
Type of activity
Journal article
Journal
Discrete mathematics
Date of publication
2018-07
Volume
341
Number
10
First page
2872
Last page
2877
DOI
https://doi.org/10.1016/j.disc.2018.06.016 Open in new window
Repository
http://hdl.handle.net/2117/119636 Open in new window
https://arxiv.org/pdf/1610.00116.pdf Open in new window
URL
https://www.sciencedirect.com/science/article/pii/S0012365X18301870 Open in new window
Abstract
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 complete enumeration of all optimal (1, 1)-regular mixed graphs with diameter three is presented, so proving that, in general, the proposed bound cannot be improved.
Citation
Dalfo, C., Fiol, M., López, N. An improved upper bound for the order of mixed graphs. "Discrete mathematics", Juliol 2018, vol. 341, núm. 10, p. 2872-2877.
Keywords
Degree/diameter problem, Mixed graph, Moore bound, Network design
Group of research
COMBGRAPH - Combinatorics, Graph Theory and Applications

Participants

Attachments