On the Spectral Characterization of *H*-Shape Trees

ABSTRACT

A graph *G* is said to be determined by its spectrum if any graph having the same spectrum as *G* is isomorphic to *G*. An *H*-shape is a tree with exactly two of its vertices having maximal degree 3. In this paper, a formula of counting the number of closed 6-walks is given on a graph, and some necessary conditions of a graph Γ cospectral to an *H*-shape are given.

KEYWORDS

Spectra of Graphs, Cospectral Graphs, Spectra Radius,*H*-Shape Trees,
Determined by Its Spectrum

Spectra of Graphs, Cospectral Graphs, Spectra Radius,

Cite this paper

Hu, S. (2014) On the Spectral Characterization of*H*-Shape Trees. *Advances in Linear Algebra & Matrix Theory*, **4**, 79-86. doi: 10.4236/alamt.2014.42005.

Hu, S. (2014) On the Spectral Characterization of

References

[1] Cvetkovi'c, D., Doob, M. and Sachs, H. (1980) Spectra of Graphs—Theory and Application. Academic Press, New York.

[2] van Dam, E.R. and Haemers, W.H. (2003) Which Graph Are Determined by Their Spectrum? Linear Algebra and Its Applications, 373, 241-272. http://dx.doi.org/10.1016/S0024-3795(03)00483-X

[3] Doob, M. and Haemers, W.H. (2002) The Complement of the Path Is Determined by Its Spectrum. Linear Algebra and Its Applications, 356, 57-65.

http://dx.doi.org/10.1016/S0024-3795(02)00323-3

[4] Noy, M. (2003) Graphs Determined by Polynomial Invariants. Theoretical Computer Science, 307, 365-384.

[5] Smith, J.H. (1970) Some Propertice of the Spectrum of Graph. In: Guy, R., et al., Eds., Combinatorial Structure and Their Applications, Gordon and Breach, New York, 403-406.

[6] Wang, W. and Xu, C.-X. (2006) On the Spactral Characterization of T-Shape Trees. Linear Algebra and Its Applications, 414, 492-501.

http://dx.doi.org/10.1016/j.laa.2005.10.031

[7] Schwenk, A.J. (1973) Almost All Trees Are Cospectral. In: Harary, F., Ed., New Directions in the Theory of Graphs, Academic Press, New York, 275-307.

[8] Godsil, C.D. (1993) Algebraic Combinatorics. Chapman & Hall, New York.

[9] Sachs, H. (1964) Beziehungen zwischen den in einem graphen enthaltenen kreisenund seinem charakteristischen polynom. Publicationes Mathematicae, 11, 119-134.

[10] Omidi, G.R. and Tajbakhsh, K. (2007) Starlike Trees Are Determined by Their Laplacian Spectrum. Linear Algebra and Its Applications, 422, 654-658.

http://dx.doi.org/10.1016/j.laa.2006.11.028

[1] Cvetkovi'c, D., Doob, M. and Sachs, H. (1980) Spectra of Graphs—Theory and Application. Academic Press, New York.

[2] van Dam, E.R. and Haemers, W.H. (2003) Which Graph Are Determined by Their Spectrum? Linear Algebra and Its Applications, 373, 241-272. http://dx.doi.org/10.1016/S0024-3795(03)00483-X

[3] Doob, M. and Haemers, W.H. (2002) The Complement of the Path Is Determined by Its Spectrum. Linear Algebra and Its Applications, 356, 57-65.

http://dx.doi.org/10.1016/S0024-3795(02)00323-3

[4] Noy, M. (2003) Graphs Determined by Polynomial Invariants. Theoretical Computer Science, 307, 365-384.

[5] Smith, J.H. (1970) Some Propertice of the Spectrum of Graph. In: Guy, R., et al., Eds., Combinatorial Structure and Their Applications, Gordon and Breach, New York, 403-406.

[6] Wang, W. and Xu, C.-X. (2006) On the Spactral Characterization of T-Shape Trees. Linear Algebra and Its Applications, 414, 492-501.

http://dx.doi.org/10.1016/j.laa.2005.10.031

[7] Schwenk, A.J. (1973) Almost All Trees Are Cospectral. In: Harary, F., Ed., New Directions in the Theory of Graphs, Academic Press, New York, 275-307.

[8] Godsil, C.D. (1993) Algebraic Combinatorics. Chapman & Hall, New York.

[9] Sachs, H. (1964) Beziehungen zwischen den in einem graphen enthaltenen kreisenund seinem charakteristischen polynom. Publicationes Mathematicae, 11, 119-134.

[10] Omidi, G.R. and Tajbakhsh, K. (2007) Starlike Trees Are Determined by Their Laplacian Spectrum. Linear Algebra and Its Applications, 422, 654-658.

http://dx.doi.org/10.1016/j.laa.2006.11.028