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

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

运筹学学报

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

翟若男¹王力工^1,*董占鹏¹ 王展青¹梅若星¹

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

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

Laplacian spectral characterizations of some classes of multi-cyclic graphs

ZHAI Ruonan¹ WANG Ligong^1,*DONG Zhanpeng¹WANG Zhanqing¹MEI Ruoxing¹

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

Received:2015-08-06 Online:2016-06-15 Published:2016-06-15

摘要/Abstract

摘要：

设图G是一个简单连通图. 如果任何一个与图G同拉普拉斯谱的图都与图G同构，则称图G是由其拉普拉斯谱确定的. 定义了双圈图\theta_{n}(p_1,p_2,\cdots,p_t) 和m 圈图H_n(m\cdot C_3;p_1,p_2,\cdots,p_t). 证明了双圈图\theta_{n}(p)和\theta_{n}(p,q)，三圈图H_n(3\cdot C_3;p)和H_n(3\cdot C_3;p,q)分别是由它们的拉普拉斯谱确定的.

关键词: 拉普拉斯谱, 度序列, 双圈图, 三圈图

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

翟若男, 王力工, 董占鹏, 王展青, 梅若星. 几类多圈图的拉普拉斯谱刻画[J]. 运筹学学报, doi: 10.15960/j.cnki.issn.1007-6093.2016.02.005.

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.

参考文献

[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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics

本文评价

[1]	陶艳亮, 黄琼湘, 陈琳. 图的区间边着色的收缩图方法[J]. 运筹学学报, 2019, 23(2): 31-43.
[2]	孙秋实, 杨筱韵, 王力工, 李希赫, 王朋超. 新单圈图H(p,tK_1,m)的拉普拉斯谱刻画[J]. 运筹学学报, 2019, 23(1): 72-80.
[3]	陈媛媛, 王国平. 三圈图的无符号拉普拉斯谱半径[J]. 运筹学学报, 2019, 23(1): 81-89.
[4]	秦倩楠, 邵燕灵. 三圈图的极小广义和连通指数[J]. 运筹学学报, 2018, 22(1): 142-150.
[5]	张涛, 白延琴. 基于拉普拉斯谱确定的两类树[J]. 运筹学学报, 2017, 21(1): 103-110.
[6]	余桂东, 周甫, 刘琦. 可迹图的谱充分条件[J]. 运筹学学报, 2017, 21(1): 118-124.
[7]	简相国,袁西英,张曼. 单圈图和双圈图的最大无符号拉普拉斯分离度[J]. 运筹学学报, 2015, 19(2): 99-104.
[8]	蔡改香, 邢抱花, 余桂东. 三圈图的Harary指数[J]. 运筹学学报, 2015, 19(2): 45-53.
[9]	肖毛, 王文环. 不含偶圈双圈图的极小斜能量[J]. 运筹学学报, 2014, 18(4): 85-95.
[10]	陈琳, 黄琼湘. 恰有两个Q-主特征值的三圈图[J]. 运筹学学报, 2014, 18(3): 13-32.
[11]	徐薇薇, 王文环. 双圈图的最大Estrada指数[J]. 运筹学学报, 2014, 18(2): 111-118.
[12]	王力工, 陈彦青. Q整图新类[J]. 运筹学学报, 2012, 16(2): 23-31.
[13]	陈艳, 袁西英, 韩苗苗. 关于三圈图的拉普拉斯谱半径的一些结果[J]. 运筹学学报, 2011, 15(4): 1-8.