中文

Operations Research Transactions >

2017 , Vol. 21 >Issue 1: 103 - 110

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2017.01.010

Two families of trees determined by  their Laplacian spectrum

Expand
  • 1. Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China; 2. PAP Institute of Politics, Shanghai 201602, China

Received date: 2016-07-08

  Online published: 2017-03-15

Fold

Abstract

Let G be a simple connected graph. A graph G is called to be determined by its Laplacian spectrum if any graph having the same Laplacian spectrum as G is isomorphic to G. In this paper, tree Y_n and tree F(2,n,1) which have special structures are defined. It is proved that these two families of trees are determined by their Laplacian spectrum, considering the properties of the line graphs of  the cospectral graphs.

Key words： spectrum of a graph; cospectral graphs; eigenvalue; Laplacian spectrum

Cite this article

ZHANG Tao, BAI Yanqin .

Two families of trees determined by  their Laplacian spectrum
[J]. Operations Research Transactions, 2017 , 21(1) : 103 -110 . DOI: 10.15960/j.cnki.issn.1007-6093.2017.01.010

References

[1] Van Dam E R, Haemers W H. Which graphs are determined by their spectrum [J]. Linear Algebra Appl, 2003, 373: 241-272.
[2] Doob M, Haemers W H. The complement of the path is determined by its spectrum [J]. Linear Algebra Appl, 2002, 356: 57-65.
[3] Dragos M, Cvetkovic, Michael D, Horst S.   Spectra of Graphs: Theory and Applications [M].  Heidelberg;  Leipzig: Barth, 1976.
[4] Bondy J A, Murty U S R. Graph Theory with Application [M]. New York: The MacMillan Press, 1976.
[5] Oliveira C S, Deabreu N M M, Jurkiewilz S. The characteristic polynomial of the Laplacian of graphs in (a, b)-linear classes [J].  Linear Algebra Appl, 2002, 356: 113-121.
[6] Kelmans A K. The number of trees of a graph Ⅰ [J]. Automat i Telemah, 1965, 26: 2154-2204.
[7] Kelmans A K. The number of trees of a graph Ⅱ [J].  Automat i Telemah, 1966, 27: 56-65.
[8] Kelmans A K. Characteristic polynomial and the number of spanning trees of graphs and their optimization [D]. t Lectrures at the All-union Workshop on Graph Theory, Vaivary, Latviiskiy Gos Universitet, 1972.
[9] Kelmans A K , Chelnokov V M. A certain polynomial of a graph and graphs with an extremal numbers of trees [J]. Journal of Combinatorial Theory, Series B, 1974, 16: 197-214.
[10] Li J S, Zhang X D. On the Laplacian eigenvalues of a graph [J]. Linear Algebra Appl, 1998, 285: 305-307.
[11] Gutman I, Gineityte V, Lepovic M, et al. The high-energy band in the photoelectron spectrum of alkanes and its dependence on molecular structure [J]. J Serb Chem Soc, 1999, 64: 673-680.
[12] Harary F. Graph Theory [M]. Addison Wesley, 1969.
[13] 沈小玲, 侯耀平. 一些由它的 Laplacian 谱确定的树 [J]. 湖南师范大学自然科学学报, 2006, 29(1): 21-24.
Options
Outlines

/

〈 〉