几类多圈图的拉普拉斯谱刻画

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

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, a bicyclic graph \theta_{n}(p_1,p_2,\cdots,p_t) and a m-cyclic graph H_n(m\cdot C_3;p_1,p_2,\cdots,p_t) are defined. It is proved that bicyclic graphs \theta_{n}(p), \theta_{n}(p,q), and tricyclic graphs H_n(3\cdot C_3;p), H_n(3\cdot C_3;p,q) are determined by their Laplacian spectra.

Key words: Laplacian spectrum, degree sequence, bicyclic graph, tricyclic graph graph

ZHAI Ruonan, WANG Ligong, DONG Zhanpeng, WANG Zhanqing, MEI Ruoxing. Laplacian spectral characterizations of some classes of multi-cyclic graphs[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2016.02.005.

References

[1] Gunthard H H, Primas H. Zusammenhang von Graphentheorie und MO-Theorie von Molekeln mit Systemen konjugierter Bindungen [J]. Helv Chim Acta, 1956, 39: 1645-1653.

[2] Kac M. Can one hearing the shape of a drum? [J]. Amer Math Monthly, 1966, 73: 1-23.

[3] Dam E R, Haemers W H. Which graphs are determined by their spectrum? [J]. Linear Algebra Appl, 2003, 373: 241-272.

[4] Dam E R, Haemers W H. Developments on spectral characterizations of graphs [J]. Discrete Math, 2009, 309: 576-586.

[5] Haemers W H, Liu X G, Zhang Y P. Spectral characterizations of lollipop graphs [J]. Linear Algebra Appl, 2008, 428(11-12): 2415-2423.

[6] Liu X G, Wang S J, Zhang Y P, et al. On the spectral characterization of some unicyclic graphs [J]. Discrete Math, 2011, 311: 2317-2336.

[7] 卢鹏丽，王旭柱，陈作汉. 一类单圈图的 Laplacian 谱刻画 [J]. 哈尔滨工程大学学报, 2012, 33(7): 851-854.

[8] Wang L H, Wang L G. Laplacian spectral characterization of a kind of unicyclic graphs [J]. Journal of Mathematical Research with Applications, 2014, 34(5): 505-516.

[9] Wang J F, Huang Q X, Belardo F, et al. On the spectral characterizations of \infty-graph [J]. Discrete Math, 2010, 310(13-14): 1845-1855.

[10] Liu F J, Huang Q X. Laplacian spectral characterization of 3-rose graphs [J]. Linear Algebra Appl, 2013, 439(10): 2914-2920.

[11] Liu X G, Zhou S M. Spectral characterizations of propeller graphs [J]. Electronic Journal of Linear Algebra, 2014, 27: 19-38.

[12] Wang L H, Wang L G. Laplacian spectral characterization of clover graphs [J]. Linear and Multilinear Algebra, 2015, 63(12): 2396-2405.

[13] 卢鹏丽. 章鱼图由 Laplacian 谱确定 [J]. 宁夏大学学报, 2009, 30(3): 220-222.

[14] Bu C J, Zhou J, Li H B, et al. Spectral characterization of the corona of a cycle and two isolated vertices [J]. Graphs and Combinatorics, 2014, 30(5): 1123-1133.

[15] 王陆华. 单圈图 H(p,tK_{1,2}) 的拉普拉斯谱刻画 [J]. 纺织高校基础科学学报, 2014, 27(3):293-297.

[16] 梅若星, 王力工, 王陆华等. 单圈图 H(p,tK_{1,m}) 的 Laplacian 谱刻画 [J]. 运筹学学报, 2015, 19(1): 57-64.

[17] Kelmens A K, Chelnokov V M. A certain polynomial of a graph and graphs with an extremal number of trees [J]. Journal of Combinatorial Theory, Series B, 1974, 16: 197-214.

[18] Li J S, Zhang X D. On the Laplacian eigenvalues of a graph [J]. Linear Algebra Appl, 1998, 285(1-3): 305-307.

[19] Li J S, Pan Y L. A note on the second largest eigenvalues of the Laplacian matrix of a graph [J]. Linear Multilinear Algebra, 2000, 48(2): 117-121.

[20] Biggs N L. Algebraic Graph Theory [M]. Cambridge: Cambridge University Press, 1993.

[21] Brualdi R A, Ryser H J. Combinatorial Matrix Theory [M]. New York: Cambridge University Press, 1991, 380.

Laplacian spectral characterizations of some classes of multi-cyclic graphs

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 8

Recommended Articles

Metrics

Comments

[1]	TAO Yanliang, HUANG Qiongxiang, CHEN Lin. Contraction graph method for the interval edge-colorings of graphs [J]. Operations Research Transactions, 2019, 23(2): 31-43.
[2]	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.
[3]	ZHANG Tao, BAI Yanqin. Two families of trees determined by their Laplacian spectrum [J]. Operations Research Transactions, 2017, 21(1): 103-110.
[4]	JIAN Xiangguo,YUAN Xiying,ZHANG Man. The maximum signless Laplacian separator of unicyclic and bicyclic graphs [J]. Operations Research Transactions, 2015, 19(2): 99-104.
[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]	XIAO Mao, WANG Wenhuan. Minimal skew energies of oriented bicyclic graphs without even cycles [J]. Operations Research Transactions, 2014, 18(4): 85-95.
[7]	XU Weiwei, WANG Wenhuan. Bicyclic graph with the maximal Estrada indices [J]. Operations Research Transactions, 2014, 18(2): 111-118.
[8]	Wang-Li-Gong, CHEN Yan-Qing. Some new families of Q-integral graphs [J]. Operations Research Transactions, 2012, 16(2): 23-31.