Distinguishing graphs with zeta functions and generalized spectra. (English) Zbl 1315.05085
Summary: Conjecturally, almost all graphs are determined by their spectra. This problem has also been studied for variants such as the spectra of the Laplacian and signless Laplacian. Here we consider the problem of determining graphs with Ihara and Bartholdi zeta functions, which are also computable in polynomial time. These zeta functions are geometrically motivated, but can be viewed as certain generalizations of characteristic polynomials. After discussing some graph properties determined by zeta functions, we show that large classes of cospectral graphs can be distinguished with zeta functions and enumerate graphs distinguished by zeta functions on \(\leq11\) vertices. This leads us to conjecture that almost all graphs which are not determined by their spectrum are determined by zeta functions.
Along the way, we make some observations about the usual types of spectra and disprove a conjecture of A. Setyadi and C. K. Storm [ibid. 438, No. 1, 564–572 (2013; Zbl 1257.05064)] about Ihara zeta functions determining degree sequences.
Along the way, we make some observations about the usual types of spectra and disprove a conjecture of A. Setyadi and C. K. Storm [ibid. 438, No. 1, 564–572 (2013; Zbl 1257.05064)] about Ihara zeta functions determining degree sequences.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C30 | Enumeration in graph theory |
| 11M41 | Other Dirichlet series and zeta functions |
Citations:
Zbl 1257.05064References:
| [1] | Bartholdi, Laurent, Counting paths in graphs, Enseign. Math. (2), 45, 1-2, 83-131 (1999) · Zbl 0961.05032 |
| [2] | Bass, Hyman, The Ihara-Selberg zeta function of a tree lattice, Internat. J. Math., 3, 6, 717-797 (1992) · Zbl 0767.11025 |
| [3] | Bayati, Paymun; Somodi, Marius, On the Ihara zeta function of cones over regular graphs, Graphs Combin., 29, 6, 1633-1646 (2013) · Zbl 1282.05093 |
| [4] | Brouwer, Andries E.; Haemers, Willem H., Spectra of Graphs, Universitext (2012), Springer: Springer New York · Zbl 1231.05001 |
| [5] | Brouwer, A. E.; Spence, E., Cospectral graphs on 12 vertices, Electron. J. Combin., 16, 1 (2009), Note 20, 3 pp · Zbl 1185.05097 |
| [6] | Buser, Peter, Geometry and Spectra of Compact Riemann Surfaces, Mod. Birkhäuser Class. (2010), Birkhäuser Boston, Inc.: Birkhäuser Boston, Inc. Boston, MA, Reprint of the 1992 edition · Zbl 1239.32001 |
| [7] | Cvetković, Dragoš; Rowlinson, Peter; Simić, Slobodan, An Introduction to the Theory of Graph Spectra, London Math. Soc. Stud. Texts, vol. 75 (2010), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1211.05002 |
| [8] | Cooper, Yaim, Properties determined by the Ihara zeta function of a graph, Electron. J. Combin., 16, 1 (2009), Research Paper 84, 14 pp · Zbl 1230.05199 |
| [9] | Czarneski, Debra, Zeta functions of finite graphs (2005), Louisiana State University and Agricultural & Mechanical College, ProQuest LLC, Ann Arbor, MI |
| [10] | Godsil, C. D.; McKay, B. D., Constructing cospectral graphs, Aequationes Math., 25, 2-3, 257-268 (1982) · Zbl 0527.05051 |
| [11] | Haemers, Willem H.; Spence, Edward, Enumeration of cospectral graphs, European J. Combin., 25, 2, 199-211 (2004) · Zbl 1033.05070 |
| [12] | Hashimoto, Ki-ichiro, Zeta functions of finite graphs and representations of \(p\)-adic groups, (Automorphic Forms and Geometry of Arithmetic Varieties. Automorphic Forms and Geometry of Arithmetic Varieties, Adv. Stud. Pure Math., vol. 15 (1989), Academic Press: Academic Press Boston, MA), 211-280 · Zbl 0709.22005 |
| [13] | Hashimoto, Ki-ichiro, On zeta and \(L\)-functions of finite graphs, Internat. J. Math., 1, 4, 381-396 (1990) · Zbl 0734.14008 |
| [14] | Hashimoto, Ki-ichiro, Artin type \(L\)-functions and the density theorem for prime cycles on finite graphs, Internat. J. Math., 3, 6, 809-826 (1992) · Zbl 0767.11026 |
| [15] | Ihara, Yasutaka, On discrete subgroups of the two by two projective linear group over \(p\)-adic fields, J. Math. Soc. Japan, 18, 219-235 (1966) · Zbl 0158.27702 |
| [16] | Johnson, Charles R.; Newman, Morris, A note on cospectral graphs, J. Combin. Theory Ser. B, 28, 1, 96-103 (1980) · Zbl 0431.05021 |
| [17] | Kim, Hye Kyung; Lee, Jaeun, A generalized characteristic polynomial of a graph having a semifree action, Discrete Math., 308, 4, 555-564 (2008) · Zbl 1130.05036 |
| [18] | McKay, Brendan D.; Piperno, Adolfo, Practical graph isomorphism, II, J. Symbolic Comput., 60, 94-112 (2014) · Zbl 1394.05079 |
| [19] | Stein, W. A., Sage Mathematics Software (Version 6.1.1), The Sage Development Team (2014) |
| [20] | Schwenk, Allen J., Almost all trees are cospectral, (New Directions in the Theory of Graphs, Proc. Third Ann Arbor Conf., Univ. Michigan. New Directions in the Theory of Graphs, Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, MI, 1971 (1973), Academic Press: Academic Press New York), 275-307 · Zbl 0261.05102 |
| [21] | Scott, Geoffrey; Storm, Christopher, The coefficients of the Ihara zeta function, Involve, 1, 2, 217-233 (2008) · Zbl 1228.05202 |
| [22] | Setyadi, A.; Storm, C. K., Enumeration of graphs with the same Ihara zeta function, Linear Algebra Appl., 438, 1, 564-572 (2013) · Zbl 1257.05064 |
| [23] | Spence, E. (July 15, 2014), Personal homepage |
| [24] | Stark, H. M.; Terras, A. A., Zeta functions of finite graphs and coverings, Adv. Math., 121, 1, 124-165 (1996) · Zbl 0874.11064 |
| [25] | Terras, Audrey, Zeta Functions of Graphs: A Stroll through the Garden, Cambridge Stud. Adv. Math., vol. 128 (2011), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1206.05003 |
| [26] | van Dam, Edwin R.; Haemers, Willem H., Which graphs are determined by their spectrum?, (Special Issue on the Combinatorial Matrix Theory Conference. Special Issue on the Combinatorial Matrix Theory Conference, Pohang, 2002. Special Issue on the Combinatorial Matrix Theory Conference. Special Issue on the Combinatorial Matrix Theory Conference, Pohang, 2002, Linear Algebra Appl., vol. 373 (2003)), 241-272 · Zbl 1026.05079 |
| [27] | van Dam, Edwin R.; Haemers, Willem H., Developments on spectral characterizations of graphs, Discrete Math., 309, 3, 576-586 (2009) · Zbl 1205.05156 |
| [28] | Wei, Wang, Generalized spectral characterization of graphs revisited, Electron. J. Combin., 20, 4 (2013), Paper 4, 13 pp · Zbl 1298.05214 |
| [29] | Wei, Wang; Li, Feng; Lu, Hongliang; Xu, Zongben, Graphs determined by their generalized characteristic polynomials, Linear Algebra Appl., 434, 5, 1378-1387 (2011) · Zbl 1205.05113 |
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.
