×

Weakly distance-regular digraphs. (English) Zbl 1033.05100

Summary: We introduce the concept of weakly distance-regular digraph and study some of its basic properties. In particular, the (standard) distance-regular digraphs, introduced by Damerell, turn out to be those weakly distance-regular digraphs which have a normal adjacency matrix. As happens in the case of distance-regular graphs, the study is greatly facilitated by a family of orthogonal polynomials called the distance polynomials. For instance, these polynomials are used to derive the spectrum of a weakly distance-regular digraph. Some examples of these digraphs, such as the butterfly and the cycle prefix digraph which are interesting for their applications, are analyzed in the light of the developed theory. Also, some new constructions involving the line digraph and other techniques are presented.

MSC:

05E30 Association schemes, strongly regular graphs
05C20 Directed graphs (digraphs), tournaments
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05E35 Orthogonal polynomials (combinatorics) (MSC2000)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bannai, E.; Cameron, P. J.; Kahn, J., Nonexistence of certain distance-transitive digraphs, J. Combin. Theory Ser. B, 31, 105-110 (1981) · Zbl 0468.05035
[2] Bannai, E.; Ito, T., Algebraic Combinatorics I: Association Schemes (1984), Benjamin/Cummings: Benjamin/Cummings Menlo Park, CA · Zbl 0555.05019
[3] Bermond, J.-C.; Darrot, E.; Delmas, O.; Perennes, S., Hamilton circuits in the directed wrapped butterfly network, Discrete Appl. Math., 84, 1-3, 21-42 (1998) · Zbl 0901.05062
[4] N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1974; 2nd Edition, 1993.; N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1974; 2nd Edition, 1993. · Zbl 0284.05101
[5] A. Brouwer, personal homepage:; A. Brouwer, personal homepage:
[6] Brualdi, R. A.; Ryser, H. J., Combinatorial Matrix Theory (1991), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0746.05002
[7] Comellas, F.; Fiol, M. A., Vertex-symmetric digraphs with small diameter, Discrete Appl. Math., 58, 1, 1-12 (1995) · Zbl 0822.05033
[8] Comellas, F.; Mitjana, M., The spectra of cycle prefix digraphs, SIAM J. Discrete Math., 16, 3, 418-421 (2003) · Zbl 1029.05095
[9] Damerell, R. M., Distance-transitive and distance-regular digraphs, J. Combin. Theory Ser. B, 31, 1, 46-53 (1981) · Zbl 0468.05034
[10] Douglas, D. A.; Nomura, K., The girth of a directed distance-regular graph, J. Combin. Theory Ser. B, 58, 1, 34-39 (1993) · Zbl 0733.05044
[11] Duval, A. M., A directed graph version of strongly regular graphs, J. Combin. Theory Ser. A, 47, 1, 71-100 (1988) · Zbl 0642.05025
[12] Enomoto, H.; Mena, R. A., Distance-regular digraphs of girth 4, J. Combin. Theory Ser. B, 43, 3, 293-302 (1987) · Zbl 0642.05024
[13] Espona, M.; Serra, O., Cayley digraphs based on the de Bruijn networks, SIAM J. Discrete Math., 11, 2, 305-317 (1998) · Zbl 0916.05028
[14] Faber, V.; Moore, J. W.; Chen, W. Y.C., Cycle prefix digraphs for symmetric interconnection networks, Networks, 23, 641-649 (1993) · Zbl 0802.90043
[15] Fiol, M. A., Algebraic characterizations of distance-regular graphs, Discrete Math., 246, 1-3, 111-129 (2002) · Zbl 1025.05060
[16] Fiol, M. A.; Yebra, J. L.A.; Alegre, I., Line digraphs iterations and the \((d,k)\) digraph problem, IEEE Trans. Comput., C-32, 400-403 (1984) · Zbl 0528.68048
[17] Godsil, C. D., Algebraic Combinatorics (1993), Chapman & Hall: Chapman & Hall New York · Zbl 0814.05075
[18] Klasing, R.; Lüling, R.; Monien, B., Compressing cube-connected cycles and butterfly networks, Networks, 32, 1, 47-65 (1998) · Zbl 1015.68006
[19] Lam, C. W.H., Distance-transitive digraphs, Discrete Math., 29, 3, 265-274 (1980) · Zbl 0442.05031
[20] Lancaster, P.; Tismenetsky, M., The Theory of Matrices (1985), Academic Press: Academic Press Orlando, FL · Zbl 0516.15018
[21] Liebler, R. A.; Mena, R. A., Certain distance-regular digraphs and related rings of characteristic 4, J. Combin. Theory Ser. A, 47, 1, 111-123 (1988) · Zbl 0641.05022
[22] X. Marcote, C. Balbuena, I. Pelayo, The relationship between the Jordan normal forms of a digraph and its line digraph, Research Report, Universitat Politècnica de Catalunya, 1999.; X. Marcote, C. Balbuena, I. Pelayo, The relationship between the Jordan normal forms of a digraph and its line digraph, Research Report, Universitat Politècnica de Catalunya, 1999.
[23] M. Mitjana, Propagació d’informació en grafs i digrafs que modelen xarxes d’interconnexió simètriques (Catalan), Ph.D. Thesis, Universitat Politècnica de Catalunya, 1999.; M. Mitjana, Propagació d’informació en grafs i digrafs que modelen xarxes d’interconnexió simètriques (Catalan), Ph.D. Thesis, Universitat Politècnica de Catalunya, 1999.
[24] J.C. Montserrat, Propiedades matriciales de los grafos dirigidos, Master Thesis, Universitat Politècnica de Catalunya, 1986 (Spanish).; J.C. Montserrat, Propiedades matriciales de los grafos dirigidos, Master Thesis, Universitat Politècnica de Catalunya, 1986 (Spanish).
[25] P. Rowlinson, Linear algebra, in: L.W. Beineke, R.J. Wilson (Eds.), Graph Connections, Oxford Lecture Series in Mathematical Applications, Vol. 5, Oxford University Press, New York, 1997, pp. 86-99.; P. Rowlinson, Linear algebra, in: L.W. Beineke, R.J. Wilson (Eds.), Graph Connections, Oxford Lecture Series in Mathematical Applications, Vol. 5, Oxford University Press, New York, 1997, pp. 86-99.
[26] Takahashi, T., Distance-regular digraphs of girth 6, Mem. Fac. Sci. Kyushu Univ. Ser. A, 45, 2, 155-166 (1991) · Zbl 0751.05049
[27] Wang, K.; Suzuki, H., Weakly distance-regular digraphs, Discrete Math., 264, 1-3, 225-263 (2003) · Zbl 1014.05077
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.