Spectra of subdivision-vertex and subdivision-edge joins of graphs
Spectra of subdivision-vertex and subdivision-edge joins of graphs
复制标题
DOI：
--
复制
发表时间：
2012-12
期刊：
影响因子：
--
通讯作者：
Xiaogang Liu;Zuhe Zhang
中科院分区：
文献类型：
--
作者：
Xiaogang Liu;Zuhe Zhang
细分图 $\mathcal{S}(G)$ 图形的 $G$ 的每条边都插入一个新的顶点得到这个图吗 $G$． 让 $G_1$ 和 $G_2$ 是两个顶点不相交的图。的细分顶点连接 $G_1$ 和 $G_2$，表示为 $G_1\dot{\vee}G_2$，是由 $\mathcal{S}(G_1)$ 和 $G_2$ 通过连接的每个顶点 $V(G_1)$ 每个顶点都是 $V(G_2)$． 的细分边连接 $G_1$ 和 $G_2$，表示为 $G_1\underline{\vee}G_2$，是由 $\mathcal{S}(G_1)$ 和 $G_2$ 通过连接的每个顶点 $I(G_1)$ 每个顶点都是 $V(G_2)$，其中 $I(G_1)$ 插入顶点的集合是 $\mathcal{S}(G_1)$． 的邻接谱、拉普拉斯谱和无符号拉普拉斯谱 $G_1\dot{\vee}G_2$ (分别； $G_1\underline{\vee}G_2$)表示正则图 $G_1$ 任意一个图 $G_2$的对应谱 $G_1$ 和 $G_2$． 作为应用，这些结果使我们能够构造无限多对共谱图。我们也给出了生成树的个数和的基尔霍夫指数 $G_1\dot{\vee}G_2$ (分别； $G_1\underline{\vee}G_2$)表示正则图 $G_1$ 任意一个图 $G_2$．
The subdivision graph $\mathcal{S}(G)$ of a graph $G$ is the graph obtained by inserting a new vertex into every edge of $G$. Let $G_1$ and $G_2$ be two vertex disjoint graphs. The subdivision-vertex join of $G_1$ and $G_2$, denoted by $G_1\dot{\vee}G_2$, is the graph obtained from $\mathcal{S}(G_1)$ and $G_2$ by joining every vertex of $V(G_1)$ with every vertex of $V(G_2)$. The subdivision-edge join of $G_1$ and $G_2$, denoted by $G_1\underline{\vee}G_2$, is the graph obtained from $\mathcal{S}(G_1)$ and $G_2$ by joining every vertex of $I(G_1)$ with every vertex of $V(G_2)$, where $I(G_1)$ is the set of inserted vertices of $\mathcal{S}(G_1)$. In this paper we determine the adjacency spectra, the Laplacian spectra and the signless Laplacian spectra of $G_1\dot{\vee}G_2$ (respectively, $G_1\underline{\vee}G_2$) for a regular graph $G_1$ and an arbitrary graph $G_2$, in terms of the corresponding spectra of $G_1$ and $G_2$. As applications, these results enable us to construct infinitely many pairs of cospectral graphs. We also give the number of the spanning trees and the Kirchhoff index of $G_1\dot{\vee}G_2$ (respectively, $G_1\underline{\vee}G_2$) for a regular graph $G_1$ and an arbitrary graph $G_2$.