×

zbMATH — the first resource for mathematics

Vertex-symmetric digraphs with small diameter. (English) Zbl 0822.05033
New families of large vertex-symmetric digraphs with a given maximum out- degree \(\Delta\) and diameter at most \(D\) are presented. The authors use certain digraphs on alphabets and develop new construction techniques. The largest known vertex-symmetric \((\Delta, D)\) digraphs are surveyed in a table.

MSC:
05C20 Directed graphs (digraphs), tournaments
05C35 Extremal problems in graph theory
05C12 Distance in graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bermond, J.-C.; Delorme, C.; Quisquater, J.J., Strategies for interconnection networks: some methods from graph theory, J. parallel distrib. comput., 3, 433-449, (1986)
[2] Bridges, W.G.; Toueg, S., On the impossibility of directed Moore graphs, J. combin. theory ser. B, 29, 339-341, (1980) · Zbl 0388.05019
[3] de Bruijn, N.G., A combinatorial problem, (), 758-764 · Zbl 0060.02701
[4] Chudnovsky, D.V.; Chudnovsky, G.V.; Denneau, M.M., Regular graphs with small diameter as models for interconnection networks, (), 232-239
[5] Conway, J.H.; Guy, M.J.T., Message graphs, Ann. discrete math., 13, 61-64, (1982) · Zbl 0495.05029
[6] Dinneen, M.J., Algebraic methods for efficient network constructions, ()
[7] Dinneen, M.J.; Hafner, P.R., New results for the degree/diameter problem, () · Zbl 0806.05039
[8] Elpas, B., Topological constrains on interconnection limited logic, (), 133-197
[9] Faber, V.; Moore, J.W., High-degree low-diameter interconnection networks with vertex symmetry: the directed case, ()
[10] Fiol, M.A.; Alegre, I.; Yebra, J.L.A.; Fàbrega, J., Digraphs with walks of equal length between vertices, (), 702-713 · Zbl 0571.05021
[11] Fiol, M.A.; Yebra, J.L.A.; Alegre, I., Line digraph iterations and the (d, k) digraph problem, IEEE trans. comput., 33, 400-403, (1984) · Zbl 0528.68048
[12] Fiol, M.A.; Yebra, J.L.A.; Alegre, I.; Valero, M., A discrete optimization problem in local networks and data alignment, IEEE trans. comput., 36, 702-713, (1987)
[13] J. Gómez, Department de Matemàtica Aplicada i Telemàtica, Universitat Politècnica de Catalunya, personal communication, 1992.
[14] P.R. Hafner, Department of Mathematics and Statistics, University of Auckland, personal communication, 1992.
[15] M. Jiang and F. Ruskey, Determining the Hamilton-connectedness of certain vertex-transitive graphs, Discrete Math., to appear. · Zbl 0824.05044
[16] Kautz, W.H., Bounds on directed (d, k) graphs, (), 20-28
[17] Kautz, W.H., Design of optimal interconnection networks for multiprocessors, (), 249-272
[18] Mendelsohn, N.S., Directed graphs with the unique path property, (), 783-799 · Zbl 0209.28402
[19] Plesník, J.; Znám, Š., Strongly geodetic directed graphs, Acta fac. rerum natur. univ. Comenian. math. publ., 29, 29-34, (1974) · Zbl 0291.05106
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.