Degree Subtraction Adjacency Eigenvalues and Energy of Graphs Obtained From Regular Graphs

1. Introduction

Let \(G\) be a simple, undirected graph with vertex set \(V(G) = \{v_1, v_2, \ldots, v_n\}\) and edge set \(E(G) = \{e_1, e_2, \ldots, e_m\}\). The degree of a vertex \(v_i\) denoted by \(d_{G}(v_i)\) is the number of edges incident to it. If all vertices have same degree equal to \(r\) then \(G\) is called an \(r\)-regular graph.

The adjacency matrix of \(G\) is a square matrix of order \(n\), defined as \(A=A(G)=[a_{ij}]\), where \(a_{ij}=1\) if \(v_i\) is adjacent to \(v_j\) and \(a_{ij}=0\), otherwise. The characteristic polynomial of \(A(G)\) is denoted by \(\phi(G:\lambda)\), that is, \(\phi(G:\lambda)= \det|\lambda I-A(G)|\), where \(I\) is an identity matrix. The characteristic polynomial of the adjacency matrix of a complete graph \(K_n\) is \(\phi(K_n : \lambda) = (\lambda – n + 1)(\lambda + 1)^{n-1}\). The roots of the equation \(\phi(G:\lambda)=0\) are called the adjacency eigenvalues of \(G\) [1] and they are denoted by \(\lambda_{1}, \lambda_{2}, \ldots, \lambda_{n}\). Two non-isomorphic graphs are said to be cospectral if they have same eigenvalues. For any graph \(G\), \(-\Delta\leq \lambda_{i} \leq \Delta\), where \(\Delta\) is the maximum degree. Thus for an \(r\)-regular graph, \(\lambda_{i}+ r\geq 0\) for \(i= 1, 2, \ldots, n\).

The vertex-edge incidence matrix of \(G\) is defined as \(B=B(G)=[b_{ij}]\), where \(b_{ij}=1\) if the vertex \(v_i\) is incident to an edge \(e_j\) and \(b_{ij}=0\), otherwise.

It is easy to observe that [1] $$BB^T=A+D,$$ where \(D= \text{diag} [d_G(v_1), d_G(v_2), \ldots, d_G(v_n)]\) is a diagonal degree matrix of \(G\) and \(B^T\) is the transpose of \(B\). If \(G\) is an \(r\)-regular graph, then The other matrices of a graph exists in the literature such as distance matrix [2], Laplacian matrix [3], Laplacian distance matrix [4], sum-eccentricity matrix [5, 6], degree sum matrix [7, 8], degree sum adjacency matrix [9], Zagreb matrix [10], degree subtraction matrix [11], degree product matrix [12], degree square sum matrix [13] and average-degree eccentricity matrix [14]. In [15] the degree subtraction adjacency (DSA) matrix is defined as \(DSA(G)=[d_{ij}]\), where \[ d_{ij} = \left\{ \begin{array}{ll} d_{G}(v_i)- d_{G}(v_j), & \text{if $v_i$ is adjacent to $v_j$} \\ 0, & \text{otherwise}. \end{array} \right. \] The characteristic polynomial of \(DSA(G)\) is called the \(DSA\)-polynomial and is denoted by \(\psi(G:\xi)\). Thus \(\psi(G:\xi) = \det(\xi I-DSA(G))\), where \(I\) is an identity matrix of order \(n\). For any regular graph of order \(n\), \(\psi(G:\xi)=\xi^n\). The line graph \(L(G)\) of a regular graph is regular. Hence \(\psi(L(G):\xi)=\xi^m\), where \(m\) is the number of edges of \(G\). The eigenvalues of \(DSA(G)\), denoted by \(\xi_1, \xi_2, \ldots, \xi_n\) are called DSA-eigenvalues of \(G\). Two non-isomorphic graphs are said to be DSA-cospectral if they have same DSA-eigenvalues. Since \(DSA(G)\) is a skew-symmetric matrix, its eigenvalues are purely imaginary or zero. The DSA-energy of a graph \(G\) is defined as The Eq. (2) is analogous to the ordinary graph energy defined as [16] $$E_A(G)=\sum_{i=1}^{n}|\lambda_i|,$$ where \(\lambda_1, \lambda_2, \ldots, \lambda_n\) are the adjacency eigenvalues of \(G\). The ordinary graph energy is well studied by many researchers [17]. In [15] the DSA-polynomial and DSA-energy of a path, complete bipartite graph, wheel, windmill graph and corona graph have been obtained. In this paper we obtain the DSA-eigenvalues and DSA-energy of subdivision graph, semitotal point graph, semitotal line graph and of toal graph of regular graphs.

2. DSA-eigenvalues

A subdivision graph of \(G\) is a graph \(S(G)\) obtained from \(G\) by inserting a new vertex on each edge of \(G\) [18]. Thus if \(G\) has \(n\) vertices and \(m\) edges, then \(S(G)\) has \(n+m\) vertices and \(2m\) edges. If \(u\in V(G)\) then \(d_{S(G)}(u)= d_{G}(u)\) and if \(v\) is subdivided vertex then \(d_{S(G)}(v)= 2\).

Lemma 2.1. If \(M\) is a non-singular matrix, then we have \[ \left| \begin{array}{cc} M & N \\ P & Q \end{array}\right| = |M||Q-PM^{-1}N|. \]

Theorem 2.2. Let \(G\) be an \(r\)-regular graph on \(n\) vertices and \(m\) edges. Then \[ \psi(S(G):\xi) = \left\{\begin{array}{ll} \xi^{\frac{n}{2}}(\xi^2+2)^{\frac{n}{2}}, & \mathrm{if} \hspace{4mm} r= 1 \\[2mm] \xi^{2n}, & \mathrm{if} \hspace{4mm} r = 2\\[2mm] (-1)^{n} (r-2)^{2n} \xi^{m-n} \phi\left(G: \frac{-\xi^2-r(r-2)^{2}}{(r-2)^2}\right), & \mathrm{if} \hspace{4mm} r \geq 3. \end{array} \right. \]

Proof. (i) If \(r=1\), then \(G\) is a union of \(k \geq 1\) edges. Thus \(G\) has \(n=2k\) vertices and \(k\) edges. The vertices of \(S(G)\) can be labeled in such a way that \[ DSA(S(G)) = \left[ \begin{array}{cc} O & B^T \\ -B & O \end{array}\right], \] where \(B\) is vertex-edge incidence matrix of \(G\) and \(O\) is zero matrix. Therefore by Lemma 2.1 and Eq.(1) \begin{eqnarray*} \psi(S(G) : \xi) & = & \left|\begin{array}{cc}\xi I_m & – B^T \\ B & \xi I_n \\ \end{array}\right|\\ & = & \xi^m \left|\xi I_{n} + B \frac{I_{m}}{\xi} B^T \right| \\ & = & \xi^{m-n} \left|\xi^2 I_{n} + BB^T \right| \\ & = & \xi^{m-n} \left|\xi^2 I_{n} + A + rI_{n}\right| \\ & = & (-1)^n\xi^{m-n} \left|-(\xi^2 + r)I_{n} – A \right| \\ & = & (-1)^n\xi^{m-n} \phi(G: -(\xi^2 + r)) \\ & = & (-1)^{2k}\xi^{k-2k} \left((\xi^2+1)^2-1 \right)^{k}\\ & = & \xi^{k} (\xi^2+2)^{k} \\ & = & \xi^\frac{n}{2}(\xi^2+2)^\frac{n}{2}. \end{eqnarray*}

(ii) If \(r=2\), then each component of \(G\) is cycle. Therefore \(S(G)\) is \(2\)-regular graph on \(2n\) vertices. Hence \[ \psi(S(G):\xi)= \xi^{2n}. \]

(iii) Let \(r\geq 3\). The vertices of \(S(G)\) can be labeled in such a way that \[ DSA(S(G)) = \left[ \begin{array}{cc} O & (2-r) B^T \\ -(2-r)B & O \end{array}\right], \] where \(B\) is vertex-edge incidence matrix of \(G\) and \(O\) is zero matrix. Therefore by Lemma 2.1 and Eq.(1) \begin{eqnarray*} \psi(S(G) : \xi) & = & \left|\begin{array}{cc}\xi I_m & – (2-r)B^T \\ (2-r)B & \xi I_n \\ \end{array}\right|\\ & = & \xi^m \left|\xi I_{n} + (2-r)^2 B\frac{I_{m}}{\xi} B^T \right| \\ \nonumber & = & \xi^{m-n} \left|\xi^2 I_{n} + (r-2)^2(A+rI) \right| \\ & = & (-1)^n(r-2)^{2n}\xi^{m-n} \left|\left(\frac{-\xi^2-r(r-2)^2}{(r-2)^2}\right)I_n – A \right| \\ & = & (-1)^n(r-2)^{2n}\xi^{m-n} \phi\left(G: \frac{-\xi^2- r(r-2)^2}{(r-2)^2}\right). \end{eqnarray*}

By Theorem 2.2, we have following corollary.

Corollary 2.3. Let \(G\) be an \(r\)-regular graph on \(n\) vertices and \(m\) edges. Let \(\lambda_1, \lambda_2, \ldots, \lambda_n\) be the adjacency eigenvalues of \(G\) and \(\mathbf{i}=\sqrt{-1}\).

(i) If \(r=1\) then DSA-eigenvalues of \(S(G)\) are \(0\) (\(\frac{n}{2}\) times) and \(\pm \mathbf{i}\sqrt{2}\) (\(\frac{n}{2}\) times).

(ii) If \(r=2\) then DSA-eigenvalues of \(S(G)\) are all zeros.

(iii) If \(r\geq 3\) then DSA-eigenvalues of \(S(G)\) are \(0\) (\(m-n\) times) and \(\pm \mathbf{i}(r-2)\sqrt{r+\lambda_i}\), \(i=1, 2, \ldots, n\).

The semitotal pont graph of \(G\), denoted by \(T_{1}(G)\), is a graph with vertex set \(V(G)\cup E(G)\) and two vertices in \(T_{1}(G)\) are adjacent if they are adjacent vertices in \(G\) or one is a vertex and other is an edge incident to it in \(G\) [19]. Note that if \(u\in V(G)\) then \(d_{T_{1}(G)}(u)= 2 d_{G}(u)\) and if \(e\in E(G)\) then \(d_{T_{1}(G)}(e)= 2\).

Theorem 2.4. Let \(G\) be an \(r\)-regular graph on \(n\) vertices and \(m\) edges. Then \[ \psi(T_{1}(G):\xi) = \left\{\begin{array}{ll} \xi^{m+n}, & \mathrm{if} \hspace{4mm} r = 1\\[2mm] (-1)^n (2r-2)^{2n}\xi^{m-n} \phi\left(G: \frac{-\xi^2- r(2r-2)^2}{(2r-2)^2}\right), & \mathrm{if} \hspace{4mm} r\geq 2. \end{array} \right. \]

Proof. (i) If \(r=1\), then \(T_{1}(G)\) is a regular graph of degree two on \(m+n\) vertices. Hence \[ \psi(T_{1}(G):\xi) = \xi^{m+n}. \]

(ii) Let \(r \geq 2\). The vertices of \(T_1(G)\) can be labeled in such a way that \[ DSA(T_1(G)) = \left[\begin{array}{cc} O & (2-2r) B^T \\ -(2-2r)B & O \end{array}\right], \] where \(B\) is vertex-edge incidence matrix of \(G\) and \(O\) is a zero matrix. Therefore by Lemma 2.1, and Eq. (1) \begin{eqnarray*} \psi(T_1(G) : \xi) & = & \left|\begin{array}{cc}\xi I_m & – (2-2r)B^T \\ (2-2r)B & \xi I_n \\ \end{array}\right|\\ & = & \xi^m \left|\xi I_{n} + (2r-2)^2 B\frac{I_{m}}{\xi} B^T \right| \\ \nonumber & = & \xi^{m-n} \left|\xi^2 I_{n} + (2r-2)^2(A+rI) \right| \\ & = & (-1)^n(2r-2)^{2n}\xi^{m-n} \left|\left(\frac{-\xi^2-r(2r-2)^2}{(2r-2)^2}\right)I_n – A \right| \\ & = & (-1)^n(2r-2)^{2n}\xi^{m-n} \phi\left(G: \frac{-\xi^2- r(2r-2)^2}{(2r-2)^2} \right). \end{eqnarray*}

By Theorem 2.4, we have following corollary.

corollary 2.5. Let \(G\) be an \(r\)-regular graph on \(n\) vertices and \(m\) edges. Let \(\lambda_1, \lambda_2, \ldots, \lambda_n\) be the adjacency eigenvalues of \(G\) and \(\mathbf{i}=\sqrt{-1}\).

(i) If \(r=1\) then DSA-eigenvalues of \(T_1(G)\) are all zeros.

(ii) If \(r\geq 2\) then DSA-eigenvalues of \(T_1(G)\) are \(0\) (\(m-n\) times) and \(\pm \mathbf{i}(2r-2)\sqrt{r+\lambda_i}\), \(i=1, 2, \ldots, n\).

Semitotal line graph of \(G\), denoted by \(T_2(G)\), is a graph with vertex set \(V(G)\cup E(G)\) and two vertices in \(T_2(G)\) are adjacent if one is a vertex and other is an edge incident to it in \(G\) or both are edges adjacent in \(G\) [1]. Note that if \(u\in V(G)\) then \(d_{T_2(G)}(u)= d_{G}(u)\) and if \(e= uv \in E(G)\) then \(d_{T_2(G)}(e)= d_{G}(u)+d_{G}(v)\).

Theorem 2.6. Let \(G\) be an \(r\)-regular graph \((r\geq 1)\) on \(n\) vertices and \(m\) edges. Then \[ \psi(T_2(G) : \xi) = (-1)^n r^{2n}\xi^{m-n} \phi\left(G: \frac{-\xi^2- r^3}{r^2} \right). \]

Proof. The vertices of \(T_2(G)\) can be labeled in such a way that \[ DSA(T_2(G)) = \left[ \begin{array}{cc} O & r B^T \\ – rB & O \end{array}\right], \] where \(B\) is vertex-edge incidence matrix of \(G\) and \(O\) is a zero matrix. Therefore by Lemma 2.1 and Eq. (1) \begin{eqnarray*} \psi(T_2(G) : \xi) & = & \left|\begin{array}{cc}\xi I_m & – rB^T \\ rB & \xi I_n \\ \end{array}\right|\\ & = & \xi^m \left|\xi I_{n} + r^2 B\frac{I_{m}}{\xi} B^T \right| \\ \nonumber & = & \xi^{m-n} \left|\xi^2 I_{n} + r^2(A+rI) \right| \\ & = & (-1)^n r^{2n}\xi^{m-n}\left |\left(\frac{-\xi^2-r^3}{r^2}\right)I_n – A \right| \\ & = & (-1)^n r^{2n}\xi^{m-n} \phi\left(G: \frac{-\xi^2 – r^3}{r^2} \right). \end{eqnarray*}

By Theorem 2.6, we have following corollary.

Corollary 2.7. Let \(G\) be an \(r\)-regular graph \((r\geq 1)\) on \(n\) verties and \(m\) edges. Let \(\lambda_1, \lambda_2, \ldots, \lambda_n\) be the adjacency eigenvalues of \(G\) and \(\mathbf{i}=\sqrt{-1}\). Then DSA-eigenvalues of \(T_2(G)\) are \(0\) (\(m-n\) times) and \(\pm \mathbf{i}r\sqrt{r+\lambda_{i}}\), \(i=1, 2, \ldots, n\).

Total graph of \(G\), denoted by \(T(G)\), is a graph with vertex set \(V(G)\cup E(G)\) and two vertices in \(T(G)\) are adjacent if and only if they are adjacent vertics of \(G\) or adjacent edges of \(G\) or one is a vertex and other is an edge incident to it in \(G\) [18]. Total graph of a regular graph is regular. Hence if \(G\) is regular, then \[ \psi(T(G): \xi) = \xi^{m+n}. \] Two different graphs having same eigenvalues are called cospectral. If \(G_1\) and \(G_2\) are adjacency cospectral graphs with same regularity, then by Corollaries 2.3, 2.5, and 2.7, the graphs \(S(G_1)\) and \(S(G_2)\); \(T_1(G_1)\) and \(T_1(G_2)\); \(T_2(G_1)\) and \(T_2(G_2)\) form a pair of DSA-cospectral graphs.

3. DSA-energy

By Corollaries 2.3, 2.5, and 2.7 and by Eq. (2) we get the following proposition.

Proposition 3.1. Let \(G\) be an \(r\)-regular graph on \(n\) vertices and \(m\) edges. Let \(\lambda_1, \lambda_2, \ldots, \lambda_n\) be the adjacency eigenvalues of \(G\). Then

(i) \[ DSAE(S(G)) = \left\{\begin{array}{ll} n\sqrt{2}, & \mathrm{if} \hspace{4mm} r= 1 \\[2mm] 0, & \mathrm{if} \hspace{4mm} r = 2\\[2mm] 2(r-2)\sum\limits_{i=1}^{n}\sqrt{r+\lambda_{i}}, & \mathrm{if} \hspace{4mm} r \geq 3. \end{array} \right. \]

(ii) \[ DSAE(T_1(G)) = \left\{\begin{array}{ll} 0, & \mathrm{if} \hspace{4mm} r= 1 \\[2mm] 2(2r-2)\sum\limits_{i=1}^{n}\sqrt{r+\lambda_{i}}, & \mathrm{if} \hspace{4mm} r \geq 2. \end{array} \right. \]

(iii) \(DSAE(T_2(G)) = 2r\sum\limits_{i=1}^{n}\sqrt{r+\lambda_{i}}\) for \(r \geq 1\).

(iv) \(DSAE(T(G))= 0\) for \(r\geq 1\).

By Proposition 3.1 we have following result.

Proposition 3.2. If \(G\) is an \(r\)-regular graph \((r\geq 3)\) on \(n\) vertices, then

(i) \((2r-2) DSAE(S(G)) = (r-2) DSAE(T_1(G))\);

(ii) \(r DSAE(S(G)) = (r-2) DSAE(T_2(G))\);

(iii) \(r DSAE(T_1(G)) = (2r-2) DSAE(T_2(G))\).

Proposition 3.3. Let \(G\) be an \(r\)-regular graph \((r\geq 3)\) on \(n\) vertices. Then $$DSAE(S(G)) < DSAE(T_2(G)) < DSAE(T_1(G)).$$

Proof. For \(r\geq 3\), we see that $$r-2 < r < 2r-2.$$ Hence by Proposition 3.2, this implies $$DSAE(S(G)) < DSAE(T_2(G)) < DSAE(T_1(G)).$$

Competing Interests

The authors declare that they have no competing interests.