Hoffman polynomials of nonnegative irreducible matrices and strongly connected digraphs. (English) Zbl 1083.05030
Summary: For a nonnegative \(n \times n\) matrix \(A\), we find that there is a polynomial \(f(x) \in \mathbb R[x]\) such that \(f(A)\) is a positive matrix of rank one if and only if \(A\) is irreducible. Furthermore, we show that the lowest degree of such a polynomial \(f(x)\) with tr \(f(A) = n\) is unique. Thus, generalizing the well-known definition of the Hoffman polynomial of a strongly connected regular digraph, for any irreducible nonnegative \(n \times n\) matrix \(A\), we are led to define its Hoffman polynomial to be the polynomial \(f(x)\) of minimum degree satisfying that \(f(A)\) is positive and has rank 1 and trace \(n\). The Hoffman polynomial of a strongly connected digraph is defined to be the Hoffman polynomial of its adjacency matrix. We collect in this paper some basic results and open problems related to the concept of Hoffman polynomials.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 15A24 | Matrix equations and identities |
| 05C20 | Directed graphs (digraphs), tournaments |
Keywords:
Perron eigenvalue; Perron eigenvector; Perron pair; matrix equation; tensor product; elementary equivalence; split; amalgamation; harmonic digraphReferences:
| [1] | Bannai, E.; Ito, T., On Moore graphs, J. Fac. Sci. Univ. Tokyo Ser. A, 20, 191-208 (1973) · Zbl 0275.05121 |
| [2] | Bernau, S. J.; Abian, A., Jordan canonical forms of matrices AB and BA, Rend. Istit. Math. Univ. Trieste, 20, 101-108 (1988) · Zbl 0693.15005 |
| [3] | Biggs, N., Algebraic Graph Theory (1993), Cambridge University Press |
| [4] | Bollobás, B., Modern Graph Theory (2002), Springer · Zbl 1027.05083 |
| [5] | Bridges, W. G.; Mena, R. A., Multiplicative designs II: uniform normal and reducible cases, J. Combin. Theory Ser. A, 27, 269-281 (1979) · Zbl 0443.05023 |
| [6] | Bridges, W. G.; Mena, R. A., Multiplicative cones—a family of three eigenvalue graphs, Aequationes Math., 22, 208-214 (1981) · Zbl 0481.05043 |
| [7] | Bridges, W. G.; Toueg, S., On the impossibility of directed Moore graphs, J. Combin. Theory Ser. B, 29, 339-341 (1980) · Zbl 0388.05019 |
| [8] | Brualdi, R. A., Combinatorial verification of the elementary divisors of tensor products, Linear Algebra Appl., 71, 31-47 (1985) · Zbl 0595.15023 |
| [9] | Brualdi, R. A.; Ryser, H. J., Combinatorial Matrix Theory (1991), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0746.05002 |
| [10] | Comellas, F.; Fiol, M. A.; Gimbert, J.; Mitjana, M., The spectra of wrapped butterfly digraphs, Networks, 42, 15-19 (2003) · Zbl 1018.05066 |
| [11] | Comellas, F.; Mitjana, M., The spectra of cycle prefix digraphs, SIAM J. Disc. Math., 16, 418-421 (2003) · Zbl 1029.05095 |
| [12] | Curtin, B., Algebraic characterizations of graph regularity conditions, Des. Codes Crytogr., 34, 241-248 (2005) · Zbl 1055.05154 |
| [13] | Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs (1979), Academic Press: Academic Press New York |
| [14] | Dress, A.; Grüneward, S., Semiharmonic trees and monocyclic graphs, Appl. Math. Lett., 16, 1329-1332 (2003) · Zbl 1039.05050 |
| [15] | Dress, A.; Stevanović, D., Hoffman-type identities, Appl. Math. Lett., 16, 297-302 (2003) · Zbl 1041.05048 |
| [16] | Duval, A., A directed version of strongly regular graphs, J. Combin. Theory Ser. A, 47, 71-100 (1988) · Zbl 0642.05025 |
| [17] | Feng, R. Q.; Kwak, J. H., Some results on covers of complete graphs, Chinese Sci. Bull., 45, 796-798 (2000) · Zbl 1041.05059 |
| [18] | Fiol, M. A.; Garriga, E., On the algebraic theory of pseudo-distance-regularity around a set, Linear Algebra Appl., 298, 115-141 (1999) · Zbl 0984.05060 |
| [19] | Gimbert, J., On digraphs with unique walks of closed length between vertices, Australas. J. Combin., 20, 77-90 (1999) · Zbl 0935.05050 |
| [20] | Gimbert, J.; Wu, Y., The underlying line digraph structure of some (0,1) matrix equations, Discrete Appl. Math., 116, 289-296 (2002) · Zbl 0995.05097 |
| [21] | Grüneward, S., Harmonic trees, Appl. Math. Lett., 15, 1001-1004 (2002) · Zbl 1009.05041 |
| [22] | Hemminger, R. L.; Beineke, L. W., Line graphs and line digraphs, (Lowell, W. B.; Wilson, R. J., Selected Topics in Graph Theory (1978), Academic Press: Academic Press New York), 271-305 · Zbl 0434.05056 |
| [23] | Ho, C. F., Some 0, 1 solutions to matrix equations \(A^m\)−\(A^n= lJ \)—Part I, SIAM J. Matrix Anal. Appl., 11, 200-206 (1990) · Zbl 0733.05059 |
| [24] | S.A. Hobart, A.E. Brouwer, A table of parameters of directed strongly regular graphs. Available from: <; S.A. Hobart, A.E. Brouwer, A table of parameters of directed strongly regular graphs. Available from: < · Zbl 1110.05320 |
| [25] | Hoffman, A. J., On the polynomial of a graph, Amer. Math. Monthly, 70, 30-36 (1963) · Zbl 0112.14901 |
| [26] | Hoffman, A. J., On the line graph of a projective plane, Proc. Amer. Math. Soc., 16, 297-302 (1965) · Zbl 0133.16802 |
| [27] | Hoffman, A. J.; McAndrew, M. H., The polynomial of a directed graph, Proc. Amer. Math. Soc., 16, 303-309 (1965) · Zbl 0129.40102 |
| [28] | Hou, Y.; Tian, F., A note on Hoffman-type identities of graphs, Linear Algebra Appl., 402, 143-149 (2005) · Zbl 1063.05092 |
| [29] | Jørgensen, L. K., Non-existence of directed strongly regular graphs, Disc. Math., 264, 111-126 (2003) · Zbl 1014.05074 |
| [30] | L.K. Jørgensen, Directed strongly regular graphs. Available from: <http://www.math.aau.dk/ leif/ research/dsrg-table.html>; L.K. Jørgensen, Directed strongly regular graphs. Available from: <http://www.math.aau.dk/ leif/ research/dsrg-table.html> |
| [31] | Kitchens, B. P., Symbolic Dynamics: One-sided, Two-Sided and Countable State Markov Shifts (1998), Springer · Zbl 0892.58020 |
| [32] | Lauri, J.; Scapellato, R., Topics in Graph Automorphisms and Reconstruction (2003), Cambridge University Press · Zbl 1038.05025 |
| [33] | Lam, C. W.H.; van Lint, J. H., Directed graphs with unique paths of fixed length, J. Combin. Theory Ser. B, 24, 331-337 (1978) · Zbl 0319.05112 |
| [34] | Lazarus, A. J., Eigenvectors of circulant matrices of prime dimension, Linear Algebra Appl., 221, 111-116 (1995) · Zbl 0827.15004 |
| [35] | Lind, D.; Marcus, B., An Introduction to Symbolic Dynamics and Coding (1995), Cambridge University Press · Zbl 1106.37301 |
| [36] | van Lint, J. H.; Wilson, R. M., A Course in Combinatorics (2001), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0980.05001 |
| [37] | Marcus, M.; Robinson, H., Elementary divisors of tensor products, Commun. ACM, 18, 36-39 (1975) · Zbl 0297.15025 |
| [38] | Muzychuk, M.; Klin, M., On graphs with three eigenvalues, Disc. Math., 198, 191-207 (1998) · Zbl 0956.05071 |
| [39] | Plesník, J.; Znám, S., Strongly geodetic directed graphs, Acta F. R. N. Univ. Comen-Mathe, 29, 29-34 (1975) · Zbl 0291.05106 |
| [40] | Teranishi, Y., The Hoffman number of a graph, Disc. Math., 260, 255-265 (2003) · Zbl 1012.05111 |
| [41] | X. Wang, A. Deng, Q. Li, Hoffman polynomials and spectra of some generalized cycles, J. Shanghai Jiaotong Univ. (in Chinese), in press.; X. Wang, A. Deng, Q. Li, Hoffman polynomials and spectra of some generalized cycles, J. Shanghai Jiaotong Univ. (in Chinese), in press. · Zbl 1174.05409 |
| [42] | West, D. B., Introduction to Graph Theory (2001), Prentice Hall |
| [43] | Wu, Y.; Li, Q., On the matrix equation \(A^k+A^{k\)+ℓ · Zbl 0933.15023 |
| [44] | Wu, Y.; Li, Q.; Li, J., Spectra and elementary cycles of the digraphs with unique paths of fixed length, Linear Algebra Appl., 293, 145-158 (1999) · Zbl 0956.05069 |
| [45] | Wu, Y.; Li, Q.; Huang, X., On the matrix equation \(A^k=J−\(I\), Linear Algebra Appl., 295, 249-260 (1999) · Zbl 0938.15008 |
| [46] | Wu, Y.; Li, Q., Some characterizations for the wrapped butterfly, (He, T. X.; Shiue, P. J.S.; Li, Z., Analysis, Combinatorics and Computing, Proceedings of the International Symposium on Analysis, Combinatorics and Computing, August 5-8, 2000, Dalian, PR China (2003), Nova Science Publishers, Inc.), 419-433, Available from: · Zbl 1081.05514 |
| [47] | Wu, Y.; Jia, R.; Li, Q., g-Circulant solutions to the (0,1) matrix equation \(A^m=J_{n\) · Zbl 0998.15015 |
| [48] | Wu, Y.; Li, Q., An approach to solving \(A^k=J−\(I\), Linear Algebra Appl., 373, 121-142 (2003) · Zbl 1032.15011 |
| [49] | Y. Wu, X. Wang, Strong homomorphisms between digraphs, in: Proceedings of the Workshop on Discrete Models for Complex Systems, Turku Center for Computer Science, Turku, Finland, July 2004, pp. 101-113.; Y. Wu, X. Wang, Strong homomorphisms between digraphs, in: Proceedings of the Workshop on Discrete Models for Complex Systems, Turku Center for Computer Science, Turku, Finland, July 2004, pp. 101-113. |
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.
