×

Spectra of digraphs. (English) Zbl 1221.05177

Summary: In this primarily expository paper we survey classical and some more recent results on the spectra of digraphs, equivalently, the spectra of (0,1)-matrices, with emphasis on the spectral radius.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R.P. Agaev, P.Yu. Chebotarev, Laplace spectra of digraphs and their applications, (Russian, Russian summary), Avtomat. i Telemekh, No. 5, 2005, pp. 47-62 (translation in Autom. Remote Control 66 (2005) 719-733.; R.P. Agaev, P.Yu. Chebotarev, Laplace spectra of digraphs and their applications, (Russian, Russian summary), Avtomat. i Telemekh, No. 5, 2005, pp. 47-62 (translation in Autom. Remote Control 66 (2005) 719-733.
[2] Agaev, R.; Chebotarev, P., On the spectra of nonsymmetric Laplacian matrices, Linear Algebra Appl., 399, 157-168 (2005) · Zbl 1076.15012
[3] Al’pin, Yu. A., Bounds for the Perron root of a nonnegative matrix involving the properties of its graph, Math. Notes, 58, 1121-1123 (1995) · Zbl 0853.15012
[4] Babai, L., Arc transitive covering digraphs and their eigenvalues, J. Graph Theory, 9, 363-370 (1985) · Zbl 0583.05030
[5] Balbuena, C.; Ferrero, D.; Marcote, X.; Pelayo, I., Algebraic properties of a digraph and its line digraph, J. Interconnection Networks, 4, 377-393 (2003)
[6] Bermond, J. C.; Darrot, E.; Delmas, O.; Perennes, S., Hamilton circuits in the directed wrapped butterfly network, Discrete Appl. Math., 84, 21-42 (1998) · Zbl 0901.05062
[7] Biggs, N., Algebraic Graph Theory (1974), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0284.05101
[8] Boros, E.; Brualdi, R. A.; Cramer, Y.; Hoffman, A. J., Gers˘goron variations III: On a theorem of Brualdi and Varga, Linear Algebra Appl., 428, 14-19 (2008) · Zbl 1134.15006
[9] Brauer, A.; Gentry, I. C., On the characteristic roots of tournament matrices, Bull. Amer. Math. Soc., 74, 133-1135 (1968) · Zbl 0167.03002
[10] Brauer, A.; Gentry, I. C., Some remarks on tournaments, Linear Algebra Appl., 5, 311-318 (1972) · Zbl 0246.15012
[11] Brauer, A.; Gentry, I. C., Bounds for the greatest characteristic root of an irreducible nonnegative matrix, Linear Algebra Appl., 8, 105-107 (1974) · Zbl 0279.15011
[12] Brauer, A.; Gentry, I. C., Bounds for the greatest characteristic root of an irreducible nonnegative matrix II, Linear Algebra Appl., 8, 109-114 (1976) · Zbl 0323.15006
[13] Brualdi, R. A., Matrices, eigenvalues, and directed graphs, Linear and Multilinear Algebra, 11, 143-165 (1982) · Zbl 0484.15007
[14] Brualdi, R. A., Combinatorial Matrix Classes (2006), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1106.05001
[15] Brualdi, R. A.; Hoffman, A. J., On the spectral radius of \((0, 1)\)-matrices, Linear Algebra Appl., 65, 133-146 (1985) · Zbl 0563.15012
[16] Brualdi, R. A.; Hwang, S.-G., On the spectral radius of \((0, 1)\)-matrices with 1’s in prescribed positions, SIAM J. Matrix Anal. Appl., 17, 489-508 (1996) · Zbl 0858.15003
[17] Brualdi, R. A.; Kiernan, K., Landau’s and Rado’s theorems and partial tournaments, Electron. J. Combin., 16, 1, N2 (2009) · Zbl 1159.05014
[18] R.A. Brualdi, S. Kirkland, Totally nonnegative \(( 0 , 1 )\); R.A. Brualdi, S. Kirkland, Totally nonnegative \(( 0 , 1 )\) · Zbl 1217.05134
[19] Brualdi, R. A.; Li, Q., Problem 31, Discrete Math., 43, 329-330 (1983)
[20] Brualdi, R. A.; Mellendorf, S., Regions in the complex plane containing the eigenvalues of a matrix, Amer. Math. Monthly, 101, 975-985 (1994) · Zbl 0838.15010
[21] Brualdi, R. A.; Ryser, H. J., Combinatorial Matrix Theory (1991), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0746.05002
[22] Brualdi, R. A.; Shen, J., Landau’s inequalities for tournament scores and a short proof of a theorem on transitive sub-tournaments, J. Graph Theory, 38, 244-254 (2001) · Zbl 0996.05064
[23] Brualdi, R. A.; Solheid, E. S., On the spectral radius of complementary acyclic matrices of zeros and ones, SIAM J. Alg. Disc. Meth., 7, 265-272 (1986) · Zbl 0591.05051
[24] Brualdi, R. A.; Solheid, E. S., On the minimum spectral radius of matrices of zeros and ones, Linear Algebra Appl., 85, 81-100 (1987) · Zbl 0612.15008
[25] Caporossi, G.; Cvetković, D.; Gutman, I.; Hansen, P., Variable neighborhood search for extremal graphs. 2. Finding graphs with extremal energy, J. Chem. Inf. Comput. Sci., 39, 984-996 (1999)
[26] Ching, Li, A bound on the spectral radius of matrices of zeros and ones, Linear Algebra Appl., 132, 179-183 (1990) · Zbl 0701.15011
[27] Chung, F. R.K., Spectral Graph Theory (1997), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 0872.05052
[28] Chung, F. R.K., Laplacians and the Cheeger inequality for directed graphs, Ann. Comb., 9, 1-19 (2005) · Zbl 1059.05070
[29] F.R.K. Chung, The diameter and Laplacian eigenvalues of directed graphs, Electron. J. Combin., 13, Note 4, 2006, 6pp.; F.R.K. Chung, The diameter and Laplacian eigenvalues of directed graphs, Electron. J. Combin., 13, Note 4, 2006, 6pp. · Zbl 1084.05031
[30] Comellas, F.; Dalfó, C.; Fiol, M. A., Multidimensional Manhattan street networks, SIAM J. Discrete Math., 22, 1428-1447 (2008) · Zbl 1227.05156
[31] Comellas, F.; Fiol, M. A.; Gimbert, J.; Mitjana, M., The spectra of wrapped butterfly graphs, Networks, 42, 15-19 (2003) · Zbl 1018.05066
[32] Comellas, F.; Fiol, M. A.; Gimbert, J.; Mitjana, M., The spectra of Manhattan street networks, Linear Algebra Appl., 429, 1823-1839 (2008) · Zbl 1144.05316
[33] Cvetković, D.; Doob, M.; Sachs, H., Spectra of Graphs—Theory and Application (1995), Johann Ambosius Barth: Johann Ambosius Barth Heidelberg, Leipzig · Zbl 0824.05046
[34] de Caen, D.; Gregory, D. A.; Kirkland, S. J.; Pullman, N. J.; Maybee, J. S., Algebraic multiplicity of the eigenvalues of a tournament matrix, Linear Algebra Appl., 169, 179-193 (1992) · Zbl 0758.15012
[35] Dedo, E.; Zagaglia Salvi, N.; Kirkland, S., A particular case of bigraphs, Ars Combin., 45, 13-28 (1997) · Zbl 0933.05098
[36] Duval, A. M., A directed graph version of strongly regular digraphs, J. Combin. Theory, Ser. A, 47, 71-100 (1988) · Zbl 0642.05025
[37] Elsner, L.; van den Driessche, P., Bounds for the Perron root using max eigenvalues, Linear Algebra Appl., 428, 2000-2005 (2008) · Zbl 1141.15017
[38] Eschenbach, C.; Hall, F.; Hemasinha, R.; Kirkland, S. J.; Li, Z.; Shader, B. L.; Stuart, J. L.; Weaver, J. R., On almost regular tournament matrices, Linear Algebra Appl., 306, 103-121 (2000) · Zbl 0947.05040
[39] Esser, F.; Harary, F., Digraphs with real and Gaussian spectra, Discrete Appl. Math., 2, 113-124 (1980) · Zbl 0435.05027
[40] Esser, F.; Harary, F., The pairing theorem for digraph spectra, Bull. Malaysian Math. Soc., 4, 17-19 (1981) · Zbl 0474.05034
[41] Fiol, M. A.; Lladó, A. S., The partial line digraph technique in the design of large interconnection networks, IEEE Trans. Comput., C-41, 7, 848-857 (1992) · Zbl 1395.68029
[42] Gimbert, M. A. Fiol. J.; Miller, M., Multipartite Moore digraphs, Linear Algebra Appl., 419, 234-250 (2006) · Zbl 1105.05028
[43] Fiol, M. A.; Mitjana, M., The spectra of some families of digraphs, Linear Algebra Appl., 423, 109-118 (2007) · Zbl 1113.05063
[44] Friedland, S., The maximal eigenvalue of 0-1 matrices with prescribed number of ones, Linear Algebra Appl., 69, 33-69 (1985) · Zbl 0578.15010
[45] Godsil, C. D., Eigenvalues of graphs and digraphs, Linear Algebra Appl., 46, 43-50 (1982) · Zbl 0492.05032
[46] Godsil, C. D.; Hobart, S. A.; Martin, W. J., Representations of directed strongly regular graphs, European J. Combin., 28, 1980-1993 (2007) · Zbl 1121.05078
[47] C.D. Godsil, B. McKay, Products of graphs and their spectra, in Combinatorial Mathematics IV, Lecture Notes in Mathematics, vol. 560, Springer, Berlin, 1977, pp. 91-117.; C.D. Godsil, B. McKay, Products of graphs and their spectra, in Combinatorial Mathematics IV, Lecture Notes in Mathematics, vol. 560, Springer, Berlin, 1977, pp. 91-117.
[48] Godsil, C. D.; McKay, B., Constructing copsectral graphs, Aequationes Math., 25, 257-268 (1982) · Zbl 0527.05051
[49] C.D. Godsil, G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207, Springer-Verlag, New York, 2001.; C.D. Godsil, G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207, Springer-Verlag, New York, 2001. · Zbl 0968.05002
[50] Kirkland, S.; Gregory, D., Singular values of tournament matrices, Electron. Linear Algebra, 5, 39-52 (1999) · Zbl 0915.05085
[51] Gregory, D. A.; Kirkland, S. J.; Shader, B. L., Pick’s inequality and tournaments, Linear Algebra Appl., 186, 15-36 (1993) · Zbl 0776.05072
[52] Gutman, I., The energy of a graph, Ber. Math.-Stat. Sekt. Forschungszent Graz, 103, 1-22 (1978)
[53] I. Gutman, The energy of a graph: old and new results, in: A. Betten, R. Laue, A. Wasserman (Eds.), Algebraic Combinatorics and Applications, Springer-Verlag, Berlin, 2001, pp. 196-211.; I. Gutman, The energy of a graph: old and new results, in: A. Betten, R. Laue, A. Wasserman (Eds.), Algebraic Combinatorics and Applications, Springer-Verlag, Berlin, 2001, pp. 196-211. · Zbl 0974.05054
[54] Haemers, W.; Van Dam, E. R., Which graphs are determined by their spectrum?, Linear Algebra Appl., 373, 241-272 (2003) · Zbl 1026.05079
[55] Harary, F.; King, C.; Mowshowitz, A.; Read, R. C., Cospectral graphs and digraphs, Bull. London Math. Soc., 3, 321-328 (1971) · Zbl 0224.05125
[56] Hemasinha, R.; Weaver, J. R.; Kirkland, S. J.; Stuart, J. L., Properties of the Brualdi-Li tournament matrix, Linear Algebra Appl., 361, 63-73 (2003) · Zbl 1017.05074
[57] A.J. Hoffman, On limit points of spectral radii of non-negative symmetric matrices, in: Graph Theory and its Applications, Lecture Notes in Mathematics, vol. 303, Springer, Berlin, 1972, pp. 165-172.; A.J. Hoffman, On limit points of spectral radii of non-negative symmetric matrices, in: Graph Theory and its Applications, Lecture Notes in Mathematics, vol. 303, Springer, Berlin, 1972, pp. 165-172.
[58] Hoffman, A. J.; McAndrew, M. H., The polynomial of a directed graph, Proc. Amer. Math. Soc., 16, 303-309 (1965) · Zbl 0129.40102
[59] Hoffman, A. J., Geršgorin variations I: on a theme of Pupkov and Solov’ev, Linear Algebra Appl., 304, 173-177 (2000) · Zbl 0972.15012
[60] L. Hogben (Ed.), Handbook of Linear Algebra, Chapman & Hall/CRC Press, Boca Raton, FL, 2007, pp. 21-23.; L. Hogben (Ed.), Handbook of Linear Algebra, Chapman & Hall/CRC Press, Boca Raton, FL, 2007, pp. 21-23.
[61] Horn, R. A.; Johnson, C. R., Topics in Matrix Analysis (1991), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0729.15001
[62] Johnson, C. R.; Szulc, T., Further lower bounds for the smallest singular value, Linear Algebra Appl., 272, 169-179 (1998) · Zbl 0891.15013
[63] Jorgensen, L. K., Non-existence of directed strongly regular graphs, Discrete Math., 264, 111-126 (2003) · Zbl 1014.05074
[64] Kharaghani, H.; Tayfeh-Rezaie, B., On the energy of \((0, 1)\)-matrices, Linear Algebra Appl., 429, 2046-2051 (2008) · Zbl 1144.05320
[65] Kirkland, S., Hypertournament matrices, score vectors and eigenvalues, Linear and Multilinear Algebra, 30, 261-274 (1991) · Zbl 0751.15009
[66] Kirkland, S., On the minimum Perron value for an irreducible tournament matrix, Linear Algebra Appl., 244, 277-304 (1996) · Zbl 0860.15016
[67] Kirkland, S., A note on the sequence of Brualdi-Li matrices, Linear Algebra Appl., 248, 233-240 (1996) · Zbl 0865.15014
[68] Kirkland, S., Perron vector bounds for a tournament matrix with applications to a conjecture of Brualdi and Li, Linear Algebra Appl., 262, 209-227 (1997) · Zbl 0880.15024
[69] Kirkland, S., An upper bound on the Perron value of an almost regular tournament matrix, Linear Algebra Appl., 361, 7-22 (2003) · Zbl 1019.15004
[70] Kirkland, S.; Shader, B. L., Tournament matrices with extremal spectral properties, Linear Algebra Appl., 196, 1-17 (1994) · Zbl 0790.15021
[71] Kolotilina, L. Yu., Bounds and inequalities for the Perron root of a nonnegative matrix, J. Math. Sci., 2481-2507 (2004) · Zbl 1071.15020
[72] Kolotilina, L. Yu., Bounds and inequalities for the Perron root of a nonnegative matrix, II. Circuit bounds and inequalities, J. Math. Sci., 127, 1988-2005 (2005) · Zbl 1081.15531
[73] Kolotilina, L. Yu., Bounds and inequalities for the Perron root of a nonnegative matrix, III. Bounds dependent on simple paths and circuits, J. Math. Sci., 137, 4801-4814 (2006)
[74] Kolotilina, L. Yu., Bounds for the singular values of a matrix involving its sparsity pattern, J. Math. Sci., 137, 4794-4800 (2006)
[75] Krishnamoorthy, V.; Parthasarathy, K. R., A note on non-isomorphic cospectral digraphs, J. Combin. Theory, Ser. B, 17, 39-40 (1974) · Zbl 0268.05107
[76] Krishnamoorthy, V.; Parthasarathy, K. R., Cospectral graphs and digraphs with given automorphism group, J. Combin. Theory, Ser. B, 19, 204-213 (1975) · Zbl 0285.05108
[77] Kwapisz, J., On the spectral radius of a directed graph, J. Graph Theory, 23, 405-411 (1996) · Zbl 0866.05043
[78] Lin, G.; Zhang, F., On the characteristic polynomial of directed line graph and a type of cospectral directed graph, Kexue TongBao (Chinese), 22, 348-1350 (1983)
[79] Liu, Bolian, On sharp bounds of the spectral radius of graphs, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat., 9, 55-59 (1998) · Zbl 1008.05096
[80] Liu, B.; Lai, H.-J. H., Matrices in Combinatorics and Graph Theory (2000), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht/Boston/London, pp. 19-20
[81] López, W.; Rada, J., Equienergetic digraphs, Int. J. Pure Appl. Math., 6, 361-372 (2007) · Zbl 1131.05310
[82] Mathias, R., The spectral norm of a nonnegative matrix, Linear Algebra Appl., 139, 269-284 (1990) · Zbl 0705.15012
[83] Maybee, J. S.; Pullman, N. J., Tournament matrices and their generalizations, Linear and Multilinear Algebra, 28, 57-70 (1990) · Zbl 0714.05041
[84] B.D. McKay, F. Oggier, G.F. Royle, N.J.A. Sloane, I.M Wanless, H.S. Wilf, Acyclic digraphs and eigenvalues of \(( 0 , 1 )\); B.D. McKay, F. Oggier, G.F. Royle, N.J.A. Sloane, I.M Wanless, H.S. Wilf, Acyclic digraphs and eigenvalues of \(( 0 , 1 )\) · Zbl 1064.05101
[85] Meng, J. X., Non-isomorphic cospectral Cayley digraphs, Graph Theory Notes, 35, 51-53 (1998)
[86] Mowshowitz, A., The characteristic polynomial of a graph, J. Combin. Theory, Ser. B, 12, 177-193 (1972) · Zbl 0212.29401
[87] Nikiforov, V., The energy of graphs and matrices, J. Math. Anal. Appl., 326, 1472-1475 (2007) · Zbl 1113.15016
[88] Nikiforov, V., Graphs and matrices with maximal energy, J. Math. Anal. Appl., 327, 735-738 (2007) · Zbl 1112.05067
[89] Ostrowski, A., Über die determinaten mit über wiegender Hauptdiagonale, Comm. Math. Helv., 10, 69-96 (1937) · JFM 63.0035.01
[90] Peña, I.; Rada, J., Energy of digraphs, Linear and Multilinear Algebra, 56, 565-579 (2008) · Zbl 1155.05031
[91] Pupkov, V. A., Some sufficient conditions for the non-degeneracy of matrices, USSR Comput. Math. Math. Phys., 24, 86-89 (1984) · Zbl 0581.15002
[92] Rada, J., The McClelland inequality for the energy of digraphs, Linear Algebra Appl., 430, 800-804 (2009) · Zbl 1151.05026
[93] Rada, J., Lower bounds for the energy of digraphs, Linear Algebra Appl., 432, 2174-2180 (2010) · Zbl 1227.05186
[94] Rosenfeld, V. R., Some spectral properties of the arc-graph (English summary), Match, 43, 41-48 (2001) · Zbl 1026.05083
[95] Savchenko, S. V., On the change of the Jordan form under transition from the adjacency matrix of a vertex-transitive digraph to its principal submatrix of co-order one, Linear Algebra Appl., 394, 225-235 (2005) · Zbl 1066.15011
[96] Savchenko, S. V., Normal matrices and their prinicpal submatrices of co-order one, Linear Algebra Appl., 419, 556-568 (2006) · Zbl 1115.15022
[97] Schur, J., Bemerkungen zur Theorie der beschränkten Bilinearformen mit endliche vielen Veränderlichen, Journal für Reine und Angew. Mathematik, 140, 1-28 (1911) · JFM 42.0367.01
[98] Solov’ev, V. A., A generalization of Geršgorin’s theorem, USSR Izvestiya, 23, 545-559 (1984)
[99] Strunkov, S. P., On weakly cospectral graphs (Russian), Dokl. Akad. Nauk, 379, 02-304 (2001) · Zbl 1043.05080
[100] Schwarz, B., Rearrangements of square matrices with non-negative elements, Duke Math. J., 31, 45-62 (1964) · Zbl 0121.26401
[101] Tam, Bit-Shun; Shangjun, Yang; Xiaodong, Zhang, Invertibility of irreducible matrices, Linear Algebra Appl., 259, 39-70 (1997) · Zbl 0886.15026
[102] Snellman, J., The maximal spectral radius of a digraph with \((M + 1)^2 - S\) edges, Electron. J. Linear Algebra, 10, 179-189 (2003) · Zbl 1047.05029
[103] R.S. Varga, Geršgorin, His Circles, Springer Series in Computational Mathematics, vol. 36, Springer, Berlin, Heidelberg, New York, 2004.; R.S. Varga, Geršgorin, His Circles, Springer Series in Computational Mathematics, vol. 36, Springer, Berlin, Heidelberg, New York, 2004.
[104] Walters, I., Constructing cospectral digraphs with arbitrary centers, Electron. Notes Discrete Math., 11 (2002), 6 pages · Zbl 1075.05544
[105] Wu, Y.; Deng, A., Hoffman polynomials of nonnegative irreducible matrices and strongly connected digraphs, Linear Algebra Appl., 414, 138-171 (2006) · Zbl 1083.05030
[106] G.-H. Xu, C.-Q. Xu, Sharp bounds for the spectral radius of digraphs, Linear Algebra Appl., in press.; G.-H. Xu, C.-Q. Xu, Sharp bounds for the spectral radius of digraphs, Linear Algebra Appl., in press.
[107] Zhang, F.; Chen, Z., Limit points of eigenvalues of (di)graphs, Czech. Math. J., 56, 131, 895-902 (2006) · Zbl 1164.05412
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.