Homomorphisms, representations and characteristic polynomials of digraphs. (English) Zbl 1117.05079
Summary: The existence of a homomorphism between two digraphs often implies many structural properties. We collect in this paper some characterizations of various digraph homomorphisms using matrix equations and fiber partitions. We also survey the relationship among the characteristic polynomials of a digraph and its divisors. This includes an introduction of the concept of branched coverings of digraphs, their voltage assignment representations, and a decomposition formula for the characteristic polynomial of a branched cover with branch index 1. Some open problems are included.
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05E99 | Algebraic combinatorics |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 05C20 | Directed graphs (digraphs), tournaments |
References:
| [1] | Adler, R. L.; Marcus, B., Topological entropy and equivalence of dynamical systems, Mem. Amer. Math. Soc., 219 iv+84 (1979) · Zbl 0412.54050 |
| [2] | Biggs, N., Algebraic Graph Theory (1993), Cambridge University Press: Cambridge University Press London |
| [3] | Boldi, P.; Vigna, S., Fibrations of graphs, Discrete Math., 243, 21-66 (2002) · Zbl 0988.05073 |
| [4] | Chae, Y.; Kwak, J. H.; Lee, J., Characteristic polynomials of some graph bundles, J. Korean Math. Soc., 30, 229-249 (1993) · Zbl 0782.05058 |
| [5] | Chan, A.; Godsil, C. D., Symmetry and eigenvectors, (Hahn, G.; Sabidussi, G., Graph Symmetry—Algebraic Methods and Applications (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 75-106 · Zbl 0883.05097 |
| [6] | Cvetković, D., The main part of the spectrum, divisors and switching of graphs, Publ. Inst. Math. (Beograd), 23, 31-38 (1978) · Zbl 0423.05028 |
| [7] | Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs: Theory and Applications (1995), Johann Ambrosius Barth Verlag: Johann Ambrosius Barth Verlag Heidelberg-Leipzig · Zbl 0824.05046 |
| [8] | Cvetković, D.; Rowlinson, P.; Simić, S., Eigenspaces of Graphs (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0878.05057 |
| [9] | Deng, A.; Wu, Y., Characteristic polynomials of digraphs having a semi-free action, Linear Algebra Appl., 408, 189-206 (2005) · Zbl 1074.05042 |
| [10] | Deng, A.; Sato, I.; Wu, Y., Characteristic polynomials of ramified uniform covering digraphs, Eur. J. Combin. (2006) |
| [11] | Dress, A.; Stevanović, D., A note on a theorem of Horst Sachs, Ann. Comb., 8, 487-497 (2004) · Zbl 1064.05099 |
| [12] | Feng, R.; Kwak, J. H.; Lee, J., Characteristic polynomials of graph coverings, Bull. Austral. Math. Soc., 69, 133-136 (2004) · Zbl 1043.05075 |
| [13] | Godsil, C.; Royle, G., Algebraic Graph Theory (2001), Springer-Verlag: Springer-Verlag New York · Zbl 0968.05002 |
| [14] | Gross, J. L.; Tucker, T. W., Generating all graph coverings by permutation voltage assignments, Discrete Math., 18, 273-283 (1977) · Zbl 0375.55001 |
| [15] | Gross, J. L.; Tucker, T. W., Topological Graph Theory (1987), Wiley-Interscience: Wiley-Interscience New York · Zbl 0621.05013 |
| [16] | Híc, P.; Nedela, R.; Pavlíková, S., Front divisors of trees, Acta Math. Univ. Comenianae, 1, 69-84 (1992) · Zbl 0821.05041 |
| [17] | James, G.; Liebeck, M., Representations and Characters of Groups (2001), Cambridge University Press · Zbl 0981.20004 |
| [18] | Kitchens, B. P., Symbolic Dynamics: One-sided, Two-Sided and Countable State Markov Shifts (1998), Springer · Zbl 0892.58020 |
| [19] | Knuth, D. E., Partitioned tensor products and their spectra, J. Algebraic Combin., 6, 259-267 (1997) · Zbl 0882.05090 |
| [20] | Kwak, J. H.; Lee, J., Characteristic polynomials of some graph bundles II, Linear and Multilinear Algebra, 32, 61-73 (1992) · Zbl 0755.05078 |
| [21] | Lee, J.; Kim, H. K., Characteristic polynomials of graphs having a semi-free action, Linear Algebra Appl., 307, 35-46 (2000) · Zbl 0991.05072 |
| [22] | Lind, D.; Marcus, B., An Introduction to Symbolic Dynamics and Coding (1995), Cambridge University Press · Zbl 1106.37301 |
| [23] | Mizuno, H.; Sato, I., Characteristic polynomials of some graph coverings, Discrete Math., 142, 295-298 (1995) · Zbl 0835.05044 |
| [24] | Mizuno, H.; Sato, I., Characteristic polynomials of some covers of symmetric digraphs, Ars Combin., 45, 3-12 (1997) · Zbl 0933.05120 |
| [25] | Nasu, M., Constant-to-one and onto global maps of homomorphisms between strongly connected graphs, Ergodic Theory Dynam. Syst., 3, 387-413 (1983) · Zbl 0544.05029 |
| [26] | Neumann, P. M., A lemma that is not Burnside’s, Math. Scientist, 4, 133-141 (1979) · Zbl 0409.20001 |
| [27] | Schwenk, A. J., Computing the characteristic polynomial of a graph, Lect. Notes Math., 406, 153-172 (1974) · Zbl 0308.05121 |
| [28] | Sachs, H., Simultane Überlangerung gegebener Graphen, Magyar Tud. Akad. Mat. Kutató Int. Közl., 9, 415-427 (1965) · Zbl 0134.43401 |
| [29] | Serre, J. P., Linear Representations of Finite Group (1977), Springer-Verlag: Springer-Verlag New York · Zbl 0355.20006 |
| [30] | Williams, R. F., Classification of subshifts of finite type, Ann. Math., 98, 120-153 (1973), errata, ibid. 99 (1974) 380-381 · Zbl 0282.58008 |
| [31] | Wu, Y.; Deng, A., Hoffman polynomials of irreducible matrices and digraphs, Linear Algebra Appl., 414, 138-171 (2006) · Zbl 1083.05030 |
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.
