×

On the spectral characterization of the \(p\)-sun and the \((p, Q)\)-double sun. (English) Zbl 1480.05084

Summary: A. J. Schwenk [in: New directions in the theory of graphs. Proceedings of the third Ann Arbor conference on graph theory, held at the University of Michigan, October 21–23, 1971. New York-London: Academic Press. 275–307 (1973; Zbl 0261.05102)] proved that almost every tree has a cospectral mate. Inspired by Schwenk’s result [loc. cit.], in this paper we study the spectrum of two families of trees. The \(p\)-sun of order \(2 p + 1\) is a star \(K_{1 , p}\) with an edge attached to each pendant vertex, which we show to be determined by its spectrum among connected graphs. The \((p, q)\)-double sun of order \(2(p + q + 1)\) is the union of a \(p\)-sun and a \(q\)-sun by adding an edge between their central vertices. We determine when the \((p, q)\)-double sun has a cospectral mate and when it is determined by its spectrum among connected graphs. Our method is based on the fact that these trees have few distinct eigenvalues and we are able to take advantage of their nullity to shorten the list of candidates.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
15A03 Vector spaces, linear dependence, rank, lineability

Citations:

Zbl 0261.05102
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gong, S.-C.; Fan, Y.-Z.; Yin, Z.-X., On the nullity of graphs with pendant trees, Linear Algebra Appl., 433, 7, 1374-1380 (2010) · Zbl 1194.05086
[2] Günthard, H. H.; Primas, H., Zusammenhang von graphentheorie und mo-theorie von molekeln mit systemen konjugierter bindungen, Helv. Chim. Acta, 39, 6, 1645-1653 (1956)
[3] Gutman, I.; Furtula, B.; Bozkurt, Ş. B., On Randić energy, Linear Algebra Appl., 442, 50-57 (2014) · Zbl 1282.05118
[4] Jacobs, D. P.; Machado, C. M.; Trevisan, V., An \(\operatorname{O}( \operatorname{n}^2)\) algorithm for the characteristic polynomial of a tree, J. Comb. Math. Comb. Comput., 54, 213 (2005) · Zbl 1080.05089
[5] Lepović, M.; Gutman, I., No starlike trees are cospectral, Discrete Math., 242, 1-3, 291-295 (2002) · Zbl 0992.05054
[6] Omidi, G.; Tajbakhsh, K., Starlike trees are determined by their Laplacian spectrum, Linear Algebra Appl., 422, 2-3, 654-658 (2007) · Zbl 1114.05064
[7] Schwenk, A. J., Almost all trees are cospectral, (New Directions in the Theory of Graphs (1973)), 275-307 · Zbl 0261.05102
[8] Trevisan, V.; Carvalho, J. B.; Del Vecchio, R. R.; Vinagre, C. T., Laplacian energy of diameter 3 trees, Appl. Math. Lett., 24, 6, 918-923 (2011) · Zbl 1216.05010
[9] Van Dam, E. R.; Haemers, W. H., Which graphs are determined by their spectrum?, Linear Algebra Appl., 373, 241-272 (2003) · Zbl 1026.05079
[10] Von Collatz, L.; Sinogowitz, U., Spektren endlicher grafen, (Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, vol. 21 (1957), Springer), 63-77 · Zbl 0077.36704
[11] Wang, W.; Xu, C.-X., On the spectral characterization of t-shape trees, Linear Algebra Appl., 414, 2-3, 492-501 (2006) · Zbl 1086.05050
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.