Spectra of subdivision-vertex and subdivision-edge neighbourhood coronae

Xiaogang Liu; Pengli Lu

doi:10.1016/j.laa.2012.12.033

paper

Spectra of subdivision-vertex and subdivision-edge neighbourhood coronae

arXiv:1212.0851 · doi:10.1016/j.laa.2012.12.033

Abstract

Let $G = (V (G), E (G))$ be a graph with vertex set $V (G)$ and edge set $E (G)$ . 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 subdivision-vertex neighbourhood corona of $G_{1}$ and $G_{2}$ , denoted by $G_{1} ⊡ G_{2}$ , is the graph obtained from $S (G_{1})$ and $∣ V (G_{1}) ∣$ copies of $G_{2}$ , all vertex disjoint, and joining the neighbours of the $i$ th vertex of $V (G_{1})$ to every vertex in the $i$ th copy of $G_{2}$ . The subdivision-edge neighbourhood corona of $G_{1}$ and $G_{2}$ , denoted by $G_{1} ⊟ G_{2}$ , is the graph obtained from $S (G_{1})$ and $∣ I (G_{1}) ∣$ copies of $G_{2}$ , all vertex disjoint, and joining the neighbours of the $i$ th vertex of $I (G_{1})$ to every vertex in the $i$ th copy of $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} ⊡ G_{2}$ (respectively, $G_{1} ⊟ 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, and using the results on the Laplacian spectra of subdivision-vertex neighbourhood coronae, new families of expander graphs are constructed from known ones.

arXiv admin note: substantial text overlap with arXiv:1209.5906, arXiv:1212.0619

Spectra of subdivision-vertex and subdivision-edge neighbourhood coronae

Abstract

References in corpus (2)

Cited by in corpus (7)