单圈图H(p,tK_{1,m})的Laplacian谱刻画

运筹学学报 ›› 2015, Vol. 19 ›› Issue (1): 57-64.

单圈图H(p,tK_{1,m})的Laplacian谱刻画

梅若星¹, 王力工^1,*, 王陆华¹, 王展青¹

1. 西北工业大学理学院应用数学系, 西安 710072;

收稿日期:2014-07-18 出版日期:2015-03-15 发布日期:2015-03-15
通讯作者: 王力工 E-mail:lgwangmath@163.com
基金资助:
国家自然科学基金(No. 11171273), 国家级大学生创新创业训练计划项目(No. 201410699079)

Laplacian spectral characterizations of unicyclic graphs H( p, t K_{ 1, m})

MEI Ruoxing¹, WANG Ligong^1,*, WANG Luhua¹, WANG Zhanqing¹

1. Department of Applied Mathemtics, School of Science, Northwestern Polytechnical University, Xi'an 710072, China

Received:2014-07-18 Online:2015-03-15 Published:2015-03-15

摘要/Abstract

摘要： 设图\,$H(p,tK_{1,m})$\,是一个顶点数为\,$p+mt$\,的连通单圈图，它是由圈\,$C_{p}$\,的依次相邻的\,$t(1\leq t\leq p)$\,个顶点、每一个顶点分别与星\,$K_{1,m}$\,的中心重合而得到的单圈图. 证明了单圈图\,$ H( p,p K_{1,4})$, $H(p,p K_{1,3})$, $H(p,(p-1)K_{1,3})$\,是由它们的\,Laplacian\,谱确定的，并证明了当\,$p$\,为偶数时，单圈图\,$H(p,$$2K_{1,3})$, $H( p,(p-2) K_{1,3})$, $H(p,(p-3)K_{1,3})$\,也是由它们的\,Laplacian\,谱确定的.

关键词: Laplacian谱, 邻接谱, 单圈图

Abstract: Let $H(p,tK_{1,m})$ be a connected unicyclic graph with $p+mt$ vertices obtained from $C_{p}$ by attaching the center of star $K_{1,m}$ to each one of $t$ mutual adjacent vertices of the cycle $C_{p}$, respectively. In this paper, it is proved that the unicyclic graphs $H(p,p K_{1,4})$, $H(p,p K_{1,3})$, $H((p,(p-1) K_{1,3} )$ are determined by their Laplacian spectra, and when $ p $ is even number, the unicyclic graphs $H(p,2 K_{1,3})$, $H(p,(p-2)K_{1,3})$, $H(p,(p-3)K_{1,3})$ are also determined by their Laplacian spectra.

Key words: Laplacian spectrum, adjacency spectrum, unicyclic graph

中图分类号:

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

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.

参考文献

G\ddot{u}nthard Hs H, Primas H. Zusammenhang von Graphentheorie und MO-Theorie von Molekeln mit Systemen konjugierter Bindungen [J]. Helv Chim Acta, 1956, 39: 1645-1653.
Kac M. Can one hearing the shape of a drum? [J]. Amer Math Monthly, 1966, 73: 1-23.
van Dam E R, Haemers W H. Which graphs are determined by their spectrum? [J]. Linear Algebra Appl, 2003, 373: 241-272.

Liu X G, Zhou S M. Spectral characterizations of propeller graphs [J]. Electronic Journal of Linear Algebra, 2014, 27: 19-38.
van Dam E R, Haemers W H. Developments on spectral characterizations of graphs [J]. Discrete Math, 2009, 309: 576-586.

Boulet R. Spectral characterizations of sun graphs and broken sun graphs [J]. Discrete Mathematics and Theoretical Computer Science, 2009, 149-160.

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

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.
Guo G Q, Wang G P. On the (signless) Laplacian spectral characterization of the line graphs of lollipop graphs [J]. Linear Algebra Appl, 2013, 438(12): 4595-4605.

Liu F J, Huang Q X. Laplacian spectral characterization of 3-rose graphs [J]. Linear Algebra Appl, 2013, 439(10): 2914-2920.
Liu M H, Shan H Y, Das K C. Some graphs determined by their (signless) Laplacian spectra [J]. Linear Algebra Appl, 2014, 449: 154-165.
Liu X G, Wang S J. Laplacian spectral characterization of some graph products [J]. Linear Algebra Appl, 2012, 437: 1749-1759.
王陆华. 单圈图 H(p,tK_{1,2)的拉普拉斯谱刻画 [J]. 纺织高校基础科学学报, 2014, 27(3): 293-297.
卢鹏丽，王旭柱，陈作汉. 一类单圈图的Laplacian谱刻画 [J]. 哈尔滨工程大学学报, 2012, 33(7): 851-854.
Mirzakhah M, Kiani D. The sun graph is determined by its signless Laplacian spectrum [J]. Electronic Journal of Linear Algebra, 2010, 20: 610-620.
Liu X G, Wang S J, Zhang Y P. On the spectral characterization of some unicyclic graphs [J]. Discrete Math, 2011, 311: 2317-2336.
Cvetkovi\'{c} D M, Doob M, Sachs H. Spectra of Graphs-Theory and Applications [M]. Heidelberg-leipzig: Johan Ambrosius Bart Verlag, 1995.

Cvetkovi\'{c} D M, Rowlinson P. Spectra of unicyclic graphs [J]. Graphs and Combinatorics, 1987, 3: 7-23.
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.

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

[1]	孙秋实, 杨筱韵, 王力工, 李希赫, 王朋超. 新单圈图H(p,tK_1,m)的拉普拉斯谱刻画[J]. 运筹学学报, 2019, 23(1): 72-80.
[2]	丁超, 余桂东. 含偶圈图的Laplacian 谱刻画[J]. 运筹学学报, 2018, 22(4): 135-140.
[3]	简相国,袁西英,张曼. 单圈图和双圈图的最大无符号拉普拉斯分离度[J]. 运筹学学报, 2015, 19(2): 99-104.