Let \(G\) be a graph with vertex set \(V(G) = \{v_1, v_2, \dots, v_n\}\). We associate to \(G\), a matrix \(P(G)\) whose \((i, j)\)-th entry is the maximum number of vertex-disjoint paths between the corresponding vertices if \(i\neq j\), and is zero otherwise. We call this matrix the path matrix of \(G\), and its eigenvalues are referred to as the path eigenvalues of \(G\). In this paper, we investigate the path eigenvalues of graphs resulting from certain graph operations and specific graph families.
In this paper, we consider simple connected graphs. Let \(G\) be a graph with vertex set \(V(G) = \{v_1, v_2, \ldots, v_n\}\) and edge set \(E(G)\). For each vertex \(v_i\), let \(d_i\) denote its degree, where \(i = 1, 2, \ldots, n\). The adjacency matrix \(A(G) = [a_{ij}]\) of \(G\) is a square matrix of size \(n \times n\), defined as:
\[a_{ij} = \begin{cases} 1, & \text{if vertices } v_i \text{ and } v_j \text{ are adjacent}, \\ 0, & \text{otherwise}. \end{cases}\]
Since \(A(G)\) is symmetric, all its eigenvalues \(\mu_1, \mu_2, \ldots, \mu_n\) are real, and their sum is zero because all the diagonal entries of \(A(G)\) are zero.
The concept of graph energy was introduced by Gutman [3], where the energy of a graph \(E(G)\) is defined as:
\[E(G) = \sum_{i=1}^n |\mu_i|.\]
The eigenvalues \(\mu_1,\mu_2,…,\mu_n\) of the graph \(G\) are defined as the eigenvalues of its adjacency matrix \(A(G).\) If \(\mu_1,\mu_2,…,\mu_t\) are the distinct eigenvalues of \(G\), the spectrum of \(G\) can be written as
\[Spec(G)=\left(\begin{array}{cccc}\mu_1&\mu_2&…&\mu_t\\m_1&m_2&…&m_t\end{array}\right),\] where \(m_j\) indicates the algebraic multiplicity of the eigenvalue \(\mu_j,1\leq j\leq t\) of \(G.\)
Let \(G\) be a simple graph with a vertex set \(V(G) = \{v_1, v_2, \dots, v_n\}\). Define the path matrix \(P = (p_{ij})\), an \(n \times n\) matrix as follows:
\[p_{ij} = \begin{cases} \text{maximum number of vertex-disjoint paths from } v_i \text{ to } v_j, & \text{if } i \neq j, \\ 0, & \text{if } i = j. \end{cases}\]
The matrix \(P = P(G)\) is called the path matrix of the graph \(G\). Since \(P\) is real and symmetric, all its eigenvalues are real. The eigenvalues of \(P(G)\) are the path eigenvalues of G. Patekar and Shikare introduced path matrix in their paper [9] and studied the path eigenvalues of certain class of graphs such as complete graphs, trees, cycles, bipartite graphs etc and their properties.
This setup connects the spectral properties of the path matrix to the graph’s structure, particularly focusing on vertex-disjoint paths, and provides insights into graph connectivity and related properties.The path matrix is a useful tool for analysing connectivity, durability, and routing in a variety of graph-modeled systems. By concentrating on vertex-disjoint paths, it promotes the structural independence of connections, which makes it especially relevant in scenarios where node failure or independence is important.
The concept of path energy was introduced in [1] by Akbari et al. In [1], the path energy of a graph is defined as the sum of the absolute values of its path eigenvalues and analyze spectral properties for various graph classes.
The path energy \(PE(G)\) is expressed as:
\[PE(G) = \sum_{i=1}^n |\lambda_i|,\] where \(\lambda_i\)’s are the eigenvalues of the path matrix \(P(G)\). In [8], Aleksandar and Milan proved that for a connected graph \(G\) of order n, \(\mathrm{PE}(G) \geq 2(n – 1)\) and \(\mathrm{PE}(G) \leq 2(n – 1)^2\) and they have characterised the graphs for which this bound is attained. Also, they have studied the path energy of unicyclic graphs.
Throughout this paper, \(I_{n}\) denotes identity matrix of order \(n\) and \(J_{m\times n}\), \(J_{n}\) respectively denotes matrix of order \(m\times n\) and matrix of order \(n\) with all its entries are one.
The purpose of this paper is to study the eigenvalues of path matrices under certain graph operations such as splitting graph, shadow graph, duplicate graph and in specific graph families.
In this section, we recall the concepts of some graph operations and list some results that will be used in the subsequent sections.
Let \(A = [a_{ij}]_{m \times n}\) and \(B = [b_{ij}]_{p \times q}\) be two matrices, then the Kronecker product of \(A\) and \(B\) is defined in [7] as the matrix
\[A \otimes B = \left[\begin{array}{lllll} a_{11}B & a_{12}B & a_{13}B & \dots & a_{1n}B \\ a_{21}B & a_{22}B & a_{23}B & \dots & a_{2n}B \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{m1}B & a_{m2}B & a_{m3}B & \dots & a_{mn}B \end{array}\right].\]
Result 2.1. Let \(A = [a_{ij}]_{m \times m}\) and \(B = [b_{ij}]_{n \times n}\). Also, let \(\alpha\) be an eigenvalue of the matrix \(A\) with corresponding eigenvector \(y\), and \(\beta\) be an eigenvalue of the matrix \(B\) with corresponding eigenvector \(z\). Then, \(\alpha \beta\) is an eigenvalue of \(A \otimes B\) with corresponding eigenvector \(y \otimes z\) [7].
Result 2.1.Let \[M = \begin{bmatrix} (\beta + a)I_{n_1} – a J_{n_1} & -c J_{n_1 \times n_2} \\ -d J_{n_2 \times n_1} & (\beta + b)I_{n_2} – b J_{n_2} \end{bmatrix}\] where, \(I_{n_1}\) and \(I_{n_2}\) are identity matrices of order \(n_1\) and \(n_2\), respectively. \(J_{n_1}\) and \(J_{n_2}\) are matrices of all ones of order \(n_1\) and \(n_2\), respectively. \(J_{n_1 \times n_2}\) and \(J_{n_2 \times n_1}\) are matrices of all ones with dimensions \(n_1 \times n_2\) and \(n_2 \times n_1\), respectively. \(a\), \(b\), \(c\), \(d\), and \(\beta\) are real numbers. The determinant of \(M\) = \((\beta + a)^{n_1 – 1} (\beta + b)^{n_2 – 1} \left( \big[\beta – (n_1 – 1)a\big] \big[\beta – (n_2 – 1)b\big] – n_1 n_2 cd \right)\) [10].
Graph operations are operations using which we can produce new graphs from the given graph. There are several graph operations. We mainly focus on shadow graph, splitting graph and duplicate graph.
Definition 2.3. The \(\textit{shadow graph}\) \(D_2(G)\) of a connected graph \(G\) is constructed by taking two copies of \(G\), say \(G'\) and \(G''\). Join each vertex \(u'\) in \(G'\) to the neighbours of the corresponding vertex \(u''\) in \(G''\).
The \(\textit{ m -shadow graph}\) \(D_m(G)\) of a connected graph \(G\) is constructed by taking \(m\) copies of \(G\), say \(G_1, G_2, \dots, G_m\). Then join each vertex \(u\) in \(G_i\) to the neighbours of the corresponding vertex \(v\) in \(G_j\), where \(1 \leq i, j \leq m\) [13].
Definition 2.4. For a graph \(G\), the \(\textit{splitting graph}\) \(Spl(G)\) is obtained by taking a new vertex \(v^{'}\) corresponding to each vertex \(v\) of the graph \(G\) and then joining \(v^{'}\)to all vertices of \(G\) that are adjacent to \(v\) [12].
The \(\textit{ m -splitting graph}, \text{Spl}_m(G)\) of a graph \(G\) is obtained by adding to each vertex \(v\) of \(G\) new \(m\) vertices, say \(v_1, v_2, v_3, \dots, v_m\), such that \(v_i\), \(1 \leq i \leq m\), is adjacent to each vertex that is adjacent to \(v\) in \(G\) [13].
Definition 2.5. Let \(G = (V, E)\) be a simple \((p, q)\) graph with vertex set \(V\) and edge set \(E\). Let \(V'\) be a set such that \(V \cap V' = \emptyset\), \(|V| = |V'|\), and \(f : V \to V'\) be bijective (for \(a \in V\), we write \(f(a)\) as \(a'\) for convenience). The duplicate graph of \(G\) is \(DG = (V_1, E_1)\), where the vertex set \(V_1 = V \cup V'\) and the edge set \(E_1\) of \(DG\) is defined as follows: The edge \(ab\) is in \(E\) if and only if both \(ab'\) and \(a'b\) are in \(E_1\). Then we have \(D^2G=D(DG), D^nG=D(D^{n-1}G)\). Then \(D^nG\) is called \(\textit{n-duplicate graph}\) of G [11].
Result 2.6. For a connected graph \(G\), \(nG\) is the graph having \(n\) components, each being isomorphic to \(G\). For a connected graph \(G\), \(D(G)=2G\) if and only if \(G\) has no odd cycles [11].
Result 2.7. If \(n \geq 3\) is odd , \(\text{DC}_n = \text{C}_{2n}\) [11].
Result 2.8. For a connected graph G and any integer \(n \geq 1\), \(D^nG=2^{n-1}DG\) if G has an odd cycle and \(D^nG=2^{n}G\) if G has no odd cycles [11].
A group of graphs that adhere to the same pattern or rule is known as a graph family. There are so many well known graph families in literature. Here, we consider the graph families namely subdivision graph, thorn graph, tadpole graph, crown graph and gear graph.
Definition 2.9. The t-subdivision graph \(S_t(G)\) of a graph G is the graph obtained by replacing each edge of G with a path of length t [5].
Definition 2.10. The subdivision graph \(S(G)\) of a graph G is the graph obtained by inserting a new vertex on each edge of G [6].
Definition 2.11. The thorn graph \(G^{+t}\) is a graph obtained from the graph G by attaching \(t (t \geq 1)\) pendant edges to each vertex of G. If G is a graph of order n and size m, then \(G^{+t}\) is graph of order \(n + nt\) and size \(m + nt\) [4].
Definition 2.12. The tadpole graph \(T_{n,k}\) is a graph formed by connecting one endpoint of a path of length \(k\) to a vertex of an \(n\)-cycle [2].
Definition 2.13. A cycle \(C_n\) with a pendant edge attached to each of its vertices is called a crown graph \(CW_n\) [2].
Definition 2.14. The gear graph \(G_n\) is obtained from the wheel graph \(W_n\) by inserting a vertex between each pair of adjacent vertices in the \(n\)-cycle [2].
In this section, we find the path eigenvalues and path energy of shadow graph, splitting graph and duplicate graph.
Theorem 3.1. Let G be a k-regular simple graph with n vertices having vertex connectivity k. Then, the path eigenvalues of its m-shadow graph \(D_m(G)\) are given by \(mk(mn-1)\) with mulitiplicity 1 and \(-mk\) with multiplicity \(mn-1\).
Proof. Let \(v_1, v_2, \dots, v_n\) be the vertices of the graph G. Then its path matrix is given by
\[P(G)= \begin{bmatrix} 0 & k &k& \dots & k \\ k & 0 &k& \dots & k\\ \vdots & \vdots & \ddots & \vdots \\ k & k &k& \dots & 0 \end{bmatrix}_{n} .\)
Then the path matrix of its \(m\)-shadow graph \(D_m(G)\] will be
\[P(D_m(G) )= \begin{bmatrix} 0 & mk &mk& \dots & mk \\ mk & 0 &mk& \dots & mk\\ \vdots & \vdots & \ddots & \vdots \\ mk & mk &mk& \dots & 0 \end{bmatrix}_{mn} =mk J_{mn}-mk I_{mn}\].
Then the path eigenvalues of its m-shadow graph \(D_m(G)\) is given by \(mk(mn-1)\) with mulitiplicity 1 and \(-mk\) with multiplicity \(mn-1\) \[Spec(D_m(G))=\left(\begin{array}{cccc} mk(mn-1)&-mk\\1&mn-1\end{array}\right).\] ◻
Corollary 3.2. Let G be a k-regular graph with n vertices having vertex connectivity k.Then, the path eigenvalues of its shadow graph \(D_2(G)\) are given by \(2k(2n-1)\) with mulitiplicity 1 and \(-2k\) with multiplicity \(2n-1\).
Theorem 3.3. Let \(K_n\) be a complete graph with n vertices.Then, the path eigenvalues of its splitting graph \(Spl(K_n)\) are \(3-2n\) repeating \(n-1\) times, \(1-n\) repeating \(n-1\) times and the remaining two eigenvalues are the roots of the equation \(( [\lambda – (n – 1)(2n-3)] [\lambda – (n – 1)(n-1)] – n^2(n-1)^2)=0\).
Proof. The path matrix of splitting graph of \(K_n\) is
\[P(Spl(K_n))= \begin{bmatrix} (2n-3)J_n-(2n-3)I_n & (n-1)J_n\\ (n-1)J_n & (n-1)J_n-(n-1)I_n \end{bmatrix}_{2n},\]
where J is matrix of all 1’s. By applying Result 2.2, we have
\[\begin{aligned} \left| \lambda I_{n} -P(Spl(K_n)) \right| =& \begin{vmatrix} (\lambda +(2n-3))I_n – (2n-3)J_n & -(n-1) J_n\\ -(n-1) J_n &(\lambda+(n-1))I_n-(n-1)J_n \end{vmatrix} \\[3mm] =&(\lambda + (2n-3))^{n – 1} (\lambda + (n-1))^{n – 1} ( [\lambda – (n – 1)(2n-3)]\\ &\times [\lambda – (n – 1)(n-1)] – n^2(n-1)^2). \end{aligned}\]
Therefore, the path eigenvalues of splitting graph \(Spl(K_n)\) are \(3-2n\) with multiplicity \(n-1\) , \(1-n\) with multiplicity \(n-1\) and the remaining two eigenvalues are the roots of the equation \(( [\lambda – (n – 1)(2n-3)] [\lambda – (n – 1)(n-1)] – n^2(n-1)^2)=0\). ◻
Theorem 3.4. Let \(C_n\) be a cycle with n vertices. Then, the path spectrum of its splitting graph \(Spl(C_n)\) is \(-4\) repeating \(n-1\) times, \(-2\) repeating \(n-1\) times and the remaining two eigenvalues are the roots of the equation \(( [\lambda – 4(n – 1)] [\lambda – 2(n – 1)] – 4n^2)=0\).
Proof. The path matrix of splitting graph of \(C_n\) is
\[P(Spl(C_n))= \begin{bmatrix} 4J_n-4I_n & 2J_n\\ 2J_n & 2J_n-2I_n \end{bmatrix}_{2n},\]
where J is matrix of all 1’s. By applying Result 2.2, we have
\[\begin{aligned} \left| \lambda I_{n} -P(Spl(C_n)) \right| &= \begin{vmatrix} (\lambda +4)I_n – 4J_n & -2 J_n\\ -2 J_n &(\lambda+2)I_n-2J_n \end{vmatrix}\\ &=(\lambda + 4)^{n – 1} (\lambda + 2)^{n – 1} ( [\lambda – 4(n – 1)] [\lambda – 2(n – 1)] – 4n^2). \end{aligned}\]
Hence, the path spectrum of splitting graph \(Spl(C_n)\) is \(-4\) repeating \(n-1\) times, \(-2\) repeating \(n-1\) times and the remaining two eigenvalues are the roots of the equation \(( [\lambda – 4(n – 1)] [\lambda – 2(n – 1)] – 4n^2)=0\). ◻
In the following theorems, we find the relation between the path energy of m-duplicate graph of a graph and the path energy of the original graph.
Theorem 3.5. Let G be a connected graph with n vertices and no odd cycles. Then the path energy of its m-duplicate graph \(D^mG\) is \(PE(D^mG)=2^mPE(G)\).
Proof. Since G is a connected graph with n vertices having no odd cycles, we have \(D^mG=2^mG\). Then the path matrix of \(D^mG\) is
\[P(D^mG )= \begin{bmatrix} P(G) & 0 &0& \dots &0\\ 0 & P(G) &0& \dots & 0\\ \vdots & \vdots & \ddots & \vdots \\ 0& 0 &0& \dots &P(G) \end{bmatrix}_{2^mn} = \begin{bmatrix} 1 & 0 &0& \dots &0\\ 0 & 1 &0& \dots & 0\\ \vdots & \vdots & \ddots & \vdots \\ 0& 0 &0& \dots &1 \end{bmatrix}_{2^m}\otimes P(G).\]
By using Result 2.1, the path energy of its m-duplicate graph is \(PE(D^mG)=2^mPE(G)\). ◻
Corollary 3.6. Let G be a connected graph with n vertices and contains no odd cycles. Then we have \(PE(DG)=2PE(G)\).
Theorem 3.7. Let G be a connected graph with n vertices and contains odd cycles. Then the path energy of its m-duplicate graph \(D^mG\) is \(PE(D^mG)=2^mPE(DG)\).
Proof. Since G is a connected graph with n vertices having odd cycles, we have \(D^mG=2^{m-1} DG\), where \(DG\) represents the duplicate graph of \(G\).Then the path matrix of \(D^mG\) is \[\begin{aligned} P(D^mG )= &\begin{bmatrix} P(DG) & 0 &0& \dots &0\\ 0 & P(DG) &0& \dots & 0\\ \vdots & \vdots & \ddots & \vdots \\ 0& 0 &0& \dots &P(DG) \end{bmatrix}_{2^{m}n}\\=& \begin{bmatrix} 1 & 0 &0& \dots &0\\ 0 & 1 &0& \dots & 0\\ \vdots & \vdots & \ddots & \vdots \\ 0& 0 &0& \dots &1 \end{bmatrix}_{2^{m-1}}\otimes P(DG). \end{aligned}\]
By using Result 2.1, we obtain the path energy of m-duplicate graph \(D^mG\) as \(PE(D^mG)\\=2^{m-1}PE(DG)\). ◻
Theorem 3.8. Let \(K_n\) be a complete graph with n vertices. Then the path eigenvalues of its duplicate graph \(DK_n\) are given by \((n-1)(2n-1)\) with mulitiplicity 1 and \(-(n-1)\) with multiplicity \(2n-1\).
Proof. Let \(v_1, v_2, \dots, v_n\) be the vertices of the graph G. Then its path matrix is given by
\[P(K_n)= \begin{bmatrix} 0 & n-1 &n-1& \dots & n-1 \\ n-1 & 0 &n-1& \dots & n-1\\ \vdots & \vdots & \ddots & \vdots \\ n-1 & n-1 &n-1& \dots & 0 \end{bmatrix}_{n}\).
Then the path matrix of its duplicate graph \(DG\] is
\[P(DK_n)= \begin{bmatrix} 0 & n-1 &n-1& \dots & n-1 \\ n-1 & 0 &n-1& \dots & n-1\\ \vdots & \vdots & \ddots & \vdots \\ n-1 & n-1 &n-1& \dots & 0 \end{bmatrix}_{2n} =(n-1) J_{2n}-(n-1)I_{2n}\],
where \(J_{2n}\) is a \(2n \times 2n\) matrix with all its entries are unity. Then the path eigenvalues of its duplicate graph \(DK_n\) are given by \((n-1)(2n-1)\) with mulitiplicity 1 and \(-(n-1)\) with multiplicity \(2n-1.\) \[Spec(DK_n))=\left(\begin{array}{cccc} (n-1)(2n-1)&-(n-1)\\1&2n-1\end{array}\right).\] ◻
Theorem 3.9. Let \(C_n\) be a cycle of even length with n vertices, \(n \geq 4\). Then the path eigenvalues of its duplicate graph \(DC_n\) are given by \(2(n-1)\) with mulitiplicity 2 and \(-2\) with multiplicity \(2n-2.\)
Proof. Let \(v_1, v_2, \dots, v_n\) be the vertices of the graph G.Then the path matrix of \(C_n\) is given by
\[P(C_n)= \begin{bmatrix} 0 & 2 &2& \dots & 2 \\ 2 & 0 &2& \dots & 2\\ \vdots & \vdots & \ddots & \vdots \\ 2& 2 &2& \dots & 0 \end{bmatrix}_{n}.\]
Since \(C_n\) is an even cycle, we have \(DC_n=2C_n\) . Then the path matrix of its duplicate graph \(DC_n\) is given by
\[P(DC_n)= \begin{bmatrix} P(C_n) & 0\\ 0 & P(C_n) \end{bmatrix}_{2n} =\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \otimes P(C_n).\]
The eigenvalues of the matrix \(\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\) is 1 with multiplicity 2 and the eigenvalues of \(P(C_n)\) are \(2(n-1)\) with multiplicity 1 and \(-2\) with multiplicity \(n-1\)
By using Result 2.1, we obtain the path eigenvalues of its duplicate graph \(DC_n\) as \(2(n-1)\) with mulitiplicity 2 and \(-2\) with multiplicity \(2n-2.\)
\[Spec(DC_n)=\left(\begin{array}{cccc} 2(n-1)&-2\\2&2n-2\end{array}\right).\] ◻
Let \(C_n\) be a cycle with n vertices, \(n \geq 3\), is odd. Then the path eigenvalues of its duplicate graph \(DC_n\) are given by \(4n-2\) with multiplicity \(1\) and \(-2\) with multiplicity \(2n-1.\)
Proof. Let \(v_1, v_2, \dots, v_n\) be the vertices of the graph G.Then the path matrix of \(C_n\) is given by
\[P(C_n)= \begin{bmatrix} 0 & 2 &2& \dots & 2 \\ 2 & 0 &2& \dots & 2\\ \vdots & \vdots & \ddots & \vdots \\ 2& 2 &2& \dots & 0 \end{bmatrix}_{n}\].
Since \(n \geq 3\) is odd , \(\text{DC}_n = \text{C}_{2n}\).Then the path matrix of its duplicate graph is given by
\[P(DC_n)= \begin{bmatrix} 0 & 2 &2& \dots & 2 \\ 2 & 0 &2& \dots & 2\\ \vdots & \vdots & \ddots & \vdots \\ 2& 2 &2& \dots & 0 \end{bmatrix}_{2n}=2 J_{2n}-2 I_{2n}\].
Then the path eigenvalues are given by \(4n-2\) with multiplicity \(1\) and \(-2\) with multiplicity \(2n-1\)
\(Spec(DC_n)=\left(\begin{array}{cccc} 4n-2&-2\\1&2n-1\end{array}\right).\) ◻
In this section, we find the path eigenvalues of some graph families
such as subdivision graph, thorn graph, tadpole graph, crown graph and
gear graph.
The following theorem gives the path eigenvalues of t -subdivision graph
of a k-regular graph with connectivity k.
Theorem 4.1. Let G be an \(k\)-regular graph of order n and size m with connectivity \(k\). Then the path eigenvalues of its t-subdivision graph \(S_t(G)\) are given by \(-k\) repeating n-1 times, \(-2\) repeating mt-1 times and remaining two eigenvalues are the roots of the second degree equation \(( [\lambda – (n – 1)k] [\lambda – (mt – 1)2] – 4nmt)=0\).
Proof. Let G be a \(k\)-regular graph of order n with connectivity k. Then the t-subdivision graph \(S_t(G)\) of the graph G has two types of vertices. The n vertices are of degree k and the remaining mt vertices are of degree 2. Then the path matrix of \(S_t(G)\) is
\[P(S_t(G))= \begin{bmatrix} kJ_n-kI_n& 2 J_{nXmt} \\ 2 J_{mtXn}& 2 J_{mt}-2I_{mt} \end{bmatrix}_{n+mt},\]
where J is a matrix of all 1’s. By applying the Result 2.2, we have \[\begin{aligned} \left| \lambda I_{n} -P(S_t(G)) \right| = & \begin{vmatrix} (\lambda +k)I_n – kJ_n & -2 J_{nXmt}\\ -2 J_{mtXn} &(\lambda +2)I_{mt} – 2J_{mt} \end{vmatrix}\\ =&(\lambda + k)^{n – 1} (\lambda + 2)^{mt – 1} ( [\lambda – (n – 1)k] [\lambda – (mt – 1)2] – 4nmt). \end{aligned}\]
Hence, the path eigenvalues of t-subdivision graph \(S_t(G)\) are \(-k\) repeating n-1 times, \(-2\) repeating mt-1 times and remaining two eigenvalues are the roots of the second degree equation \(( [\lambda – (n – 1)k] [\lambda – (mt – 1)2] – 4nmt)=0\). ◻
Corollary 4.2. Let G be a k-regular graph of order n and size m with connectivity k. Then the path eigenvalues of its subdivision graph \(S(G)\) are given by \(-k\) repeating n-1 times, \(-2\) repeating m-1 times and remaining two eigen values are the roots of the second degree equation \([\lambda – (n – 1)k] [\lambda – (m – 1)2] – 4nm=0.\)
Proof. Let G be a \(k\)-regular graph of order n with connectivity k. Then the subdivision graph \(S(G)\) of the graph G has two types of vertices. The n vertices are of degree k and the remaining m vertices are of degree 2.
\[P(S(G))= \begin{bmatrix} kJ_n-kI_n& 2 J_{nXm} \\ 2 J_{mXn}& 2 J_m-2I_m\\ \end{bmatrix}_{n+m}\],
where J is matrix of all 1’s. By applying the Result 2.2, we have
\[\begin{aligned} \left| \lambda I_{n} -P(S(G)) \right| = & \begin{vmatrix} (\lambda +k)I_n – kJ_n & -2 J_{nXm}\\ -2 J_{mXn} &(\lambda +2)I_m – 2J_m \end{vmatrix}\\ =&(\lambda + k)^{n – 1} (\lambda + 2)^{m – 1} ( [\lambda – (n – 1)k] [\lambda – (m – 1)2] – 4nm). \end{aligned}\]
Therefore, the path eigenvalues of subdivision graph \(S(G)\) are \(-k\) repeating n-1 times, \(-2\) repeating m-1 times and remaining two eigen values are the roots of the second degree equation \([\lambda – (n – 1)k] [\lambda – (m – 1)2] – 4nm=0.\) ◻
The following theorem gives the path eigenvalues of thorn graph of a k-regular graph with connectivity k.
Theorem 4.3. Let G be a k-regular graph of order n and size m with vertex connectivity k. Then the path eigenvalues of its thorn graph \(G^{+t}\) are given by \(-k\) repeating n-1 times, \(-1\) repeating m-1 times and remaining two eigenvalues are roots of the second degree equation \([\lambda – (n – 1)k] [\lambda – (nt – 1)] – n^2t=0.\)
Proof. The thorn graph \(G^{+t}\) of a \(k\)-regular graph \(G\) has two types of vertices. The \(n\) vertices are of degree \(k + t\) and the remaining \(nt\) vertices are of degree \(1\).
\[P(G^{+t})= \begin{bmatrix} kJ_n-kI_n& J_{nXnt} \\ J_{ntX n}& J_{nt}-I_{nt}\\ \end{bmatrix}_{n+nt},\]
where J is matrix of all 1’s. By applying the Result 2.2, we have
\[\begin{aligned} \left| \lambda I_{n} -P(G^{+t}) \right| = & \begin{vmatrix} (\lambda +k)I_n – kJ_n & -J_{nXnt}\\ – J_{ntXn} &(\lambda +1)I_{nt} – J_{nt} \end{vmatrix}\\ =&(\lambda + k)^{n – 1} (\lambda + 1)^{m – 1} ( [\lambda – (n – 1)r] [\lambda – (nt- 1)] – n^2t). \end{aligned}\]
Hence, the path eigenvalues of thorn graph \(G^{+t}\) are \(-k\) repeating n-1 times, \(-1\) repeating m-1 times and remaining two eigenvalues are roots of the second degree equation \([\lambda – (n – 1)k] [\lambda – (nt – 1)] – n^2t=0.\) ◻
In the following theorems, we find the path eigenvalues of tadpole graph, crown graph and gear graph of a given graph.
Theorem 4.4. The path eigenvalues of the tadpole graph \(T_{n,k}\) are \(-2\) repeating \(n-1\) times, \(-1\) repeating \(k-1\) times and the remaining two eigenvlaues are the roots of the second degree equation \([\lambda – (n – 1)2] [\lambda – (k- 1)] – nk=0\).
Proof. Let \(T_{n,k}\) be the tadpole graph obtained by joining the end point of a path of length \(k\) to an \(n\) cycle. Then its path matrix is given by
\[P(T_{n,k})= \begin{bmatrix} 2J_{n}-2I_{n} & J_{nXk} \\ J_{kX n}& J_{k}-I_{k}\\ \end{bmatrix}_{n+k},\]
where J is matrix of all 1’s. By applying Result 2.2, we have
\[\begin{aligned} \left| \lambda I_{n} -P(T_{n,k}) \right| = & \begin{vmatrix} (\lambda +2)I_n – 2J_n & -J_{nXk}\\ – J_{kXn} &(\lambda +1)I_{k} – J_{k} \end{vmatrix}\\ =&(\lambda + 2)^{n – 1} (\lambda + 1)^{k – 1} ( [\lambda – (n – 1)2] [\lambda – (k- 1)] – nk). \end{aligned}\]
Hence, the path eigenvalues of the tadpole graph \(T_{n,k}\) are \(-2\) repeating \(n-1\) times, \(-1\) repeating \(k-1\) times and the remaining two eigenvlaues are the roots of the second degree equation \([\lambda – (n – 1)2] [\lambda – (k- 1)] – nk=0\). ◻
Theorem 4.5. The path eigenvalues of the crown graph \(CW_{n}\) are \(-2\) repeating \(n-1\) times, \(-1\) repeating \(n-1\) times and the remaining two eigenvlaues are the roots of the second degree equation \([\lambda – (n – 1)2] [\lambda – (n- 1)] – n^2=0\).
Proof. Let \(CW_{n}\) denote the crown graph obtained by joining a pendant edge at each vertex of cycle with \(n\) vertices. then it’s path matrix is
\[P(CW_{n})= \begin{bmatrix} 2J_{n}-2I_{n} & J_{n} \\ J_{n}& J_{n}-I_{n}\\ \end{bmatrix}_{2n}\],
where J is matrix of all 1’s. By applying the Result 2.2, we have
\[\begin{aligned} \left| \lambda I_{n} -P(CW_{n}) \right| &= \begin{vmatrix} (\lambda +2)I_n – 2J_n & -J_{n}\\ – J_{n} &(\lambda +1)I_{n} – J_{n} \end{vmatrix}\\ &=(\lambda + 2)^{n – 1} (\lambda + 1)^{n – 1} ( [\lambda – (n – 1)2] [\lambda – (n- 1)] – n^2). \end{aligned}\]
Hence, the path eigenvalues of the crown graph \(CW_{n}\) are \(-2\) repeating \(n-1\) times, \(-1\) repeating \(n-1\) times and the remaining two eigenvlaues are the roots of the second degree equation \([\lambda – (n – 1)2] [\lambda – (n- 1)] – n^2=0\). ◻
Theorem 4.6. The path eigenvalues of the gear graph \(G_{n}\) are \(-3\) repeating \(n\) times, \(-2\) repeating \(n-1\) times and the remaining two eigenvlaues are the roots of the second degree equation \([\lambda – 3n] [\lambda – 2(n- 1)] – 4n(n+1)=0\).
Proof. Let \(G_{n}\) denote the gear graph obtained by adding a vertex between every pair of adjacent vertices of the \(n\) cycle, then it’s path matrix is
\[P(G_{n})= \begin{bmatrix} 3J_{n+1}-3I_{n+1} & 2J_{n+1\times n} \\ 2J_{n\times n+1}& 2J_{n}-2I_{n}\\ \end{bmatrix}_{2n+1},\]
where J is matrix of all 1’s. By applying the Result 2.2, we have
\[\begin{aligned} \left| \lambda I_{n} -P(G_{n}) \right| =& \begin{vmatrix} (\lambda +3)I_{n+1} – 3J_{n+1} & -2J_{(n+1) \times n}\\ – 2J_{n\times n+1} &(\lambda +2)I_{n} – 2J_{n} \end{vmatrix}\\ =&(\lambda + 3)^{n} (\lambda + 2)^{n-1} ( [\lambda – 3n] [\lambda – (n- 1)2] – 4n(n+1)). \end{aligned}\]
Therefore, the path eigenvalues of the gear graph \(G_{n}\) are \(-3\) repeating \(n\) times, \(-2\) repeating \(n-1\) times and the remaining two eigenvlaues are the roots of the second degree equation \([\lambda – 3n] [\lambda – 2(n- 1)] – 4n(n+1)=0\). ◻