×

Which Faber-Moore-Chen digraphs are Cayley digraphs? (English) Zbl 1220.05052

Summary: The problem of finding the largest graphs and digraphs of given degree and diameter is known as the ‘degree-diameter’ problem. One of the families of largest known vertex-transitive digraphs of given degree and diameter is the Faber-Moore-Chen digraphs. In our contribution we will classify those Faber-Moore-Chen digraphs that are Cayley digraphs.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chen, W. Y.C.; Faber, V.; Knill, E., Restricted routing and wide diameter of the cycle prefix network, (Interconnection Networks and Mapping and Scheduling Parallel Computations. Interconnection Networks and Mapping and Scheduling Parallel Computations, New Brunswick, NJ, 1994 (1995), Amer. Math. Soc.: Amer. Math. Soc. Providence RI), 31-46 · Zbl 0838.68006
[2] W.Y.C. Chen, V. Faber, B. Li, Automorphisms of the cycle prefix digraph, preprint.; W.Y.C. Chen, V. Faber, B. Li, Automorphisms of the cycle prefix digraph, preprint.
[3] Comellas, F.; Fiol, M. A., Vertex-symmetric digraphs with small diameter, Discrete Appl. Math., 58, 1-11 (1995) · Zbl 0822.05033
[4] Comellas, F.; Mitjana, M., Broadcasting in cycle prefix digraphs, Discrete Appl. Math., 83, 1-3, 31-39 (1998) · Zbl 0909.05042
[5] Comellas, F.; Mitjana, M., Cycles in the cycle prefix digraphs, Ars Combin., LX, 171-180 (2001) · Zbl 1071.05540
[6] Dixon, J.; Mortimer, B., Permutation groups (1996), Springer: Springer New York · Zbl 0951.20001
[7] V. Faber, J.W. Moore, 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.; V. Faber, J.W. Moore, 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.
[8] Faber, V.; Moore, J. W.; Chen, W. Y.C., Cycle prefix digraphs for symmetric interconnection networks, Networks, 23, 641-649 (1993) · Zbl 0802.90043
[9] Gómez, J., On large vertex-symmetric digraphs, Discrete Math. 0012-365X, 309, 6, 1213-1221 (2009) · Zbl 1225.05112
[10] Gómez, J., Large vertex-symmetric digraphs, Networks, 50, 4, 250-421 (2007) · Zbl 1134.05031
[11] W.H. Kautz, Bounds on directed \(( d , k )\); W.H. Kautz, Bounds on directed \(( d , k )\)
[12] Liaw, S.-C.; Chang, G. J.; Cao, F.; Hsu, D. F., Fault-tolerant routing in circulant networks and cycle prefix networks, Ann. Comb., 2, 2, 165-172 (1998) · Zbl 0930.05035
[13] M. Miller, J. Širáň, Moore graphs and beyond:. A survey, Electron. J. Combin., Dynamic Survey DS 14, 61 p. Published on-line in December 2005.; M. Miller, J. Širáň, Moore graphs and beyond:. A survey, Electron. J. Combin., Dynamic Survey DS 14, 61 p. Published on-line in December 2005.
[14] Sabidussi, G., On a class of fixed-point free graphs, Proc. Amer. Math. Soc., 9, 800-804 (1958) · Zbl 0091.37701
[15] Zassenhaus, H., Über endliche Fastkörper, Abh. Math. Sem. Hamburg, 11, 187-220 (1936) · JFM 61.0126.01
[16] M. Ždímalová, Which Kautz digraph of diameter two are Cayley digraphs?, International Conference 70 years of FCE STU, 4.-5. December 2008, Bratislava Slovakia, Zborník príspevkov z medzinárodnej konferencie, CD.; M. Ždímalová, Which Kautz digraph of diameter two are Cayley digraphs?, International Conference 70 years of FCE STU, 4.-5. December 2008, Bratislava Slovakia, Zborník príspevkov z medzinárodnej konferencie, CD.
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.