×

On the weak distance-regularity of Moore-type digraphs. (English) Zbl 1091.05042

Summary: We prove that Moore digraphs, and some other classes of extremal digraphs, are weakly distance-regular in the sense that there is an invariance of the number of walks between vertices at a given distance. As weakly distance-regular digraphs, we then compute their complete spectrum from a ‘small’ intersection matrix. This is a very useful tool for deriving some results about their existence and/or their structural properties. For instance, we present here an alternative and unified proof of the existence results on Moore digraphs, Moore bipartite digraphs and, more generally, Moore generalized \(p\)-cycles. In addition, we show that the line digraph structure appears as a characteristic property of any Moore generalized \(p\)-cycle of diameter \(D \geq 2p\).

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C20 Directed graphs (digraphs), tournaments
05E30 Association schemes, strongly regular graphs
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bannai E, Journal of the Faculty of Science. Tokyo University 20 pp 191– (1973)
[2] DOI: 10.1007/s003730050019 · Zbl 0905.05033
[3] DOI: 10.1002/jgt.20042 · Zbl 1060.05036
[4] DOI: 10.1002/jgt.3190200310 · Zbl 0838.05054
[5] Baskoro ET, The Australasian Journal of Combinatorics 9 pp 291– (1994)
[6] DOI: 10.1007/3-540-40064-8_4
[7] Biggs N, Algebraic Graph Theory,, 2. ed. (1974)
[8] Biggs N, Combinatorial Mathematics and its Applications pp 15– (1971)
[9] Bosák J, Mathematica Slovaca 28 pp 189– (1978)
[10] Bridges WG, Journal of Combinatorial Theory. Series B 29 pp 339– · Zbl 0388.05019
[11] Chartrand, G and Lesniak, L. 1996. ”Graphs & Digraphs”. In , 3rd Edn, London: Chapman & Hall. · Zbl 0890.05001
[12] DOI: 10.1090/S0894-0347-1989-0965008-X
[13] DOI: 10.1002/net.10085 · Zbl 1018.05066
[14] DOI: 10.1016/j.jctb.2003.07.003 · Zbl 1033.05100
[15] Conway JH, Annals of Discrete Mathematics 13 pp 61– (1982)
[16] DOI: 10.1017/S0305004100048015
[17] DOI: 10.1016/S0095-8956(81)80009-3 · Zbl 0468.05034
[18] Davis, PJ. 1979. ”Circulant Matrices”. New York: Wiley-Interscience.
[19] DOI: 10.1016/S0012-365X(01)00255-2 · Zbl 1025.05060
[20] DOI: 10.1002/jgt.10112 · Zbl 1036.05025
[21] DOI: 10.1002/jgt.3190140608 · Zbl 0725.05044
[22] DOI: 10.1109/TC.1984.1676455 · Zbl 0528.68048
[23] DOI: 10.1016/S0012-365X(00)00316-2 · Zbl 0979.05059
[24] Gimbert J, The Australasian Journal of Combinatorics 20 pp 77– (1999)
[25] DOI: 10.1016/S0166-218X(01)00186-X · Zbl 0995.05097
[26] Godsil, CD. 1993. ”Algebraic Combinatorics”. New York: Chapman and Hall.
[27] DOI: 10.1016/S0166-218X(98)00120-6 · Zbl 0919.05035
[28] Hagen L, IEEE Digest of Technical Papers pp 10– (1991)
[29] Hagen L, IEEE Transactions CAD/ICS 11 pp 1074– (1992)
[30] DOI: 10.1007/BF00147398 · Zbl 0333.05010
[31] DOI: 10.2307/2312780 · Zbl 0112.14901
[32] DOI: 10.1090/S0002-9939-1965-0191841-6
[33] DOI: 10.1147/rd.45.0497 · Zbl 0096.38102
[34] Lancaster, P and Tismenetsky, M. 1985. ”The Theory of Matrices”. In , 2nd Edn, Orlando, FL: Academic Press. · Zbl 0558.15001
[35] DOI: 10.1016/S0012-365X(99)00357-X · Zbl 0942.05026
[36] DOI: 10.1016/0095-8956(89)90029-4 · Zbl 0719.05042
[37] Plesník J, Acta Mathematica Universitatis Comenianae 29 pp 29– (1974)
[38] Rowlinson P, Oxford Lecture Ser. Math. Appl. 5, in: Graph Connections pp 86– (1997)
[39] DOI: 10.1016/S0024-3795(97)10072-6 · Zbl 0933.15023
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.