Some lemmas on spectral radius of graphs: including an application
Wenqian Zhang · 2026
Read Some lemmas on spectral radius of graphs: including an application by Wenqian Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-00621.txt.
Introduction
Wenqian Zhang is the sole author of a 2026 math paper on the spread of a graph. A graph is a web of points joined by lines. Its spread, called the spectral radius, is the largest value from a matrix that codes which points are linked. Zhang studies webs that hold one special, full two-sided web inside them.
The paper gives three short facts about spread for such webs. It then uses those facts, plus standard tools of the field, to pin down one best web. The best web is the flat web with no loops, on many points, that has the largest spread. It must also dodge one set loop length, which can be short or long. Such best-web results show how shape and spread trade off. They also guide work on links, chips, and other webs in math.
Catalog record
| CREATOR | Wenqian Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-00621
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Some lemmas on spectral radius of graphs: including an application Wenqian Zhang Abstract For a graph G G , the spectral radius ρ ( G ) \rho(G) of G G is the largest eigenvalue of its adjacency matrix. In this paper, we give three lammas on ρ ( G ) \rho(G) when G G contains a spanning complete bipartite graph. Using these lemmas and typical spectral method, we characterized the unique extremal graph with the maximum spectral radius among all planar graphs of large order n n without a cycle of length ℓ \ell , where 5 ≤ ℓ ≤ n 5\leq\ell\leq n . Keywords: spectral radius; planar graph; cycle; walk. 2020 Mathematics Subject Classification: 05C50; 05C35. † † footnotetext: E-mails: [email protected] 1 Introduction All graphs considered in this paper are finite, undirected and simple. For a graph G , let \overline{G} be its complement. The vertex set and edge set of G are denoted by V(G) and E(G) , respectively. For two vertices u,v , let d_{G}(u,v) denote the distance between them (i.e., the minimum length of a path connecting them). We say u\sim v , if u and v are adjacent in G . For a certain integer n , let K_{n},P_{n} and C_{n} be the complete graph, the path and the cycle of order n , respectively. For any \ell\geq 2 graphs G_{1},G_{2},...,G_{\ell} , let \cup_{1\leq i\leq\ell}G_{i} be the disjoint union of them. In particular, let tG=\cup_{1\leq i\leq t}G for any integer t\geq 1 . Let G_{1}\vee G_{2} be the join of G_{1} and G_{2} , obtained from G_{1}\cup G_{2} by connecting all vertices of G_{1} to all vertices of G_{2} . For any terminology used but not defined here, one may refer to [ 2 ] . Let G be a graph with vertices v_{1},v_{2},...,v_{n} . The adjacency matrix A(G) of G is an n\times n matrix (a_{ij}) , where a_{ij}=1 if v_{i}\sim v_{j} , and a_{ij}=0 otherwise. The spectral radius \rho(G) of G is the largest eigenvalue of its adjacency matrix. By the well-known Perron–Frobenius theorem, \rho(G) has a non-negative eigenvector. A non-negative eigenvector corresponding to \rho(G) is called a Perron vector of G . If G is connected, any Perron vector of G has positive entries. The spectral radius of a graph is closely related to its convergence property. In this paper, we first give the following three lammas on spectral radius of graphs. (Let P_{0} denote the empty graph.) Lemma 1.1 For integers n_{1}\geq n_{2}+2\geq 3 , let G_{1}=H\vee(P_{n_{1}}\cup P_{n_{2}}\cup T) and G_{2}=H\vee(P_{n_{1}-1}\cup P_{n_{2}+1}\cup T), where H,T are two graphs with |H|\geq 1 and |T|\geq 0 . Then \rho(G_{1})>\rho(G_{2}) . Lemma 1.2 For integers n_{1}\geq n_{2}\geq n_{3}\geq n_{4}\geq 1 and n_{1}\geq n_{2}+2 , let G_{1}=H\vee(P_{n_{1}}\cup P_{n_{2}}\cup P_{n_{3}}\cup P_{n_{4}}\cup T) and G_{2}=H\vee(P_{n_{1}-1}\cup P_{n_{2}+1}\cup P_{n_{3}+1}\cup P_{n_{4}-1}\cup T), where H,T are two graphs with |H|\geq 1 and |T|+\sum_{1\leq s\leq 4}n_{s}\geq 130 . Then \rho(G_{1})<\rho(G_{2}) . Lemma 1.3 For integers n_{1}\geq n_{2}\geq n_{3}\geq n_{4}\geq n_{5}\geq 1 and n_{1}\geq n_{2}+3 , let G_{1}=H\vee(P_{n_{1}}\cup P_{n_{2}}\cup P_{n_{3}}\cup P_{n_{4}}\cup P_{n_{5}}\cup T) and G_{2}=H\vee(P_{n_{1}-2}\cup P_{n_{2}+1}\cup P_{n_{3}+1}\cup P_{n_{4}+1}\cup P_{n_{5}-1}\cup T), where H,T are two graphs with |H|\geq 1 and |T|+\sum_{1\leq s\leq 5}n_{s}\geq 310 . Then \rho(G_{1})<\rho(G_{2}) . A graph is called planar, if it can be drawn in the plane without crossed edges. Tait and Tobin [ 6 ] proved that K_{2}\vee P_{n-2} is the only extremal graph with the maximum spectral radius among all planar graphs of large order n . This (asymptotically) solves a conjecture proposed by Boots and Royle [ 1 ] , and independently by Cao and Vince [ 3 ] . Recently, the researchers are also interested in determining the extremal graphs with the maximum spectral radius among all C_{\ell} -free planar graphs of large order n , where 3\leq\ell\leq n . The case \ell=4 can be settled from the results of Nikiforov [ 5 ] , and Zhai and Wang [ 8 ] . Very recently, Fang, Lin and Shi [ 4 ] solved the case when \ell=3 and 5\leq\ell\ll n . Xu, Lin and Fang [ 7 ] solved the case when \frac{\ell}{n} is close to 1. They [ 7 ] proposed the general case as a problem. Armed with Lemma 1.1 and Lemma 1.2 , using typical spectral method we can solve this problem. That is, we have the following Theorem 1.4 . For a finite family of graphs \mathcal{G} , let {\rm SPEX}(\mathcal{G}) be the set of all extremal graphs with the maximum spectral radius in \mathcal{G} . Theorem 1.4 For integers n\geq 1.8\times 10^{17} and 5\leq\ell\leq n , let \mathcal{G}_{n,\ell} be the set of all C_{\ell} -free planar graphs of order n . Then we have the following conclusions. (i) For 5\leq\ell<\frac{2n+5}{3} , {\rm SPEX}(\mathcal{G}_{n,\ell})=\left\{K_{2}\vee(P_{\lceil\frac{\ell-3}{2}\rceil}\cup(a+1)P_{\lfloor\frac{\ell-3}{2}\rfloor}\cup P_{b})\right\} , where n-\ell+1=a\lfloor\frac{\ell-3}{2}\rfloor+b with 0\leq b<\lfloor\frac{\ell-3}{2}\rfloor . (ii) For \frac{2n+5}{3}\leq\ell\leq n , {\rm SPEX}(\mathcal{G}_{n,\ell})=\left\{K_{2}\vee(P_{2\ell-n-4}\cup 2P_{n-\ell+1})\right\} . The rest of the paper is organized as follows. In Section 2, we include several lemmas, which will be used later. The proofs of Lemmas 1.1 , 1.2 and 1.3 are given in Section 3. In Section 4, we give the proof of Theorem 1.4 . 2 Preliminaries Let G be a graph. For an integer \ell\geq 1 , a walk of length \ell in G is an ordered sequence of vertices v_{0}v_{1}\cdots v_{\ell} , such that v_{i}\sim v_{i+1} for any 0\leq i\leq\ell-1 . The vertex v_{0} is called the starting vertex of the walk. For any u\in V(G) and \ell\geq 1 , let w^{\ell}_{G}(u) be the number of walks of length \ell starting at u in G . Let W^{\ell}(G)=\sum_{v\in V(G)}w^{\ell}_{G}(u) . The following spectral formula was given in [ 9 ] . Theorem 2.1 ( [ 9 ] ) For an integer r\geq 2 , let K_{n_{1},n_{2},...,n_{r}} be the complete r -partite graph of order n with parts V_{1},V_{2},...,V_{r} , where n_{i}=|V_{i}|\geq 1 for 1\leq i\leq r and \sum_{1\leq i\leq r}n_{i}=n . For each 1\leq i\leq r , let H_{i} be a graph with vertex set V(H_{i})\subseteq V_{i} . Let G be the graph obtained from K_{n_{1},n_{2},...,n_{r}} by embedding the edges of H_{i} into V_{i} for all 1\leq i\leq r . Set \rho=\rho(G) . Then \sum_{1\leq s\leq r}\frac{1}{1+\frac{n_{s}}{\rho}+\sum^{\infty}_{i=1}\frac{W^{i}(H_{s})}{\rho^{i+1}}}=r-1. The existence of the infinite series in Theorem 2.1 was guaranteed by the following two results. The first one is taken from Theorem 8.1.1 of [ 2 ] . Lemma 2.2 ( [ 2 ] ) If H is a subgraph of a connected graph G , then \rho(H)\leq\rho(G) , with equality if and only if H=G . Lemma 2.3 ( [ 9 ] ) Let G be a graph of order n . Then \sum^{\infty}_{k=1}\frac{W^{k}(G)}{x^{k}} exists for any x>\rho(G) . 3 Proofs of Lemmas 1.1 , 1.2 and 1.3 Let G be a graph. For a vertex u and a walk Q of G , we say that Q crosses u , if u is one of the vertices in the sequence of Q . For any integer \ell\geq 1 and u,v\in V(G) , let W^{\ell}_{u,v}(G) be the number of walks Q of length \ell in G , such that Q crosses u and v . Recall that P_{0} denotes the empty graph. Lemma 3.1 For integers n_{1}\geq n_{2}+2\geq 3 , denote P_{n_{1}}=u_{1}u_{2}\cdots u_{n_{1}} . Then W^{\ell}(P_{n_{1}}\cup P_{n_{2}})-W^{\ell}(P_{n_{1}-1}\cup