Spectra of subdivision-vertex join and subdivision-edge join of two graphs

Xiaogang Liu; Zuhe Zhang

doi:10.1007/s40840-017-0466-z

paper

Spectra of subdivision-vertex join and subdivision-edge join of two graphs

arXiv:1212.0619 · doi:10.1007/s40840-017-0466-z

Abstract

The subdivision graph $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 \emph{subdivision-vertex join} of $G_{1}$ and $G_{2}$ , denoted by $G_{1} \lor ˙ G_{2}$ , is the graph obtained from $S (G_{1})$ and $G_{2}$ by joining every vertex of $V (G_{1})$ with every vertex of $V (G_{2})$ . The \emph{subdivision-edge join} of $G_{1}$ and $G_{2}$ , denoted by $G_{1} \lor G_{2}$ , is the graph obtained from $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 $S (G_{1})$ . In this paper we determine the adjacency spectra, the Laplacian spectra and the signless Laplacian spectra of $G_{1} \lor ˙ G_{2}$ (respectively, $G_{1} \lor 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} \lor ˙ G_{2}$ (respectively, $G_{1} \lor G_{2}$ ) for a regular graph $G_{1}$ and an arbitrary graph $G_{2}$ .

The Bulletin of the Malaysian Mathematical Society (2017)

Spectra of subdivision-vertex join and subdivision-edge join of two graphs

Abstract

References in corpus (3)

Cited by in corpus (4)