Spectra of subdivision-vertex and subdivision-edge neighbourhood coronae

preprint2012arXivOpen access

Abstract

Let G=(V(G),E(G))G=(V(G),E(G)) be a graph with vertex set V(G)V(G) and edge set E(G)E(G). The subdivision graph S(G)\mathcal{S}(G) of a graph GG is the graph obtained by inserting a new vertex into every edge of GG. Let G1G_1 and G2G_2 be two vertex disjoint graphs. The subdivision-vertex neighbourhood corona of G1G_1 and G2G_2, denoted by G1⊡G2G_1 \boxdot G_2, is the graph obtained from S(G1)\mathcal{S}(G_1) and ∣V(G1)∣|V(G_1)| copies of G2G_2, all vertex disjoint, and joining the neighbours of the iith vertex of V(G1)V(G_1) to every vertex in the iith copy of G2G_2. The subdivision-edge neighbourhood corona of G1G_1 and G2G_2, denoted by G1⊟G2G_1 \boxminus G_2, is the graph obtained from S(G1)\mathcal{S}(G_1) and ∣I(G1)∣|I(G_1)| copies of G2G_2, all vertex disjoint, and joining the neighbours of the iith vertex of I(G1)I(G_1) to every vertex in the iith copy of G2G_2, where I(G1)I(G_1) is the set of inserted vertices of S(G1)\mathcal{S}(G_1). In this paper we determine the adjacency spectra, the Laplacian spectra and the signless Laplacian spectra of G1⊡G2G_1\boxdot G_2 (respectively, G1⊟G2G_1\boxminus G_2) in terms of the corresponding spectra of G1G_1 and G2G_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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.