LAUSR.org creates dashboard-style pages of related content for over 1.5 million academic articles. Sign Up to like articles & get recommendations!

Spectra of Subdivision-Vertex Join and Subdivision-Edge Join of Two Graphs

Photo by goumbik from unsplash

The subdivision graph $${\mathcal {S}}(G)$$S(G) of a graph G is the graph obtained by inserting a new vertex into every edge of G. Let $$G_1$$G1 and $$G_2$$G2 be two vertex… Click to show full abstract

The subdivision graph $${\mathcal {S}}(G)$$S(G) of a graph G is the graph obtained by inserting a new vertex into every edge of G. Let $$G_1$$G1 and $$G_2$$G2 be two vertex disjoint graphs. The subdivision-vertex join of $$G_1$$G1 and $$G_2$$G2, denoted by $$G_1{\dot{\vee }}G_2$$G1∨˙G2, is the graph obtained from $${\mathcal {S}}(G_1)$$S(G1) and $$G_2$$G2 by joining every vertex of $$V(G_1)$$V(G1) with every vertex of $$V(G_2)$$V(G2). The subdivision-edge join of $$G_1$$G1 and $$G_2$$G2, denoted by $$G_1{\underline{\vee }}G_2$$G1∨̲G2, is the graph obtained from $${\mathcal {S}}(G_1)$$S(G1) and $$G_2$$G2 by joining every vertex of $$I(G_1)$$I(G1) with every vertex of $$V(G_2)$$V(G2), where $$I(G_1)$$I(G1) is the set of inserted vertices of $${\mathcal {S}}(G_1)$$S(G1). In this paper, we determine the adjacency spectra, the Laplacian spectra and the signless Laplacian spectra of $$G_1{\dot{\vee }}G_2$$G1∨˙G2 (respectively, $$G_1{\underline{\vee }}G_2$$G1∨̲G2) for a regular graph $$G_1$$G1 and an arbitrary graph $$G_2$$G2, in terms of the corresponding spectra of $$G_1$$G1 and $$G_2$$G2. 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$$G1∨˙G2 (respectively, $$G_1{\underline{\vee }}G_2$$G1∨̲G2) for a regular graph $$G_1$$G1 and an arbitrary graph $$G_2$$G2.

Keywords: subdivision; edge; graph; join; vertex; vee

Journal Title: Bulletin of the Malaysian Mathematical Sciences Society
Year Published: 2019

Link to full text (if available)


Share on Social Media:                               Sign Up to like & get
recommendations!

Related content

More Information              News              Social Media              Video              Recommended



                Click one of the above tabs to view related content.