Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2021, Vol. 48 Issue (2): 180-188    DOI: 10.3785/j.issn.1008-9497.2021.02.007
数学与计算机科学     
关于两个图的一类新连接图的谱
刘剑萍, 吴先章, 陈锦松
福州大学 数学与计算机科学学院， 福建 福州 350116
On the spectrum of a new join of two graphs
LIU Jianping, WU Xianzhang, CHEN Jinsong
College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China
 全文: PDF(1221 KB)   HTML  
摘要： 给定2个图G1和G2，设G1的边集E(G1)={e1,e2,?,em1}，则图G1⊙G2可由一个G1，m1个G2通过在G1对应的每条边外加一个孤立点，新增加的点记为U={u1,u2,?,um1}，将ui分别与第i个G2的所有点以及G1中的边ei的端点相连得到，其中i=?1,2,?,m1。得到：（i）当G1是正则图，G2是正则图或完全二部图时，确定了G1⊙G2的邻接谱（A-谱）。（ii）当G1是正则图，G2是任意图时，给出了G1⊙G2的拉普拉斯谱（L-谱）。（iii）当G1和G2都是正则图时，给出了G1⊙G2的无符号拉普拉斯谱（Q-谱）。作为以上结论的应用，构建了无限多对A-同谱图、L-同谱图和Q-同谱图；同时当G1是正则图时，确定了G1⊙G2支撑树的数量和Kirchhoff指数。
关键词： 谱;  同谱图;  支撑树;  基尔霍夫（Kirchhoff）指数    
Abstract: Given graphs G1 and G2,let E(G1)={e1,e2,?,em1} be the edge set of G1,the graph G1⊙G2 can be obtained from one copy of G1 and m1 copies of G2 by adding a new vertex corresponding to each edge of G1, letting the resulting new vertex set be U={u1,u2,?,um1}, and joining ui with each vertex of i-th copy of G2 and with the endpoints of ei, for i=1,2,?,m1. We can determine: (i) the adjacency spectrum of G1⊙G2 for G1,G2 are both regular graphs, or G1 is regular graph, but G2 is a complete bipartite graph; (ii) the Laplacian spectrum of G1⊙G2 when G1 is a regular graph and G2 is an arbitrary graph; (iii) the signless Laplacian spectrum of G1⊙G2 for both G1 and G2 are regular graphs. As applications, we construct infinitely many pairs of A-cospectral graphs, L-cospectral graphs and Q-cospectral graphs. and determine the number of spanning trees and the Kirchhoff index of G1⊙G2,where G1 is a regular graph.
Key words: spectrum    cospectral graphs    spanning trees    Kirchhoff index
收稿日期: 2018-04-12 出版日期: 2021-03-18
CLC:  O  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
刘剑萍
吴先章
陈锦松

引用本文:

刘剑萍, 吴先章, 陈锦松. 关于两个图的一类新连接图的谱[J]. 浙江大学学报（理学版）, 2021, 48(2): 180-188.

LIU Jianping, WU Xianzhang, CHEN Jinsong. On the spectrum of a new join of two graphs. Journal of Zhejiang University (Science Edition), 2021, 48(2): 180-188.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2021.02.007    或    https://www.zjujournals.com/sci/CN/Y2021/V48/I2/180

1 BONDY J A ， MURTY U S R . Graph Theory with Application［M］. New York：Elsevir Science Publishing Co，Inc，1976.
2 LI X L ， SHI Y T ， GUTMAN I . Graph Energy［M］.New York：Springer-Verlag，2012. 10.1007/978-1-4614-4220-2_10
3 GUTMAN I ， BABIC D ， GINEITYPE V . Degeneracy in the equivalent bond orbital model for high-energy bond in the photoelectron spectra of saturated hydrocarbons［J］.ACH Models in Chemistry，1998，135（6）：901-909.
4 GAO X ， LUO Y F ， LIU W W . Kirchhoff index in line，subdivision and total graph of a regular graph［J］.Discrete Applied Mathematics，2012，160（4/5）：560-565. DOI：10.1016/j.dam.2011.11.011
5 KLEIN D J ， RANDIC M .Resistance distance［J］.Journal of Mathematical Chemistry，1993，12：81-95.
6 ZHANG Y P ， YONG X R ， GOLIN M J .Chebyshev polynomials and spanning tree formula for circulant and related graphs［J］. Discrete Mathematics，2005，298（1/2/3）：334-364. DOI：10.1016/j.disc.2004.10.025
7 LIU J P ， LIU B L . A Laplacian-energy-like invariant of a graph［J］.MATCH Communnications in Mathematical and in Computer Chemistry，2008，59（2）：355-372. DOI：10.1016/j.marchem.2007.11.002
8 LIU J P ， LIU B L ， RADENKOVIC S ，et al . Minimal LEL-equienergetic graphs［J］. MATCH Communnications in Mathematical and in Computer Chemistry，2009，61（2）：471-478. DOI：10.1111/j.1467-9892.2008.00605.x
9 CUI S Y ， TIAN G X . The spectrum and the signless Laplacian spectrum of coronae［J］.Linear Algebra and Its Applications，2012，437（7）：1692-1703. DOI：10.1016/j.laa.2012.05.019
10 GOPALAPILLAI I .The spectrum of neighborhood corona of graphs［J］.Kragujevac Journal of Mathematics，2011，35（3）：493-500.
11 HOU Y P ， SHIU W C .The spectrum of the edge corona of two graphs［J］.Electronic Journal of Linear Algebra，2010，20（1）：586-594. DOI：10.13001/1081-3810.1395
12 WANG S L ， ZHOU B . The signless Laplacian spectra of the corona and edge corona of two graphs［J］. Linear and Multilinear Algebra，2013，61（2）：197-204. DOI：10.1080/03081087.2012.670236
13 INDUAL G . Spectrum of two new joins of graphs and infinite families of integral graphs［J］. Kragujevac Journal of Mathematics，2012，36（1）：133-139.
14 MCLEMAN C ， MCNICHOLAS E . Spectra of coronae［J］. Linear Algebra & Its Applications，2011，435（5）：998-1007. DOI：10.1016/j.laa.2011.02.007
15 BONCHEV D ， BALABAN A T ，LIU .X， et al .Molecular cyclicity and centricity of polycyclic graphs I cyclicity based on resistance distances or reciprocal distances［J］.International Journal of Quantum Chemistry，1994，50（1）：1-20.
16 HONG Y . Bounds of eigenvalues of a graph［J］. Acta Mathematicae Applicatae Sinica，1988，4（2）：165-168. 10.1007/bf02006065
17 FANG K . Ordering graphs with cut edges by their spectral radii［J］. Acta Mathematicae Applicatae Sinica，2012，28（1）：193-200. DOI：10.1007/S10255-012-0134-X
18 HORN R A ， JOHNSON C R . Topics in Matrix Analysis［M］.Cambridge：Cambridge University Press，1991. 10.1017/cbo9780511840371
19 CVETKOVIC D M ， DOOB M ， SACHS H . Spectrum of Graphs：Theory and Applications［M］.3rd ed.Heidelberg：Johann Ambrosius Barth， 1995.
[1] 李楠,曹小红. 有界线性算子的拓扑一致降标及(WE)性质[J]. 浙江大学学报（理学版）, 2023, 50(5): 551-557.
[2] 车雨红, 戴磊. 有界线性算子的a-Browder定理及(R1)性质[J]. 浙江大学学报（理学版）, 2022, 49(6): 676-681.
[3] 徐艳艳,廖志银,王珍,王首锋. 密码子优化的人溶菌酶基因在毕赤酵母中的分泌表达及抗菌活性分析[J]. 浙江大学学报（理学版）, 2022, 49(6): 753-759.
[4] 郜文,孙秀梅,金衍健,郝青,傅宇,叶茂盛,杨承虎,郭远明. 固相萃取净化-气相色谱-负化学源质谱法测定近岸海洋环境中的甲氧基多溴联苯醚[J]. 浙江大学学报（理学版）, 2022, 49(3): 344-353.
[5] 郏丽丽, 孙婷婷. 紫色球杆菌视紫红质光谱特性的机器学习研究[J]. 浙江大学学报（理学版）, 2022, 49(3): 280-286.
[6] 孙晨辉,王宁,曹小红. A-Browder定理及其摄动[J]. 浙江大学学报（理学版）, 2022, 49(3): 287-293.
[7] 赵小鹏, 戴磊, 曹小红. 有界线性算子及其函数的（R）性质[J]. 浙江大学学报（理学版）, 2022, 49(3): 294-299.
[8] 周玉兰,陈嘉,孔华芳,薛蕊,程秀强. Bernoulli泛函空间中广义计数算子的表示[J]. 浙江大学学报（理学版）, 2022, 49(3): 316-323.
[9] 蔡靖,刘思懿,吴媛媛,郑紫凌,王如意,李强标. 同步脱氮除硫燃料电池的电化学特性研究[J]. 浙江大学学报（理学版）, 2022, 49(1): 105-111.
[10] 陈春, 何建平, 郑诗璐, 吴雁南, 王莹, 徐高福, 于明坚. 片段化森林中檵木幼苗种内叶经济性状变异及其驱动因子[J]. 浙江大学学报（理学版）, 2021, 48(6): 718-727.
[11] 姚茂群, 周传鑫, 李聪辉. 基于和图的电流型CMOS三变量通用逻辑门设计[J]. 浙江大学学报（理学版）, 2021, 48(5): 565-572.
[12] 杨盈悦, 朱羽庄, 梅光明, 李晋成. 渔业养殖水体中孔雀石绿、结晶紫及其代谢物残留量的检测方法研究[J]. 浙江大学学报（理学版）, 2021, 48(4): 461-469.
[13] 干雅平, 楼超艳, 朱岩, 甘露, 陈佳萍. 超临界流体色谱法同时测定海洋水体及沉积物中的4种双酚[J]. 浙江大学学报（理学版）, 2021, 48(2): 215-220.
[14] 陈俐宏, 苏维钢. 有界线性算子的限制及其谱性质[J]. 浙江大学学报（理学版）, 2020, 47(6): 687-690.
[15] 赵海英, 银宇堃. 苗族服饰色彩体系构建研究[J]. 浙江大学学报（理学版）, 2020, 47(6): 660-668.