On total regularity of mixed graphs with order close to the Moore bound

DOI10.1007/S00373-019-02114-2MaRDI QIDQ2287724zbMATH OpenOpenAlexFDO

Authors James Tuite, Grahame Erskine

Publication date 21 January 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1811.00650

zbMATH Keywords

mixed graphsdegree-diameter problemexcesstotal regularityalmost Moore graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)

Abstract: The undirected degree/diameter and degree/girth problems and their directed analogues have been studied for many decades in the search for efficient network topologies. Recently such questions have received much attention in the setting of mixed graphs, i.e. networks that admit both undirected emph{edges} and directed emph{arcs}. The degree/diameter problem for mixed graphs asks for the largest possible order of a network with diameter $k$, maximum undirected degree $leqr$ and maximum directed out-degree $leqz$. It is also of interest to find smallest possible $k$-geodetic mixed graphs with minimum undirected degree $geqr$ and minimum directed out-degree $geqz$. A simple counting argument reveals the existence of a natural bound, the emph{Moore bound}, on the order of such graphs; a graph that meets this limit is a emph{mixed Moore graph}. Mixed Moore graphs can exist only for $k=2$ and even in this case it is known that they are extremely rare. It is therefore of interest to search for graphs with order one away from the Moore bound. Such graphs must be out-regular; a much more difficult question is whether they must be totally regular. For $k=2$, we answer this question in the affirmative, thereby resolving an open problem stated in a recent paper of L'opez and Miret. We also present partial results for larger $k$. We finally put these results to practical use by proving the uniqueness of a 2-geodetic mixed graph with order exceeding the Moore bound by one.

Recommendations

• On networks with order close to the Moore bound
• On mixed Moore graphs
• A revised Moore bound for mixed graphs
• A family of mixed graphs with large order and diameter 2
• Approaching the mixed Moore bound for diameter two by Cayley graphs

Cites work

• scientific article; zbMATH DE number 426169 (Why is no real title available?)
• scientific article; zbMATH DE number 3455291 (Why is no real title available?)
• scientific article; zbMATH DE number 3632534 (Why is no real title available?)
• scientific article; zbMATH DE number 3432305 (Why is no real title available?)
• A new digraphs composition with applications to de Bruijn and generalized de Bruijn digraphs
• A revised Moore bound for mixed graphs
• Almost Moore digraphs are diregular
• Complete characterization of almost Moore digraphs of degree three
• Dynamic cage survey
• Maximum degree in graphs of diameter 2
• Moore graphs and beyond: a survey of the degree/diameter problem
• New mixed Moore graphs and directed strongly regular graphs
• Nonexistence of almost Moore digraphs of diameter four
• Nonexistence of almost Moore digraphs of diameter three
• On Moore Graphs with Diameters 2 and 3
• On \(k\)-geodetic digraphs with excess one
• On digraphs of excess one
• On mixed Moore graphs
• On mixed almost Moore graphs of diameter two
• On the impossibility of directed Moore graphs
• On total regularity of mixed graphs with order close to the Moore bound

Cited in

(16)

• On mixed almost Moore graphs of diameter two
• Moore mixed graphs from Cayley graphs
• A revised Moore bound for mixed graphs
• On large regular \(( 1 , 1 , k )\)-mixed graphs
• A family of mixed graphs with large order and diameter 2
• Moore bound for mixed networks
• On total regularity of mixed graphs with order close to the Moore bound
• On mixed Moore graphs
• An improved upper bound for the order of mixed graphs
• Approaching the mixed Moore bound for diameter two by Cayley graphs
• The Moore bound for irregular graphs
• On mixed cages
• Non existence of some mixed Moore graphs of diameter 2 using SAT
• Properties of mixed Moore graphs of directed degree one
• A variant of the McKay-Miller-Širáň construction for mixed graphs
• On networks with order close to the Moore bound

This page was built for publication: On total regularity of mixed graphs with order close to the Moore bound

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2287724)