基于拉普拉斯谱确定的两类树

doi:10.15960/j.cnki.issn.1007-6093.2017.01.010

Abstract

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, doi: 10.15960/j.cnki.issn.1007-6093.2017.01.010.

share this article

0
/ / Recommend

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2017.01.010

https://www.ort.shu.edu.cn/EN/Y2017/V21/I1/103

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.

Related Articles 10

[1]	SUN Qiushi, YANG Xiaoyun, WANG Ligong, LI Xihe, WANG Pengchao. Laplacian spectral characterizations of new unicyclic graphs H(p,tK_1,m) [J]. Operations Research Transactions, 2019, 23(1): 72-80.
[2]	YU Guidong, SUN Wei, LU Xingting. The least eignvalue of the graphs whose complements are connected and have pendant vertices [J]. Operations Research Transactions, 2019, 23(1): 90-96.
[3]	ZHAI Ruonan, WANG Ligong, DONG Zhanpeng, WANG Zhanqing, MEI Ruoxing. Laplacian spectral characterizations of some classes of multi-cyclic graphs [J]. Operations Research Transactions, 2016, 20(2): 59-68.
[4]	XU Feng, LING Chen. Some properties on Pareto-eigenvalues of higher-order tensors [J]. Operations Research Transactions, 2015, 19(3): 34-41.
[5]	MEI Ruoxing, WANG Ligong, WANG Luhua, WANG Zhanqing. Laplacian spectral characterizations of unicyclic graphs H( p, t K_{ 1, m}) [J]. Operations Research Transactions, 2015, 19(1): 57-64.
[6]	CHEN Lin, HUANG Qiongxiang. Tricyclic graphs with exactly two Q-main eigenvalues [J]. Operations Research Transactions, 2014, 18(3): 13-32.
[7]	XU Weiwei, WANG Wenhuan. Bicyclic graph with the maximal Estrada indices [J]. Operations Research Transactions, 2014, 18(2): 111-118.
[8]	LI Zhening, LING Chen, WANG Yiju, YANG Qingzhi. Some advances in tensor analysis and polynomial optimization [J]. Operations Research Transactions, 2014, 18(1): 134-148.
[9]	YU Guidong,FAN Yizheng. The least eigenvalue of graphs whose complements are 2-vertex or 2-edge connected [J]. Operations Research Transactions, 2013, 17(2): 81-88.
[10]	Wang-Li-Gong, CHEN Yan-Qing. Some new families of Q-integral graphs [J]. Operations Research Transactions, 2012, 16(2): 23-31.

Metrics

Viewed

Full text

Abstract

Comments

Abstract
References
Related Articles
Recommended Articles
Metrics
Comments

TOP