betaFeedback

WorksMathematics

On the Construction of New Families of Distance Equienergetic Graphs

Abstract

For a graph GG with vertex set V(G)={vi:1≤i≤p}V(G)=\{v_{i}:1\leq i \leq p\} and edge set E(G)={ej:1≤j≤q},E(G)=\{e_{j}:1\leq j \leq q\}, its subdivision graph SGS_G is generalized to SG(n,m),S_{G}(n,m), by replacing each vertex viv_{i} with nn vertices and each edge-vertex eje_{j} with mm vertices, with each copy having the same neighbors as the vertex it replaces. Building on this construction, we define the generalized subdivision vertex join SG1(n,m)∨˙G2S_{G_{1}}(n,m)\dot{\vee} G_{2} and the generalized subdivision edge join SG(n,m)⊻G2,S_{G}(n,m)\veebar G_{2}, which extend the known subdivision vertex and subdivision edge join of graphs. In this paper, we determine the distance spectrum of SG1(n,n)∨˙G2S_{G_{1}}(n,n)\dot{\vee} G_{2} and SG(n,n)⊻G2,S_{G}(n,n)\veebar G_{2}, when G1G_{1} and G2G_{2} are regular graphs. As an application, we construct new families of DD-cospectral graphs and DD-equienergetic graphs of diameter 4.4.

Introduction

Let GG be a simple connected graph with vertex set V(G)={vi:1≤i≤p}V(G)=\{v_i:1\le i\le p\} and edge set E(G)={ej:1≤j≤q}E(G)=\{e_j:1\le j\le q\}. The adjacency matrix of GG, A(G)=(aij)A(G)=(a_{ij}) is a p×pp\times p symmetric matrix such that aij=1a_{ij}=1, if viv_i and vjv_j are adjacent, and 0 otherwise. Let λ1,λ2,…,λp\lambda_1,\lambda_2,\ldots,\lambda_p be the eigenvalues of A(G)A(G) (adjacency eigenvalues of GG). The adjacency spectrum of GG, spec⁡(G)\operatorname{spec}(G), is the collection of all eigenvalues of A(G)A(G) along with their multiplicities. Spectral graph theory provides a powerful framework for investigating the structural and combinatorial properties of graphs through the eigenvalues of matrices associated with them. Among the most commonly studied matrices are the adjacency matrix, the Laplacian matrix, and the distance matrix, each of which captures different aspects of a graph’s structure. In particular, the distance matrix has attracted considerable attention owing to its applications in communication networks, chemistry, and various optimization problems; see [1].

The distance between any two vertices vi,vj∈V(G)v_i,v_j\in V(G), d(vi,vj)d(v_i,v_j) is defined as the length of the shortest path connecting them in GG. In 1971, Graham and Pollack [5] introduced the distance matrix of a connected graph to study data communication problems. The distance matrix of GG, D(G)D(G) is the p×pp\times p symmetric matrix whose (i,j)(i,j)-th entry is equal to d(vi,vj)d(v_i,v_j). The eigenvalues of D(G)D(G) are called the DD-eigenvalues of GG and they along with their multiplicities form the DD-spectrum of GG. The DD-eigenvalues of GG have applications in various fields like data communication, chemistry, and molecular biology (see [2] and the references therein). Let ηi\eta_i be the ithi^{th} largest eigenvalue of D(G)D(G). The concept of distance energy of a graph was introduced in 2008 [8]. The distance energy (DD-energy) of a graph GG is defined as the sum of the absolute values of the eigenvalues of its distance matrix.

The subdivision graph SGS_G of a graph GG [4], is obtained from GG by subdividing each edge of GG using a new vertex, the vertex set of SGS_G is V(G)∪E(G)V(G) \cup E(G). The concept of subdivision vertex join (respectively, subdivision edge join), which is obtained from SG1S_{G_1} and G2G_2 by joining each vertex of V(G1)V(G_1) (respectively, E(G1)E(G_1)) to every vertex of V(G2)V(G_2), was introduced in 2012 [7]. Later in 2024, Shamsher and Pirzada [12] generalized the notion of subdivision graphs as follows:

Let GG be a graph with vertex set V(G)={v1,v2,…,vp}V(G) = \{v_1,v_2,\ldots,v_p\} and edge set E(G)={e1,e2,…,eq}E(G) = \{e_1,e_2,\ldots,e_q\}. The generalized subdivision graph of GG, denoted by SG(n,m)S_G(n,m), is the graph obtained from SGS_G by replacing each vertex viv_i, i=1,2,…,pi=1,2,\ldots,p, with nn new vertices having the same neighborhood as viv_i, followed by replacing each edge eje_j, j=1,2,…,qj=1,2,\ldots,q, with mm new vertices adjacent to the neighbors of eje_j. Equivalently, the graph SG(n,m)S_G(n,m) has vertex set

(V(G)×{1,2,…,n})∪(E(G)×{1,2,…,m}),\left(V(G) \times\{1,2,\ldots,n\}\right) \cup\left(E(G) \times\{1,2,\ldots,m\}\right),

where two vertices (vl,i)(v_l,i) and (em,j)(e_m,j), are adjacent whenever the edge em∈E(G)e_m \in E(G) is incident with the vertex vl∈V(G)v_l \in V(G) in GG. Motivated by this generalized subdivision graph, we introduce the concept of generalized subdivision vertex join and generalized subdivision edge join of two graphs G1G_1 and G2G_2 as follows.

Definition 1.1. The generalized subdivision vertex join SG1(n,m)∨˙G2S_{G_1}(n,m)\dot{\vee}G_2 is the graph obtained from SG1(n,m)S_{G_1}(n,m) and G2G_2 by joining each vertex of V(G1)×{1,2,…,n}V(G_1)\times\{1,2,\ldots,n\} to every vertex of V(G2)V(G_2).

Note that, if GiG_i is a graph on pip_i vertices and qiq_i edges, i=1,2i=1,2, then SG1(n,m)∨˙G2S_{G_1}(n,m)\dot{\vee}G_2 has p1n+q1m+p2p_1n+q_1m+p_2 vertices and p2+p1np2+(p1+q1)mnp_2+p_1np_2+(p_1+q_1)mn edges.

Example 1.2. Let G1=K2G_1=K_2 and G2=C3G_2=C_3. Then, SK2(2,2)∨˙C3S_{K_2}(2,2)\dot{\vee}C_3 is depicted in Figure 1.

Figure 1. SK2(2,2)∨˙K2S_{K_2}(2,2)\dot{\vee}K_2

Definition 1.3. The generalized subdivision edge join SG1(n,m)∨G2S_{G_1}(n,m)\vee G_2 is the graph obtained from SG1(n,m)S_{G_1}(n,m) and G2G_2 by joining each vertex of E(G1)×{1,2,…,m}E(G_1)\times\{1,2,\ldots,m\} to every vertex of V(G2)V(G_2).

Note that, if GiG_i is a graph on pip_i vertices and qiq_i edges, i=1,2i=1,2, then SG1(n,m)∨G2S_{G_1}(n,m)\vee G_2 has p1n+q1m+p2p_1n+q_1m+p_2 vertices and p2+q1mp2+(p1+q1)mnp_2+q_1mp_2+(p_1+q_1)mn edges.

Example 1.4. Let G1=K2G_1=K_2 and G2=C3G_2=C_3. Then, SK2(2,2)∨C3S_{K_2}(2,2)\vee C_3 is depicted in Figure 2.

Figure 2. SK2(2,2)∨K2S_{K_2}(2,2)\vee K_2

Two non-isomorphic graphs of the same order are cospectral (respectively, DD-cospectral) if they have the same adjacency spectrum (respectively, DD-spectrum). Non-isomorphic, non-cospectral (respectively, non DD-cospectral) graphs of the same order are equienergetic (respectively, distance equienergetic) if their adjacency energies (respectively, distance energies) are the same. The construction of non-isomorphic equienergetic graphs with respect to various graph matrices is an important problem in spectral graph theory. In particular, several constructions of equienergetic and distance equienergetic graphs have been investigated in the literature; see [9, 10, 13, 14, 11]. In this work, we investigate the distance spectra of generalized subdivision vertex (respectively, edge) join of regular graphs. In particular, we derive new spectral results that encompass the main results of Indulal et al. (2019) [6] as special cases. In this work, we study the distance spectra of generalized subdivision vertex (respectively, edge) join of regular graphs. Our results generalize the main results of Indulal et al. (2019) [6]. Furthermore, using these results, we construct families of non-DD-cospectral DD-equienergetic graphs with diameter 4.

This article is organized as follows: Section 2 presents the preliminaries and notations used throughout. In Section 3, we present the distance spectra of the class of graphs obtained by the generalized subdivision vertex (respectively, edge) join of regular graphs. Finally, in Section 4, we construct families of DD-equienergetic and DD-cospectral graphs of diameter 4.

Preliminaries

References

  1. [1]Mustapha Aouchiche and Pierre Hansen. Distance spectra of graphs: a survey. _Linear Algebra Appl._, 458:301–386, 2014.
  2. [2]K Balasubramanian. Computer generation of distance polynomials of graphs. _J. Comput. Chem._, 11(7):829–836, 1990.DOI
  3. [3]Andries E Brouwer and Willem H Haemers. Spectra of graphs. _Springer Science & Business Media_, 2011.
  4. [4]Dragoš M. Cvetković, Michael Doob, and Horst Sachs. Spectra of graphs. Theory and application. _vol. 87, Academic Press, Inc, New York-London_, 1980.
  5. [5]R. L. Graham and H. O. Pollak. On the addressing problem for loop switching. _Bell Syst. Tech. J._, 50:2495–2519, 1971.DOI
  6. [6]Gopalapilla Indulal, Deena C. Scaria, and Xiaogang Liu. The distance spectrum of the subdivision vertex join and subdivision edge join of two regular graphs. _DML, Discrete Math. Lett._, 1:36–41, 2019.
  7. [7]Gopalapillai Indulal. Spectrum of two new joins of graphs and infinite families of integral graphs. _Kragujevac J. Math._, 36(1):133–139, 2012.
  8. [8]Gopalapillai Indulal, Ivan Gutman, and Ambat Vijayakumar. On distance energy of graphs. MATCH Commun. Math. Comput. Chem, 60(2):461–472, 2008.
  9. [9]B. J. Manjunatha, B. R. Rakshith, and R. G. Veeresha. Distance equienergetic graphs of diameter 4. Ex. Counterex., 7:3, 2025. Id/No 100184.DOI
  10. [10]H. S. Ramane, B. Parvathalu, K. Ashoka, and S. Pirzada. On families of graphs which are both adjacency equienergetic and distance equienergetic. Indian J. Pure Appl. Math., 55(1):198–209, 2024.
  11. [11]H. S. Ramane, Daneshwari Patil, B. Parvathalu, and K. Ashoka. Construction of distance equienergetic graphs through generalized composition. J. Adv. Math. Stud., 13(1):35–41, 2020.
  12. [12]Tahir Shamsher and S. Pirzada. Eigenvalues of the generalized subdivision graph with applications to graph energy. Discrete Math. Algorithms Appl., 16(8):14, 2024. Id/No 2350115.DOI
  13. [13]Dragan Stevanovic and Gopalapillai Indulal. The distance spectrum and energy of the compositions of regular graphs. Appl. Math. Lett., 22(7):1136–1140, 2009.DOI
  14. [14]Liang Wen Tang, Juan Liu, and Shuangwei Qin. Construction of equienergetic trees. MATCH Commun. Math. Comput. Chem., 91(2):485–488, 2024.DOI

Paper details

vlnc:W_7nxd48mk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents