Maximum degree and minimum degree spectral radii of some graph operations

1.   Introduction

Let $G$ be graph having vertex set $V = V(G)$ and edge set $E = E(G)$, then the adjacency matrix associated to the graph $G$, is

Sum of absolute values of the eigenvalues associated to $A(G)$ is known as energy of the graph $G$ denoted by $E(G)$ and the Largest eigenvalue of $A(G)$ is called Spectral radius of the graph $G$ and it is denoted by $\wp(G)$. For details and references relating to Spectral radii, follow ^[2,3,4]. The motivation of $E(G)$ was initiated by Gutman in 1978 ^[1] but the idea could not get attention until 2000. Since 2003, rapid development in technology and computer awoke significant interests in these areas. The problem of determining extreme values of spectral radius has been extensively investigated, ^[5]. Partial solutions to these problems can be traced in ^{[6,7,8,9,10,11]}. Fiedler and Nikiforov ^[6] gave tight sufficient conditions for the existence of Hamilton paths and cycles in terms of the spectral radius of graphs or the complement of graphs. Lu et al. ^[7] studied sufficient conditions for Hamilton paths in connected graphs and Hamilton cycles in bipartite graphs in terms of the spectral radius of a graph. Some other spectral conditions for Hamilton paths and cycles in graphs have been given in ^{[12,13,14,15,16]}.

Horn et al.^[17] and Gatmacher ^[18] used matrix analysis to relate it with graph energies. Balkrishnan, in ^[19], computed the sharp bounds for energy of a $k$-regular graph and proved that for $n\geq3$, there always exists two equi-energetic graphs having order $4n$ which are not co-spectral. Bapat et al. proved that $E(G)$ can not be an odd integer, ^[20] whereas Pirzada et al. ^[21] proved that it can not be square root of an odd integer. Jones ^[22] discussed $E(G)$ of simple graphs relating it with closuring and algebraic connectivity. Different kinds of matrices energies associated to a graph are presented by Meenakshi et al. ^[23]. Nikiforov ^[24] obtained various results related to bounds of energies. Samir et al. ^[25] constructed 1-splitting and 1-shadow graph of any simple connected graph and proved that adjacency energies of these newly constructed graphs is constant multiple of the energies of the original graph. Samir et al. ^[26] then generalized the idea of 1-splitting and 2-shadow graph to arbitrary $s$-splitting and $s$-shadow graph where $s > 0$ and obtained similar kind of general results for adjacency energies. Liu et al. ^[27] discussed distance and adjacency energies of multi-level wheel networks. Chu et al. ^[19] computed Laplacian and signless Laplacian spectra and energies of multi-step wheels.

In 2015, Liu et al. ^[29] discussed asymptotic Laplacian energy like invariants of lattices. In 2016, Hosamani et al. ^[30] presented degree sum energy of a graph and obtained some lower bounds for this energy. In 2018, Basavanagoud et al. ^[31] computed the characteristic polynomial of the degree square sum matrix of graphs obtained by some graph operations as well as some bounds for spectral radius for square sum eigenvalue and degree square sum energy of graphs. In 2018, Rad et al. ^[32] presented Zagreb energy and related Estrada index of various graphs. In 2019, Gutman et al. ^[33] discussed graph energy and its applications, featuring about hundred kinds of graph energies and applications in diverse areas. For further details and basic ideas of graph energies, we refer ^{[20,21,34,35,36]}. Interconnection and various applications of graph energy in chemistry of unsaturated hydrocarbons can be traced in ^[37,38,39]. Applications of different graph energies in crystallography can be found in ^[40,41], theory of macro molecules in ^[42,43], protein sequences in ^[44,45,46], biology in ^[47], applied network analysis in ^{[47,48,49,50,51,52]}, problems of air transportation in ^[48], satellite communications in ^[50] and constructions of spacecrafts in ^[52].

In the present article we produce new results about maximum degree spectral radii and minimum degree spectral radii of $m$-splitting and $m$-shadow graphs. In fact we relate these spectral radii of new graph operations with spectral radii of original graphs. The article is organized as follows. Section 2 gives basic definitions and terminologies to lay foundations of our results. In Section 3, we derive maximum degree spectral radii and minimum degree spectral radii of generalized splitting graph constructed on any basic graph. In Section 4 we proceed to find similar results but for generalized shadow graph of the given regular graph.

2.   Preliminaries

In this part we outline main ideas and preliminary facts, for details see ^[53,54]. The matrix $M(G)$ is the maximum degree matrix of the graph $G$ defined in ^[53] as

Here $d_{i}$ and $d_{j}$ are the degrees of vertices $v_{i}$ and $v_{j}$ respectively. Eigenvalues of maximum degree matrix of the graph $G$ are denoted as $\eta_{1}, \eta_{2}, \cdots \eta_{n}$. Maximum degree spectral radius is defined as

where $\eta_1, \eta_2, ..., \eta_n$ are the eigenvalues of maximum degree matrix. The matrix $MI(G)$ is called the minimum degree matrix of the graph $G$ is defined in ^[54] as

Minimum degree spectral radius is defined as

where $\eta_1, \eta_2, ..., \eta_n$ are the eigenvalues of minimum degree matrix. If we add a new vertex $v'$ to each vertex $v$ of the graph $G$, $v'$ is connected to every vertex that is adjacent to $v$ in $G$ then we obtain the splitting graph $(spl_{1}(G))$. Take two copies $G'$ and $G''$ of the graph $G$, then $(sh_{2}(G))$ is constructed if we join each vertex in $G'$ to the neighbors of the corresponding vertices in $G''$. Let $U\epsilon R^{m\times n}$, $V \epsilon R^{p\times q}$ the tensor product (Kronecker product), $U\bigotimes V$ is defined as the matrix.

Proposition 1.1. Let $U \epsilon M^{m}$, $V\epsilon M^{n}$ and $\alpha$ be an eigenvalue of $U$ and $\eta$ be an eigenvalue of $V$, then $\alpha\eta$ is an eigenvalue of $U \bigotimes V$ ^[25]. Now we move towards the main results.

3.   Spectral radii of generalized splitting graph

In this part we relate maximum degree spectral radius and minimum degree spectral radius of generalized splitting graph with original graph $G$. Here again we emphasis that $G$ is any regular graph.

Theorem 1. Let $G$ be any $n$-regular graph and $\wp M(Spl_{m}(G))$ is themaximum degree spectral radius of $m$-splitting graph $G$, then

Proof. Maximum degree matrix is given by $M(G)$ where

$M(Spl_{m}(G))$ can be written in block matrix form as

Let

Now we compute the eigenvalues of $A$ Since matrix $A$ is of rank two, so $A$ has two non-zero eigenvalues, say $\alpha_{1}$ and $\alpha_{2}$. Obviously,

Considering

Then

Solving Eqs $(3.1)$ and $(3.2)$, we have

and

So we have,

Using Eq $(3.3)$ we have

Since $M (Spl_{m}(G)) = M(G) \bigotimes A$ then by Proposition 1.1, we have

In the following corollaries, we obtain the maximum degree spectral radii of splitting graphs of $C_{n}$, $K_{n}$, $C_{n, n}$ and crown graph.

Corollary 2. If $n\geq3$ and $G$ is a $C_{n}$ graph, where $C_{n}$ is cycle graph on $n$ vertices, then

Proof. If $G$ is a cycle graph $C_{n} (n\geq3)$, then $\wp M(C_{n}) = 4$. Since cycle graph is 2-regular graph so using Theorem 1 we get the required result.

Corollary 3. If $G$ is a $K_{n}$ graph, where $K_{n}$ is complete graph on $n$ vertices, then

Proof. If $G$ is a complete graph on $n$ vertices, then $\wp M(K_{n}) = (n-1)^{2}$. Since complete graph is $n-1$-regular graph so using Theorem 1 we get the required result.

Corollary 4. If $G$ is a complete bipartite graph $K_{n, n}$, then

Proof. If $G$ is a complete bipartite graph $K_{n, n}$, then $\wp M(K_{n, n}) = (n)^{2}$. Using Theorem 1 we get the required result.

Corollary 5. If $G$ is a crown graph on $2n$ vertices, then

Proof. If $G$ is a crown graph on $2n$ vertices, then $\wp M(G) = (n-1)^{2}$. Using Theorem 1 we get the required result.

Theorem 6. Let $G$ be any $n$-regular graph and $\wp MI((Spl_{m}(G))$ is theminimum degree spectral radius of $m$-splitting graph $G$, then

Proof. Minimum degree matrix is given by

$MI(Spl_{m}(G))$ can be written in block matrix form as follows:

Let

Now we compute the eigenvalues of $A$ Since matrix $A$ is of rank two, so $A$ has two non-zero eigenvalues, say $\alpha_{1}$ and $\alpha_{2}$. Obviously,

Considering

Then

Solving Eqs $(3.4)$ and $(3.5)$ we have

So we have,

Using Eq $(3.6)$ we have

Since $MI(Spl_{m}(G)) = MI(G) \bigotimes A$ then by Proposition 1.1, we have

In the following corollaries, we obtain the minimum degree spectral radii of splitting graphs of $C_{n}$, $K_{n}$, $C_{n, n}$ and crown graph.

Corollary 7. If $n\geq3$ and $G$ is a $C_{n}$ graph, where $C_{n}$ is cycle graph on $n$ vertices, then

Proof. If $G$ is a cycle graph $C_{n} (n\geq3)$, then $\wp MI(C_{n}) = 4$. Since cycle graph is 2-regular graph so using Theorem 6 we get the required result.

Corollary 8. If $G$ is a $K_{n}$ graph, where $K_{n}$ is complete graph on $n$ vertices, then

Proof. If $G$ is a complete graph on $n$ vertices, then $\wp MI(K_{n}) = (n-1)^{2}$. Since complete graph is $n-1$-regular graph so using Theorem 6 we get the required result.

Corollary 9. If $G$ is a complete bipartite graph $K_{n, n}$, then

Proof. If $G$ is a complete bipartite graph $K_{n, n}$, then $\wp MI(K_{n, n}) = (n)^{2}$. Using Theorem 6 we get the required result.

Corollary 10. If $G$ is a crown graph on $2n$ vertices, then

Proof. If $G$ is a crown graph on $2n$ vertices, then $\wp MI(G) = (n-1)^{2}$. Using Theorem 6 we get the required result.

4.   Energies and spectral radii of generalized shadow graph

In this part we relate maximum degree spectral radius and minimum degree spectral radius of generalized Shadow graph with original graph $G$. Here again we emphasis that $G$ is any regular graph.

Theorem 11. Let $G$ be any $n$-regular graph and $\wp M(Sh_{m}(G))$ is themaximum degree spectral radius of $m$-shadow graph $G$, then

Proof. Maximum degree matrix is given by

Then $M(Sh_{m}(G))$ can be written in block matrix form as follows:

Let

Now we compute the eigenvalues of $A$ Since matrix $A$ is of rank one, so $A$ has one non-zero eigenvalue, say $\alpha_{1} = (m)^{2}.$ So we have,

Using Eq $(4.1)$ we have

Since $M(Sh_{m}(G)) = M(G) \bigotimes A$ then by Proposition 1.1, we have

In the following corollaries, we obtain the maximum degree spectral radii of shadow graphs of $C_{n}$, $K_{n}$, $C_{n, n}$ and crown graph.

Corollary 12. If $n\geq3$ and $G$ is a $C_{n}$ graph, where $C_{n}$ is cycle graph on $n$ vertices, then

Proof. If $G$ is a cycle graph $C_{n} (n\geq3)$, then $\wp M(C_{n}) = 4$. Since cycle graph is 2-regular graph so using Theorem 11 we get the required result.

Corollary 13. If $G$ is a $K_{n}$ graph, where $K_{n}$ is complete graph on $n$ vertices, then

Proof. If $G$ is a complete graph on $n$ vertices, then $\wp M(K_{n}) = (n-1)^{2}$. Since complete graph is $n-1$-regular graph so using Theorem 11, we get the required result.

Corollary 14. If $G$ is a complete bipartite graph $K_{n, n}$, then

Proof. If $G$ is a complete bipartite graph $K_{n, n}$, then $\wp M(K_{n, n}) = (n)^{2}$. Using Theorem 11, we get the required result.

Corollary 15. If $G$ is a crown graph on $2n$ vertices, then

Proof. If $G$ is a crown graph on $2n$ vertices, then $\wp M(G) = (n-1)^{2}$. Using Theorem 11, we get the required result.

Theorem 16. Let $G$ be any $n$-regular graph and $\wp MI(Sh_{m}(G))$ is theminimum degree spectral radius of $m$-shadow graph $G$, then

Proof. Minimum degree matrix is given by

Then $MI(Sh_{m}(G))$ can be written in block matrix form as follows:

Let

Now we compute the eigenvalues of $A$ Since matrix $A$ is of rank one, so $A$ has one non-zero eigenvalue, say $\alpha_{1} = (m)^{2}.$ So we have,

Using Eq $(4.2)$ we have

Since $MI(Sh_{m}(G)) = MI(G) \bigotimes A$ then by Proposition 1.1, we have

In the following corollaries, we obtain the minimum degree spectral radii of shadow graphs of $C_{n}$, $K_{n}$, $C_{n, n}$ and crown graph.

Corollary 17. If $n\geq3$ and $G$ is a $C_{n}$ graph, where $C_{n}$ is cycle graph on $n$ vertices, then

Proof. If $G$ is a cycle graph $C_{n} (n\geq3)$, then $\wp MI(C_{n}) = 4$. Since cycle graph is 2-regular graph so using Theorem 16 we get the required result.

Corollary 18. If $G$ is a $K_{n}$ graph, where $K_{n}$ is complete graph on $n$ vertices, then

Proof. If $G$ is a complete graph on $n$ vertices, then $\wp MI(K_{n}) = (n-1)^{2}$. Since complete graph is $n-1$-regular graph so using Theorem 16 we get the required result.

Corollary 19. If $G$ is a complete bipartite graph $K_{n, n}$, then

Proof. If $G$ is a complete bipartite graph $K_{n, n}$, then $\wp MI(K_{n, n}) = (n)^{2}$. Using Theorem 16, we get the required result.

Corollary 20. If $G$ is a crown graph on $2n$ vertices, then

Proof. If $G$ is a crown graph on $2n$ vertices, then $\wp MI(G) = (n-1)^{2}$. Using Theorem 16 we get the required result.

5.   Conclusions

The spectral radius of graph has vast range of applications in computer related areas. It also connects graph theory and chemistry. In this article we have related the spectral radii of the generalized shadow and splitting graph of any regular graph with spectral radius of the given graph. In particular we have proved that the Spectral Radius of the new graph is a multiple of spectral radius of the given regular graph.

Acknowledgements

The authors thank the National Key Research and Development Program under Grant 2018YFB0904205, Science and Technology Bureau of ChengDu (2020-YF09-00005-SN), Sichuan Science and Technology program (2021YFH0107) and Erasmus + SHYFTE Project (598649-EPP-1-2018-1-FR-EPPKA2-CBHE-JP).

Conflict of interest

The authors declare that there is no conflict of interest.