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

DOI10.1007/S00373-019-02114-2zbMATH Open1440.05130arXiv1811.00650OpenAlexW2982557387MaRDI QIDQ2287724FDOQ2287724

Authors: James Tuite, Grahame Erskine 

Publication date: 21 January 2020

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

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.

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

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

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)

Cites Work

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

Cited In (16)

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

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)