Geodesic
High-ordered spectral characterization of unicyclic graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1107-1141 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

In this paper we will apply the tensor and its traces to investigate the spectral characterization of unicyclic graphs. Let G be a graph and G^m be the m-th power (hypergraph) of G. The spectrum of G is referring to its adjacency matrix, and the spectrum of G^m is referring to its adjacency tensor. The graph G is called determined by high-ordered spectra (DHS, for short) if, whenever H is a graph such that H^m is cospectral with G^m for all m, then H is isomorphic to G. In this paper we first give formulas for the traces of the power of unicyclic graphs, and then provide some high-ordered cospectral invariants of unicyclic graphs. We prove that a class of unicyclic graphs with cospectral mates is DHS, and give two examples of infinitely many pairs of cospectral unicyclic graphs but with different high-ordered spectra.
Keywords: unicyclic graph, graph isomorphism, cospectral graphs, power hypergraph, adjacency tensor, trace 
@article{DMGT_2024_44_3_a15,
     author = {Fan, Yi-Zheng and Yang, Hong-Xia and Zheng, Jian},
     title = {High-ordered spectral characterization of unicyclic graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1107--1141},
     year = {2024},
     volume = {44},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a15/}
}
TY  - JOUR
AU  - Fan, Yi-Zheng
AU  - Yang, Hong-Xia
AU  - Zheng, Jian
TI  - High-ordered spectral characterization of unicyclic graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1107
EP  - 1141
VL  - 44
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a15/
LA  - en
ID  - DMGT_2024_44_3_a15
ER  - 
%0 Journal Article
%A Fan, Yi-Zheng
%A Yang, Hong-Xia
%A Zheng, Jian
%T High-ordered spectral characterization of unicyclic graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1107-1141
%V 44
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a15/
%G en
%F DMGT_2024_44_3_a15
Fan, Yi-Zheng; Yang, Hong-Xia; Zheng, Jian. High-ordered spectral characterization of unicyclic graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1107-1141. http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a15/

[1] T. van Aardenne-Ehrenfest and N.G. de Bruijn, Circuits and trees in oriented linear graphs, in: Classic Papers in Combinatorics, I. Gessel and G.C. Rota (Ed(s)), (Boston, Birkhäuser Boston 1987) 149–163.

[2] S. Bai and L. Lu, A bound on the spectral radius of hypergraphs with e edges, Linear Algebra Appl. 549 (2018) 203–218. https://doi.org/10.1016/j.laa.2018.03.030

[3] K. Cardoso, C. Hoppen and V. Trevisan, The spectrum of a class of uniform hypergraphs, Linear Algebra Appl. 590 (2020) 243–257. https://doi.org/10.1016/j.laa.2019.12.042

[4] K.C. Chang, K. Pearson and T. Zhang, Perron-Frobenius theorem for nonnegative tensors, Commun. Math. Sci. 6 (2008) 507–520. https://doi.org/10.4310/CMS.2008.v6.n2.a12

[5] L. Chen, C. Bu and J. Zhou, Spectral moments of hypertrees and their applications, Linear Multilinear Algebra(2021), in press. https://doi.org/10.1080/03081087.2021.1953431

[6] L. Chen, E.R. van Dam and C. Bu, All eigenvalues of the power hypergraph and signed subgraphs of a graph (2022, a manuscript). arXiv: 2209.03709

[7] L. Chen, L. Sun and C. Bu, High-ordered spectral characterizations of graphs (2021, a manuscript). arXiv: 2111.03877

[8] G.J. Clark and J.N. Cooper, A Harary-Sachs theorem for hypergraphs, J. Combin. Theory Ser. B 149 (2021) 1–15. https://doi.org/10.1016/j.jctb.2021.01.002

[9] J.N. Cooper and A. Dutle, Spectra of uniform hypergraphs, Linear Algebra Appl. 436 (2012) 3268–3292. https://doi.org/10.1016/j.laa.2011.11.018

[10] L. von Collatz and U. Sinogowitz, Spektren endlicher Grafen, Abh. Math. Semin. Univ. Hambg. 21 (1957) 63–77. https://doi.org/10.1007/BF02941924

[11] D. Cvetković and P. Rowlinson, Spectra of unicyclic graphs, Graphs Combin. 3 (1987) 7–23. https://doi.org/10.1007/BF01788525

[12] E.R. van Dam and W.H. Haemers, Which graphs are determined by their spectrum?, Linear Algebra Appl. 373 (2003) 241–272. https://doi.org/10.1016/S0024-3795(03)00483-X

[13] E.R. van Dam and W.H. Haemers, Developments on spectral characterizations of graphs, Discrete Math. 309 (2009) 576–586. https://doi.org/10.1016/j.disc.2008.08.019

[14] Y.-Z. Fan, Y.-H. Bao and T. Huang, Eigenvariety of nonnegative symmetric weakly irreducible tensors associated with spectral radius and its application to hypergraphs, Linear Algebra Appl. 564 (2019) 72–94. https://doi.org/10.1016/j.laa.2018.11.027

[15] Y.-Z. Fan, T. Huang and Y.-H. Bao, The dimension of eigenvariety of nonnegative tensors associated with spectral radius, Proc. Amer. Math. Soc. 150 (2022) 2287–2299. https://doi.org/10.1090/proc/15781

[16] Y.-Z. Fan, T. Huang, Y.-H. Bao, C. L. Zhuan-Sun and Y.-P. Li, The spectral symmetry of weakly irreducible nonnegative tensors and connected hypergraphs, Trans. Amer. Math. Soc. 372 (2019) 2213–2233. https://doi.org/10.1090/tran/7741

[17] Y.-Z. Fan, M. Li and Y. Wang, The cyclic index of adjacency tensor of generalized power hypergraphs, Discrete Math. 344(5) (2021) 112329. https://doi.org/10.1016/j.disc.2021.112329

[18] Y.-Z. Fan, Y.-Y. Tan, X.-X. Peng and A.-H. Liu, Maximizing spectral radii of uniform hypergraphs with few edges, Discuss. Math. Graph Theory 36 (2016) 845–856. https://doi.org/10.7151/dmgt.1906

[19] Y.-Z. Fan, M.-Y. Tian and M. Li, The stabilizing index and cyclic index of the coalescence and Cartesian product of uniform hypergraphs, J. Combin. Theory Ser. A 185 (2022) 105537. https://doi.org/10.1016/j.jcta.2021.105537

[20] Y.-Z. Fan, Y. Yang, C.-M. She, J. Zheng, Y.-M. Song and H.-X. Yang, The trace and Estrada index of uniform hypergraphs with cut vertices, Linear Algebra Appl. 660 (2023) 89–117. https://doi.org/10.1016/j.laa.2022.12.006

[21] S. Friedland, S. Gaubert and L. Han, Perron-Frobenius theorem for nonnegative multilinear forms and extensions, Linear Algebra Appl. 438 (2013) 738–749. https://doi.org/10.1016/j.laa.2011.02.042

[22] G. Gao, A. Chang and Y. Hou, Spectral radius on linear r-graphs without expanded Kr+1, SIAM J. Discrete. Math. 36 (2022) 1000–1011. https://doi.org/10.1137/21M1404740

[23] C.D. Godsil and B.D. McKay, A new graph product and its spectrum, Bull. Aust. Math. Soc. 18 (1978) 21–28. https://doi.org/10.1017/S0004972700007760

[24] C.D. Godsil and B.D. McKay, Constructing cospectral graphs, Aequationes Math. 25 (1982) 257–268. https://doi.org/10.1007/BF02189621

[25] Hs.H. Günthard and H. Primas, Zusammenhang von Graphentheorie und MO-Theorie von Molekeln mit Systemen konjugierter Bindungen, Helv. Chim. Acta 39 (1956) 1645–1653. https://doi.org/10.1002/hlca.19560390623

[26] S. Hu, L. Qi and J. Shao, Cored hypergraphs, power hypergraphs and their Laplacian eigenvalues, Linear Algebra Appl. 439 (2013) 2980–2998. https://doi.org/10.1016/j.laa.2013.08.028

[27] P. Keevash, J. Lenz and D. Mubayi, Spectral extremal problems for hypergraphs, SIAM J. Discrete Math. 28 (2014) 1838–1854. https://doi.org/10.1137/130929370

[28] L.-H. Lim, Singular values and eigenvalues of tensors: a variational approach, in: Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adapative Processing (CAMSAP'05), (New Jersey 2005) 129–132.

[29] M. Lepović, Some results on starlike trees and sunlike graphs, J. Appl. Math. Comput. 11 (2003) 109–122. https://doi.org/10.1007/BF02935725

[30] H. Li, J.-Y. Shao and L. Qi, The extremal spectral radii of k-uniform supertrees, J. Comb. Optim. 32 (2016) 741–764. https://doi.org/10.1007/s10878-015-9896-4

[31] L. Liu, L. Kang and E. Shan, On the irregularity of uniform hypergraphs, European J. Comb. 71 (2018) 22–32. https://doi.org/10.1016/j.ejc.2018.02.034

[32] X. Liu, S. Wang, Y. Zhang and X. Yong, On the spectral characterization of some unicyclic graphs, Discrete Math. 311 (2011) 2317–2336. https://doi.org/10.1016/j.disc.2011.05.034

[33] L. Lu and S. Man, Connected hypergraphs with small spectral radius, Linear Algebra Appl. 509 (2016) 206–227. https://doi.org/10.1016/j.laa.2016.07.013

[34] A. Morozov and Sh. Shakirov, Analogue of the identity Log Det = Trace Log for resultants, J. Geom. Phys. 61 (2011) 708–726. https://doi.org/10.1016/j.geomphys.2010.12.001

[35] L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput. 40 (2005) 1302–1324. https://doi.org/10.1016/j.jsc.2005.05.007

[36] A.J. Schwenk, Almost all trees are cospectral, in: New Directions in the Theory of Graphs, F. Harary (Ed(s)), (New York: Academic Press 1973) 275–307.

[37] J.-Y. Shao, L. Qi and S. Hu, Some new trace formulas of tensors with applications in spectral hypergraph theory, Linear Multilinear Algebra 63 (2015) 971–992. https://doi.org/10.1080/03081087.2014.910208

[38] W.T. Tutte and C.A.B. Smith, On unicursal paths in a network of degree 4, Amer. Math. Monthly 48 (1941) 233–237. https://doi.org/10.1080/00029890.1941.11991103

[39] W. Wang, A simple arithmetic criterion for graphs being determined by their generalized spectra, J. Combin. Theory Ser. B 122 (2017) 438–451. https://doi.org/10.1016/j.jctb.2016.07.004

[40] W. Wang and C.-X. Xu, A sufficient condition for a family of graphs being determined by their generalized spectra, European J. Combin. 27 (2006) 826–840. https://doi.org/10.1016/j.ejc.2005.05.004

[41] W. Wang and C.-X. Xu, An excluding algorithm for testing whether a family of graphs are determined by their generalized spectra, Linear Algebra Appl. 418 (2006) 62–74. https://doi.org/10.1016/j.laa.2006.01.016

[42] Y. Yang and Q. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors, SIAM J. Matrix Anal. Appl. 31 (2010) 2517–2530. https://doi.org/10.1137/090778766

[43] Q. Yang and Y. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors II}, SIAM J. Matrix Anal. Appl. 32 (2011) 1236–1250. https://doi.org/10.1137/100813671

[44] Y. Yang and Q. Yang, On some properties of nonnegative weakly irreducible tensors (2011, a manuscript). arXiv: 1111.0713v2

[45] W. Zhang, L. Kang, E. Shan and Y. Bai, The spectra of uniform hypertrees, Linear Algebra Appl. 533 (2017) 84–94. https://doi.org/10.1016/j.laa.2017.07.018

[46] J. Zhou, L. Sun, W. Wang and C. Bu, Some spectral properties of uniform hypergraphs, Electron. J. Combin. 21(4) (2014) #P4.24. https://doi.org/10.37236/4430