A revised Moore bound for mixed graphs
From MaRDI portal
Publication:284732
DOI10.1016/J.DISC.2016.03.005zbMATH Open1336.05038arXiv1508.02596OpenAlexW2343835481MaRDI QIDQ284732FDOQ284732
Authors: Dominique Buset, Mourad El Amiri, Grahame Erskine, Mirka Miller, Hebert Pérez-Rosés 
Publication date: 18 May 2016
Published in: Discrete Mathematics (Search for Journal in Brave)
Abstract: The degree-diameter problem seeks to find the maximum possible order of a graph with a given (maximum) degree and diameter. It is known that graphs attaining the maximum possible value (the Moore bound) are extremely rare, but much activity is focused on finding new examples of graphs or families of graph with orders approaching the bound as closely as possible. There has been recent interest in this problem as it applies to mixed graphs, in which we allow some of the edges to be undirected and some directed. A 2008 paper of Nguyen and Miller derived an upper bound on the possible number of vertices of such graphs. We show that for diameters larger than three, this bound can be reduced and we present a corrected Moore bound for mixed graphs, valid for all diameters and for all combinations of undirected and directed degrees.
Full work available at URL: https://arxiv.org/abs/1508.02596
Recommendations
Cites Work
Cited In (25)
- A variant of the McKay-Miller-Širáň construction for mixed graphs
- An Entropy-Based Proof for the Moore Bound for Irregular Graphs
- The degree/diameter problem for mixed abelian Cayley graphs
- Eulogy for Professor Mirka Miller (1949--2016)
- An improved upper bound for the order of mixed graphs
- On mixed almost Moore graphs of diameter two
- On large regular \(( 1 , 1 , k )\)-mixed graphs
- New Moore-like bounds and some optimal families of abelian Cayley mixed graphs
- A new general family of mixed graphs
- On mixed Moore graphs
- Non existence of some mixed Moore graphs of diameter 2 using SAT
- On mixed radial Moore graphs of diameter 3
- Almost Moore and the largest mixed graphs of diameters two and three
- Moore bound for mixed networks
- On new record graphs close to bipartite Moore graphs
- On networks with order close to the Moore bound
- The Moore bound for irregular graphs
- Construction of extremal mixed graphs of diameter two
- On total regularity of mixed graphs with order close to the Moore bound
- Sequence mixed graphs
- A Moore-like bound for mixed abelian Cayley graphs
- A construction of dense mixed graphs of diameter 2
- A family of mixed graphs with large order and diameter 2
- An improved Moore bound and some new optimal families of mixed abelian Cayley graphs
- Moore mixed graphs from Cayley graphs
This page was built for publication: A revised Moore bound for mixed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q284732)
