The Open UniversitySkip to content

On Total Regularity of Mixed Graphs with Order Close to the Moore Bound

Tuite, James and Erskine, Grahame (2019). On Total Regularity of Mixed Graphs with Order Close to the Moore Bound. Graphs and Combinatorics (Early access).

Full text available as:
PDF (Version of Record) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (534kB) | Preview
DOI (Digital Object Identifier) Link:
Google Scholar: Look up in Google Scholar


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 edges and directed arcs. The degree/diameter problem for mixed graphs asks for the largest possible order of a network with diameter $k$, maximum undirected degree $\leq r$ and maximum directed out-degree $\leq z$. Similarly one can search for the smallest possible $k$-geodetic mixed graphs with minimum undirected degree $\geq r$ and minimum directed out-degree $\geq z$. A simple counting argument reveals the existence of a natural bound, the Moore bound, on the order of such graphs; a graph that meets this limit is a 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 Lopez 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.

Item Type: Journal Item
Copyright Holders: 2019 The Authors
ISSN: 1435-5914
Keywords: degree-diameter problem; mixed graphs; almost Moore graphs; total regularity; excess
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 67892
Depositing User: James Tuite
Date Deposited: 30 Oct 2019 11:41
Last Modified: 24 Jan 2020 17:30
Share this page:


Altmetrics from Altmetric

Citations from Dimensions

Download history for this item

These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU