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

On the spectrum of a new join of two graphs

给定2个图G_(1)和G_(2),设G_(1)的边集E(G_(1))={e_(1),e_(2),…,e_(m1)},则图G_(1)⊙G_(2)可由一个G_(1),m_(1)个G_(2)通过在G_(1)对应的每条边外加一个孤立点,新增加的点记为U={u_(1),u_(2),…,u_(m1)},将u_(i)分别与第i个G_(2)的所有点以及G_(1)中的边e_(i)的端点相连得到,其中i=1,2,…,m_(1)。得到:(i)当G_(1)是正则图,G_(2)是正则图或完全二部图时,确定了G_(1)⊙G_(2)的邻接谱(A-谱)。(ii)当G_(1)是正则图,G_(2)是任意图时,给出了G_(1)⊙G_(2)的拉普拉斯谱(L-谱)。(iii)当G_(1)和G_(2)都是正则图时,给出了G_(1)⊙G_(2)的无符号拉普拉斯谱(Q-谱)。作为以上结论的应用,构建了无限多对A-同谱图、L-同谱图和Q-同谱图;同时当G_(1)是正则图时,确定了G_(1)⊙G_(2)支撑树的数量和Kirchhoff指数。

Given graphs G_(1)and G_(2),let E(G_(1))={e_(1),e_(2),…,e_(m1)}be the edge set of G_(1),the graph G_(1)⊙G_(2)can be obtained from one copy of G_(1)and m1 copies of G_(2)by adding a new vertex corresponding to each edge of G_(1),letting the resulting new vertex set be U={u_(1),u_(2),…,u_(m1)},and joining uiwith each vertex of i-th copy of G_(2)and with the endpoints of ei,for i=1,2,…,m1.We can determine:(i)the adjacency spectrum of G_(1)⊙G_(2)for G_(1),G_(2)are both regular graphs,or G_(1)is regular graph,but G_(2)is a complete bipartite graph;(ii)the Laplacian spectrum of G_(1)⊙G_(2)when G_(1)is a regular graph and G_(2)is an arbitrary graph;(iii)the signless Laplacian spectrum of G_(1)⊙G_(2)for both G_(1)and G_(2)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 G_(1)⊙G_(2),where G_(1)is a regular graph.