关于两个图的一类新连接图的谱

作者：刘剑萍; 吴先章; 陈锦松^*

来源：浙江大学学报(理学版), 2021, 48(02): 180-195.

• 谱
• 同谱图
• 支撑树
• 基尔霍夫(Kirchhoff)指数

给定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指数。