English

运筹学学报 >

2016 , Vol. 20 >Issue 2: 59 - 68

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

运筹学

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

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

收稿日期: 2015-08-06

  网络出版日期: 2016-06-15

基金资助

国家自然科学基金(No. 11171273), 国家级大学生创新创业训练计划(No. 201410699079)

收起

Laplacian spectral characterizations of some classes of multi-cyclic graphs

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

Received date: 2015-08-06

  Online published: 2016-06-15

Fold

摘要

设图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)分别是由它们的拉普拉斯谱确定的.

关键词： 拉普拉斯谱; 度序列; 双圈图; 三圈图

本文引用格式

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

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

参考文献

[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.
Options
文章导航

/

〈 〉