×

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
PDFBibTeX XMLCite
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, (Kon. Nederl. Acad. Wetensch. Proc., A49 (1946)), 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, (Proceedings 3rd International Conference on Supercomputing, ICS ’88. Proceedings 3rd International Conference on Supercomputing, ICS ’88, Boston, May 16-20 (1988)), 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, (Master Thesis (1991), Department of Computer Science, University of Victoria: Department of Computer Science, University of Victoria Victoria, BC)
[7] Dinneen, M. J.; Hafner, P. R., New results for the degree/diameter problem, (Report Series No. 265 (1992), Department of Mathematics and Statistics, University of Auckland: Department of Mathematics and Statistics, University of Auckland Auckland) · Zbl 0806.05039
[8] Elpas, B., Topological constrains on interconnection limited logic, (Proceedings 5th Symposium on Switching Circuit Theory and Logical Design, 5-164 (1964), IEEE: IEEE New York), 133-197
[9] Faber, V.; Moore, J. W., High-degree low-diameter interconnection networks with vertex symmetry: the directed case, (Technical Report LA-UR-88-1051 (1988), Los Alamos National Laboratory: Los Alamos National Laboratory Los Alamos, NM)
[10] Fiol, M. A.; Alegre, I.; Yebra, J. L.A.; Fàbrega, J., Digraphs with walks of equal length between vertices, (Alavi, Y.; etal., Graph Theory with Applications to Algorithms and Computer Science (1985), Wiley: Wiley New York), 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.; 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.; 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.; 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, (Theory of Cellular Logic Networks and Machines. Theory of Cellular Logic Networks and Machines, AFCRL-68-0668, SRI Project 7258, Final Report (1968)), 20-28
[17] Kautz, W. H., Design of optimal interconnection networks for multiprocessors, (Architecture and Design of Digital Computers (1969), Nato Advanced Summer Institute), 249-272
[18] Mendelsohn, N. S., Directed graphs with the unique path property, (Combinatorial Theory and its Applications II, Proceedings Colloquium Balatonfürer. Combinatorial Theory and its Applications II, Proceedings Colloquium Balatonfürer, 1969 (1970), North-Holland: North-Holland Amsterdam), 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. 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.