DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

Y.-Z. Fan

Yi-Zheng Fan

School of Mathematical Sciences, Anhui University, Hefei 230601, P.R.CHINA

email: fanyz@ahu.edu.cn

0000-0003-2664-8625

H.-X. Yang

Hong-Xia Yang

School of Mathematical Sciences, Anhui University, Hefei 230601, P.R.China

email: yanghx@stu.ahu.edu.cn

J. Zheng

Jian Zheng

School of Mathematical Sciences, Anhui Univeristy, Hefei 230601, P.R. China

email: zhengj@stu.ahu.edu.cn

Title:

High-ordered spectral characterization of unicyclic graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 44(3) (2024) 1107-1141

Received: 2022-09-29 , Revised: 2023-02-07 , Accepted: 2023-02-07 , Available online: 2023-03-04 , https://doi.org/10.7151/dmgt.2489

Abstract:

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

References:

  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 $K_{r+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
Close