×

Asymptotic comparison of two constructions for large digraphs of given degree and diameter. (English) Zbl 1250.05052

This paper considers the degree-diameter problem for directed graphs, that is the determination of the largest order \(n(\Delta,D)\) of maximum in- and outdegree \(\Delta\) and diameter \(D\). The authors compare two constructions of large digraphs of parameters \(\Delta\) and \(D\). The first one is Faber and Moore’s [V. Faber and J. W. Mooree, High-degree low-diameter interconnection networks with vertex symmetry: the directed case. Technical Report LA-UR-88-1051, Los Alamos National Laboratory, Los Alamos, NM (1988)]. The other one is Comellas and Fiol’s [F. Comellas and M. Fiol, “Vertex-symmetric digraphs with small diameter”, Discrete Appl. Math. 58, No. 1, 1–11 (1995; Zbl 0822.05033)]. This second construction uses ”digraph composition” starting from smaller base digraphs and is claimed to give best results whent the base graph is a Faber-Moore graph. In the present paper the authors use elementary calculations of about one page length to show that asymptotically for a fixed diameter, the order of the digraphs arising from the construction of Comellas and Fiol applied to the graphs of Faber and Moore is smaller than the order of the plain Faber-Moore digraphs (for the accordingly amended diameter).

MSC:

05C20 Directed graphs (digraphs), tournaments
05C12 Distance in graphs
05C07 Vertex degrees
05C35 Extremal problems in graph theory

Citations:

Zbl 0822.05033
PDFBibTeX XMLCite
Full Text: Link

References:

[1] Commellas, F., Fiol, M. A.: Vertex-symmetric digraphs with small diameter. Discrete Applied Mathematics 58, 1-11, 1995 · Zbl 0822.05033
[2] Faber, V., Moore, J. W.: High-degree low-diameter interconnection networks with vertex symmetry: the directed case. Technical Report LA-UR-88-1051, Los Alamos National Laboratory, Los Amalos, NM 1988
[3] Gómez, J.: Large vertex-symmetric digraphs, Networks. 50 (4), 241-250, 2007 · Zbl 1134.05031
[4] Miller, M., Širáň, J.: Moore graphs and beyond: A survey. Electron. J. Combin., Dynamic Survey DS 14 (published on-line in December 2005), 61 pp, 2005 · Zbl 1079.05043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.