A revised Moore bound for mixed graphs

Title: A revised Moore bound for mixed graphs
Creator: Buset, Dominique; El Amiri, Mourad El; Erskine, Grahame; Miller, Mirka; Pérez-Rosés, Hebert
Relation: Discrete Mathematics Vol. 339, Issue 8, p. 2066-2069
Publisher Link: http://dx.doi.org/10.1016/j.disc.2016.03.005
Publisher: Elsevier
Resource Type: journal article
Date: 2016
Description: 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.
Subject: degree-diameter problem; mixed graphs; Moore bound
Identifier: http://hdl.handle.net/1959.13/1345586
Identifier: uon:29677
Identifier: ISSN:0012-365X
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format