The Spectral Radii of Some Adhesive Graphs

Qingning Wang

School of Mathematics and Statistics, Qinghai Nationalities University, Xining, China.

DOI: 10.4236/am.2021.124017                

Abstract

The spectral radius of a graph is the maximum eigenvalues of its adjacency matrix. In this paper, using the property of quotient graph, the sharp upper bounds for the spectral radii of some adhesive graphs are determined.

Keywords

Spectral Radius, Adjacency Matrix, Equitable Partition, Quotient Graph

1. Introduction

The spectral radius of the graph powerfully characterizes dynamic processes on networks, such as virus spread and synchronization. In [1], the authors pointed out that the maximum eigenvalue of a graph (i.e., the spectral radius) plays an important role in the network virus transmission mode. They found that the small spectral radius and the large robustness suppress the spread of network viruses. At present, a group of excellent experts have used parameters such as maximum degree and girth to give the bounds of the spectral radii of many graphs, see [2] - [11]. In this paper, we will use special methods to give research on the precise spectral radii of some graphs.

Let $G=\left(V\mathrm{,}E\right)$ be a simple connected undirected graph. $A\left(G\right)$ denotes the adjacency matrix of G. Its characteristic polynomial is denoted by $\varphi \left(G\mathrm{,}\lambda \right)$ . $A\left(G\right)$ is a real symmetric matrix, as its characteristic roots are all real, and can be sorted as follows: ${\lambda }_1\left(G\right)\ge {\lambda }_2\left(G\right)\ge \cdots \ge {\lambda }_n\left(G\right)$ . Multi-sets of n characteristic roots are called the spectrum of graph G. ${\lambda }_1\left(G\right)$ is usually called the spectral radius of graph G.

A partition $\pi =\left(C_1\mathrm{,}{C}_2\mathrm{,}\cdots \mathrm{,}{C}_k\right)$ of $V\left(G\right)$ is equitable if, for all i and j, the number of neighbours which a vertex in $C_i$ has in the cell $C_j$ is independent of the choice of vertex in $C_i$ .

Given an equitable partition $\pi =\left(C_1\mathrm{,}{C}_2\mathrm{,}\cdots \mathrm{,}{C}_k\right)$ of a graph G, we now define the quotient $G/\pi$ of G with respect to $\pi$ . Let $C_{ij}$ denote the number of edges which join a fixed vertex in $C_i$ to vertices in $C_j$ . Then $G/\pi$ is the directed graph with the cells of $\pi$ as its vertices, and with $C_{ij}$ arcs going from $C_i$ to $C_j$ . Then say $G/\pi$ a quotient graph of graph G corresponding to partition $\pi$ .

An outline of the rest of the paper is as follows. In Section 2, we will present important results about quotient graph. In Section 3, we will give the main results.

2. Some Preliminaries

Godsil [12] presented important results about quotient graph as follows.

Lemma 1. ( [12] ) Let $\pi$ be an equitable partition of the connected graph G. Then $A\left(G\right)$ and $A\left(G/\pi \right)$ have the same spectral radius.

Lemma 2. ( [13] ) Suppose G is a connected graph, H is a proper subgraph of G, then ${\lambda }_1\left(H\right)<{\lambda }_1\left(G\right)$ .

3. Main Results

Theorem 1. Let G be a graph obtained by identifying a vertex of $K_k$ to every vertex of $C_l$ . Then

${\lambda }_1\left(G\right)=\frac{k+\sqrt{k^2-4k+12}}{2}\mathrm{.}$ (1)

Proof. Checking the structure of graph G, we can obtain an equivalence partition $\pi =\left(C_1\mathrm{,}{C}_2\right)$ , where C₁ = {all the vertices on the cycle C₁}, $C_2=V\left(G\right)-C_1$ , then

$A\left(G/\pi \right)=\left(\begin{array}{cc}2& k-1\\ 1& k-2\end{array}\right)\mathrm{.}$ (2)

Thus, $\varphi \left(G/\pi \mathrm{,}\lambda \right)={\lambda }^2-k\lambda +k-3$ . By Lemma 1, we know

${\lambda }_1\left(G\right)=\frac{k+\sqrt{k^2-4k+12}}{2}$ . □

By Theorem 1, we know that the spectral radius of the bonding graph G is independent of the coil length, only depends on the number of vertices of the complete graph that is bonded.

By Theorem 1, we directly obtain the following result.

Corollary 1. Let G be a graph obtained by attaching a single vertex to every vertex of $C_l$ . Then ${\lambda }_1\left(G\right)=1+\sqrt{2}$ .

A sun-like graph, denoted by $S\left(l\mathrm{<mo>\; ;\; </mo>}{p}_{m_1}\mathrm{,}{p}_{m_2}\mathrm{,}\cdots \mathrm{,}{p}_{m_l}\right)$ , obtained by attaching a vertex of degree one in $P_{m_i}\left(m_i\ge 2,i=1,2,\cdots ,l\right)$ to a vertex of cycle $C_l$ . The resulting graph see Figure 1.

From the above definition, it can be seen that $S\left(l\mathrm{<mo>\; ;\; </mo>}{p}_{m_1}\mathrm{,}{p}_{m_2}\mathrm{,}\cdots \mathrm{,}{p}_{m_l}\right)$ is a unicyclic graph. We have the following theorem for the spectral radius of a unicyclic graph.

Theorem 2. ( [3] ) Let G be a unicyclic graph with maximum degree $\Delta$ . Then

Figure 1. $S\left(l;m_1,m_2,\cdots ,m_l\right)$ .

${\lambda }_1\left(G\right)\le 2\sqrt{\Delta -1}\mathrm{,}$ (3)

where the equality holds if and only if $G\cong C_n$ .

Graph $S\left(l\mathrm{<mo>\; ;\; </mo>1,1,}\cdots \mathrm{,1}\right)$ is a sun-like graph. And $S\left(l\mathrm{<mo>\; ;\; </mo>1,1,}\cdots \mathrm{,1}\right)$ is a vertex-induced subgraph of a sunlike graph. By Lemma 2, Corollary 1 and Theorem 2, we get that

Corollary 2. $1+\sqrt{2}\le {\lambda }_1\left(S\left(m;p_{m_1},p_{m_2},\cdots ,p_{m_l}\right)\right)<2\sqrt{2}$ , where the equality holds if and only if $p_{m_i}=1\left(i=1,2,\cdots ,l\right)$ .

Corollary 3. Let G be a graph obtained by identifying a vertex of $C_3$ to every vertex of $C_l$ . Then ${\lambda }_1\left(G\right)=3$ .

Theorem 3. Let G be a graph constituted by splicing m complete graphs of order k on vertex v. Then

${\lambda }_1\left(G\right)=\frac{k-2+\sqrt{k^2-4k+4+4mk-4m}}{2}\mathrm{.}$ (4)

Proof. Checking the structure of graph G, we get an equivalence partition $\pi =\left(C_1\mathrm{,}{C}_2\right)$ , where $C_1=\left\{v\right\},C_2=V\left(G\right)-v$ . So, we have

$A\left(G/\pi \right)=\left(\begin{array}{cc}0& m\left(k-1\right)\\ 1& k-2\end{array}\right)\mathrm{,}$ (5)

Hence, $\varphi \left(G/\pi \mathrm{,}\lambda \right)={\lambda }^2-\left(k-2\right)\lambda -m\left(k-1\right)$ . By Lemma 1, we know that

${\lambda }_1\left(G\right)=\frac{k-2+\sqrt{k^2-4k+4+4mk-4m}}{2}$ . □

If G is a graph constituted by splicing two complete graphs of order k on vertex v, see Figure 2.

Corollary 4.

${\lambda }_1\left(G\right)=\frac{k-2+\sqrt{k^2-4k+4}}{2}\mathrm{.}$ (6)

Assume that G is a prism graph. Then ${\lambda }_1\left(G\right)=3$ . The following we investigate the spectral radius of a graph obtained by removing the lateral edge of a prism with a plane.

Theorem 4. Let G be a polygon with the same number of upper and lower

Figure 2. Graph G.

undersides after cutting off the side edges of the prism with a plane. Then the spectral radius of the resulting graph is

${\lambda }_1\left(G\right)=2+\sqrt{2}\mathrm{.}$ (7)

Proof. Checking the structure of G, we get an equivalence partition $\pi =\left(C_1\mathrm{,}{C}_2\right)$ , where

C₁ = {the vertices of a polygon on the upper and lower sides of a prism},

C₂ = {the vertices of a polygon with a prism section},

we get

$A\left(G/\pi \right)=\left(\begin{array}{cc}2& 1\\ 2& 2\end{array}\right)\mathrm{,}$ (8)

that is

${\lambda }_1\left(G\right)=2+\sqrt{2}\mathrm{.}$ (9)

□

By Theorem 4, if C₁ = {the vertices of a polygon on the upper and lower sides of a prism} and C₂ = {the vertex of a polygon of two cross-section planes in a prism}, then we can obtain the following result.

Corollary 5. Let G be a polygon with the same number of upper and lower undersides after cutting off the side edges of the prism with two planes. Then the spectral radius of the resulting graph is

${\lambda }_1\left(G\right)=\frac{5+\sqrt{5}}{2}\mathrm{.}$ (10)

Theorem 5. Let G be a pyramid, and let the base polygon has n vertices. Then

${\lambda }_1\left(G\right)=1+\sqrt{1+n}\mathrm{.}$ (11)

Proof. According to the structure of graph G, we get an equivalence partition $\pi =\left(C_1\mathrm{,}{C}_2\right)$ , where C₁ = {the cone point of a pyramid}, C₂ = {the vertex of a polygon on the base of a pyramid}. We can construct quotient graph $G/\pi$ of G, and

$A\left(G/\pi \right)=\left(\begin{array}{cc}0& n\\ 1& 2\end{array}\right),$ (12)

hence, $\varphi \left(G/\pi ,\lambda \right)={\lambda }^2-2\lambda -n$ . By Lemma 1.1, we know ${\lambda }_1\left(G\right)=1+\sqrt{1+n}$ . □

If the above pyramid is expanded into a plane, also known as wheel graph. The undersides (with n vertices) of two identical pyramids are glued together to form a spindle graph, the spectral radius of this graph satisfies the following corollary.

Corollary 6.

${\lambda }_1\left(G\right)=1+\sqrt{1+2n}\mathrm{.}$ (13)

The cone points (with n vertices on the base) of two identical pyramids are glued together to form a dumbbell graph, the spectral radius of this graph satisfies the following corollary.

Corollary 7.

${\lambda }_1\left(G\right)=1+\sqrt{1+2n}\mathrm{.}$ (14)

The cone points (with n vertices on the base) of two identical pyramids are glued with one edge to form a barbell graph, the spectral radius of this graph satisfies the following corollary.

Corollary 8.

${\lambda }_1\left(G\right)=\frac{3+\sqrt{1+4n}}{2}\mathrm{.}$ (15)

Theorem 6. Let G be a graph that obtained by gluing a complete graph $K_k$ on each vertex of complete graph $K_l$ , Then

${\lambda }_1\left(G\right)=\frac{l+k-3+\sqrt{{\left(l-k\right)}^2+2\left(l+k\right)-3}}{2}\mathrm{.}$ (16)

Proof. According to the structure of graph G, we get an equivalence partition $\pi =\left(C_1\mathrm{,}{C}_2\right)$ , where $C_1=\left\{\text{thevertexin}{K}_l\right\}$ , $C_2=V\left(G\right)-C_1$ . So that we have

$A\left(G/\pi \right)=\left(\begin{array}{cc}l-1& k-1\\ 1& k-2\end{array}\right)\mathrm{,}$ (17)

evidenced by the same token. □

Theorem 7. Let G be a graph obtained by corresponding adhesion between m-order subgraphs ( $m<k$ ) of two k-order complete graphs. Then

${\lambda }_1\left(G\right)=\frac{k-2+\sqrt{k^2-4m^2+4km}}{2}\left(m<k\right).$ (18)

Proof. According to the structure of graph G, we obtain an equivalence partition $\pi =\left(C_1\mathrm{,}{C}_2\right)$ , where C₁ = {m vertices bonded to each other}, $C_2=V\left(G\right)-C_1$ . So that we have

$A\left(G/\pi \right)=\left(\begin{array}{cc}m-1& 2\left(k-m\right)\\ m& k-m-1\end{array}\right),$ (19)

thus, $\varphi \left(G/\pi \mathrm{,}\lambda \right)={\lambda }^2-\left(k-2\right)\lambda +m^2-km-k+1$ . □

Theorem 8. Let G be a graph that obtained by adding m edges with one-to-one correlation between m pairs of vertices of two k-order complete graphs, then

${\lambda }_1\left(G\right)=\frac{k-1+\sqrt{k^2-2k+1+4m}}{2}\left(m<k\right).$ (20)

Proof. According to the structure of graph G, we obtain an equivalence partition $\pi =\left(C_1\mathrm{,}{C}_2\right)$ , where C₁ = {2m vertices associated with m edges added}, $C_2=V\left(G\right)-C_1$ . We can construct quotient graph $G/\pi$ of G, we have

$A\left(G/\pi \right)=\left(\begin{array}{cc}m& k-m\\ m& k-1-m\end{array}\right).$ (21)

Thus, $\varphi \left(G/\pi ,\lambda \right)={\lambda }^2-\left(k-1\right)\lambda -m$ , evidenced by the same token. □

Corollary 9. Let G be a graph that obtained by adding one edge between two k-order complete graph. Then

${\lambda }_1\left(G\right)=\frac{k-1+\sqrt{{\left(k-1\right)}^2+4}}{2}\mathrm{.}$ (22)

4. Conclusion

Lemma 2 shows that, the above results give an upper bound of the spectral radius of the corresponding subgraph. The key to characterizing the spectral radius of a graph by using the property of quotient graph is to construct equivalence partition. The adjacency matrix of the quotient graph is always smaller than the adjacency matrix of the supergraph, so it is a beautiful way to use the property of quotient graph to depict the spectral radius of graph.

Acknowledgements

This work is supported by the National Natural Science Foundation of China (No. 11661066), the Basic Research and Applied Research of Qinghai Province (2017-ZJ-701).

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Wang, Y., Chakrabarti, D., Wang, C. and Faloutsos, C. (2003) Epidemic Spreading in Real Networks: An Eigenvalue Viewpoint. 22nd Symposium in Reliable Distributed Computing, 6-8 October 2003, Florence.
[2]	Duan, C. and Wang, L. (2021) Bounds on the Spectral Radius of General Hypergraphs in Terms of Clique Number. Linear Algebra and Its Applications, 610, 120-134. https://doi.org/10.1016/j.laa.2020.09.039
[3]	Hu, S. (2007) The Largest Eigenvalue of Unicyclic Graphs. Discrete Mathematics, 307, 280-284. https://doi.org/10.1016/j.disc.2006.06.023
[4]	Liu, B., Shen, J. and Wang, X. (2007) On the Largest Eigenvalue of Nonregular Graphs. Journal of Combinatorial Theory, Series B, 97, 1010-1018. https://doi.org/10.1016/j.jctb.2007.02.008
[5]	Monsalve, J. and Rada, J. (2021) Extremal Spectral Radius of Graphs with Rank 4. Linear Algebra and Its Applications, 609, 1-11. https://doi.org/10.1016/j.laa.2020.08.017
[6]	Shi, L. (2009) The Spectral Radius of Irregular Graphs. Linear Algebra and Its Applications, 431, 189-196. https://doi.org/10.1016/j.laa.2009.02.023
[7]	Wang, Z. and Guo, J. (2020) Some Upper Bounds on the Spectral Radius of a Graph. Linear Algebra and Its Applications, 601, 101-112. https://doi.org/10.1016/j.laa.2020.04.024
[8]	Wu, T. and Hu, S. (2009) On the Spectral Radius of Bistarlike Tree. Proceeding of the 3rd International Workshop of Matrix Analysis and Applications, 3, 24-28. .
[9]	Wu, T. and Hu, S. (2011) On the Spectral Radii of M-Starlike Tree. Operations Research Transactions, 3, 45-50.
[10]	Stevanović, D. (2004) The Largest Eigenvalue of Nonregular Graphs. Journal of Combinatorial Theory, Series B, 91, 143-146. https://doi.org/10.1016/j.jctb.2003.12.002
[11]	Zhang, X. (2005) Eigenvectors and Eigenvalues of Nonregular Graphs. Linear Algebra and its Applications, 409, 79-86. https://doi.org/10.1016/j.laa.2005.03.020
[12]	Godsil, C.D. (1993) Algebra Combinatorics. Academic Press, New York.
[13]	Cvetković, D.M., Doob. M. and Sachs, H. (1980) Spectra of Graphs. Springer, New York.