Spectra of subdivision-vertex and subdivision-edge neighbourhood coronae

By Xiaogang Liu, Pengli Lu. 2012

76 citations recorded by the source corpus.

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 G1 and G2 be two vertex disjoint graphs. The subdivision-vertex neighbourhood corona of G1 and G2, denoted by G1G2, is the graph obtained from S(G1) and |V(G1)| copies of G2, all vertex disjoint, and joining the neighbours of the ith vertex of V(G1) to every vertex in the ith copy of G2. The subdivision-edge neighbourhood corona of G1 and G2, denoted by G1⊟G2, is the graph obtained from S(G1) and |I(G1)| copies of G2, all vertex disjoint, and joining the neighbours of the ith vertex of I(G1) to every vertex in the ith copy of G2, where I(G1) is the set of inserted vertices of S(G1). In this paper we determine the adjacency spectra, the Laplacian spectra and the signless Laplacian spectra of G1G2 (respectively, G1⊟G2) in terms of the corresponding spectra of G1 and G2. 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.

Subfields: Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/29ac52f7c2f3a79338d5f062a72770bc092484ee

Citations in the corpus