Source-linked AI summary
Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs
Mingqing Zhai, Huiqiu Lin, Jinlong Shu
TL;DR
The paper asks which subgraphs must occur in a graph when its spectral radius exceeds a threshold near sqrt(m). It studies fixed-edge forbidden-subgraph classes and derives spectral-radius bounds and conditions forcing cycles. In K2,r+1-free graphs with r≥2 and m≥16r², ρ(G)≤√m, with equality if and only if G is a star; the cited argument also yields cycles Ct for every t≤2k+2.
Problem
The paper asks which subgraphs must occur in a graph when its spectral radius exceeds a threshold near sqrt(m).
Source: §1 · p. 2Method
It studies fixed-edge forbidden-subgraph classes and derives spectral-radius bounds and conditions forcing cycles.
Source: §1 · pp. 2–3, §5 · p. 19Results
In K2,r+1-free graphs with r≥2 and m≥16r², ρ(G)≤√m, with equality if and only if G is a star; the cited argument also yields cycles Ct for every t≤2k+2.
Source: §1 · p. 2, §5 · p. 19Takeaways & Limitations
The stated spectral conditions yield forced-subgraph conclusions while allowing exceptions such as stars, books, and complete bipartite graphs.
Source: §1 · pp. 2–3The C5-free result’s m ≥ 8 condition is best possible.
Source: §4 · p. 12
Abstract
from arXiv · showhide
Nikiforov [Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 179--189] showed that if $G$ is $K_{r+1}$-free then the spectral radius $\rho(G)\leq\sqrt{2m(1-1/r)}$, which implies that $G$ contains $C_3$ if $\rho(G)>\sqrt{m}$. In this paper, we follow this direction on determining which subgraphs will be contained in $G$ if $\rho(G)> f(m)$, where $f(m)\sim\sqrt{m}$ as $m\rightarrow \infty$. We first show that if $\rho(G)\geq \sqrt{m}$, then $G$ contains $K_{2,r+1}$ unless $G$ is a star; and $G$ contains either $C_3^+$ or $C_4^+$ unless $G$ is a complete bipartite graph, where $C_t^+$ denotes the graph obtained from $C_t$ and $C_3$ by identifying an edge. Secondly, we prove that if $\rho(G)\geq{\frac12+\sqrt{m-\frac34}}$, then $G$ contains pentagon and hexagon unless $G$ is a book; and if $\rho(G)>{\frac12(k-\frac12)+\sqrt{m+\frac14(k-\frac12)^2}}$, then $G$ contains $C_t$ for every $t\leq 2k+2$. In the end, some related conjectures are provided for further research.
1 Introduction
The introduction frames a fixed-edge spectral Turán question: which subgraphs must occur when a graph’s spectral radius exceeds a threshold near sqrt(m)? It presents bounds for forbidden-subgraph classes and spectral conditions forcing short and consecutive-length cycles.
1 Introduction
- The introduction situates these results within spectral Turán problems, which maximize spectral radius among forbidden-subgraph graphs with a fixed number of edges.Source: §1 · p. 2
- The paper also treats graphs avoiding C3+ and C4+, generalizing results on triangle-free and C4-free graphs.Here C_t+ is formed by identifying an edge of C_t with an edge of a triangle.Source: §1 · p. 2
- For r ≥ 2 and m ≥ 16r^2, every K2,r+1-free graph has spectral radius at most sqrt(m), with equality only for a star.Source: §1 · p. 2
- For C5-free or C6-free graphs, Theorem 1.4 gives spectral-radius bounds and characterizes equality using complete split graphs.The stated edge thresholds are m ≥ 8 for C5 and m ≥ 22 for C6; the complete split graph S_n,k joins each vertex of K_k to n−k isolated vertices.Source: §1 · pp. 2–3
- Building on spectral criteria for consecutive cycles, the paper gives an edge-count analogue whose conclusion includes every cycle length t ≤ 2k+2.The cited earlier results concern graphs specified by vertex order and even-cycle conclusions.Source: §1 · p. 3
2 Basic lemmas
The section sets notation for graph neighborhoods, edge counts, and extremal graphs. It also gives structural properties of an extremal graph and a spectral-radius comparison lemma used in later proofs.
2 Basic lemmas
- If two connected graphs on the same vertex set differ in the neighborhood of a vertex, a nondecreasing adjacency quadratic form on G's Perron vector implies the modified graph has larger spectral radius.This comparison is attributed to.Source: §2 · p. 3
- The Perron vector of G* identifies u* as a vertex with maximum coordinate, and the sets N_i(u*) group its neighbors by their degree within N(u*).The section also defines neighborhoods, distance-two neighborhoods, induced subgraphs, and edge counts between vertex sets.Source: §2 · p. 3
- For a 2-connected forbidden graph F, an extremal graph G* is connected and has no cut vertex outside its maximum-Perron-coordinate vertex u*; if F is C4-free, nonadjacent degree-two vertices have identical neighborhoods.In particular, every vertex outside N[u*] has degree at least two.Source: §2 · p. 3
3 Proof of Theorem 1.3
The proof characterizes extremal graphs under forbidden-subgraph conditions using an extremal vertex and its neighborhoods. It concludes that the relevant extremal graphs are stars, complete bipartite graphs, or specified small split graphs, depending on the case.
3 Proof of Theorem 1.3
- For the K2,r+1-free extremal graph, the proof concludes G* is a star K1,m when m is at least 16r^2.The argument first establishes that if the extremal graph is bipartite, it is complete bipartite, and excludes both sides having size at least two.Source: §3 · pp. 5, 7
- The condition m≥9 in Theorem 1.3(ii) is best possible, and the listed nine-edge split graphs have spectral radius 3.The proof gives the largest root of the relevant polynomial as 3 for (n,k)=(9,1),(8,2),(7,3).Source: §3 · p. 7
- The proof establishes e(W)=0, as desired; in the cited passage, that conclusion is stated to follow from Lemmas 3.3 and 3.4.Source: §3 · p. 10
- When N1(u*) is empty in the {C3+, C4+}-free case, G* is triangle-free and hence complete bipartite.Here N1(u*) consists of neighbors of u* having one neighbor within N(u*).Source: §3 · p. 10
- The proof obtains a contradiction from e(W)<0, concludes W=∅, and then states that G* is isomorphic to one of S^3_7, S^2_8, or S^1_9.Here S^k_n is obtained from K1,n−1 by adding k disjoint edges within its independent set; e(S^k_n)=3 for (n,k)=(9,1),(8,2),(7,3).Source: §3 · pp. 7, 11
4 Proof of Theorem 1.4
The proof characterizes extremal graphs under C5- and C6-free constraints using structure around a maximum-degree vertex. It establishes Theorem 1.4(i) for C5-free graphs and derives neighborhood and exterior restrictions for C6-free graphs, including a join structure for G*.
C5-free extremal structure
- For m ≥ 8, ρ(H_{t,0} ◦ R_k) is below the stated threshold; the m ≥ 8 condition is best possible, since the m = 7 graph is C5-free and exceeds it.At m = 7, H_{1,0} ◦ R_1 has spectral radius greater than ρ⋆ = 3.Source: §4 · pp. 11–12
- For C5-free extremal graphs, every component of G*[N(u*)] is a triangle or a star K_{1,r}, including an isolated vertex.The restriction follows because G*[N(u*)] contains no path of length 3.Source: §4 · p. 12
Proof of Theorem 1.4 (i)
- Theorem 1.4(i) concludes that the extremal C5-free graph is S_{m+3/2,2}.The proof first narrows the candidates to this graph or H_{t,s} ◦ R_k, then rules out the latter.Source: §4 · pp. 13, 15
C6-free extremal structure
- For C6-free extremal graphs, G*[N(u*)] contains no cycle of length four or more.The proof further shows that e(W) = 0 and G*[N(u*)] contains no triangle, so its components are trees.Source: §4 · pp. 15, 17, 18
- In the C6-free case, the number of non-trivial tree components in G*[N(u*)] is at most one; if there is one, N_0(u*) is empty.If there are no non-trivial tree components, the proof identifies G* as bipartite.Source: §4 · p. 18
4 Proof of Theorem 1.4
- WH is empty, so G* is the join of u* with the star H.The proof rules out vertices of WH using the absence of hexagons and Lemma 2.2.Source: §4 · p. 19
- H has diameter at most 2 and is a star K1,r, with r > 4.The proof excludes diameter 3 using the C6-free condition and Lemma 2.2; the lower bound follows from ρ* > 5 and the stated eigenvector bound.Source: §4 · p. 19
5 Concluding remarks
The concluding remarks connect the paper’s spectral conditions to the existence of consecutive cycle lengths, then pose conjectures about extending those bounds and identifying graph families with spectral radius at most √m.
5 Concluding remarks
- A path P_{2k+1} in G[N(j*)] yields cycles C_t for every t≤2k+2.This is the final cycle argument in the paper.Source: §5 · p. 19
- The paper’s short-cycle results guarantee C3 and C4 unless G is a star, and cycles through C6 unless G is a book.The conclusion invokes these results as motivation for a more general condition on consecutive cycle lengths.Source: §5 · p. 19
- Conjecture 5.1 predicts cycles of every length through 2k+2 under a spectral condition, with a specified S-family exception.It is presented as a generalization of the paper’s consecutive-cycle results.Source: §5 · pp. 19–20
- The conclusion asks how large a graph family can have ρ≤√m and proposes that graphs avoiding B_{r+1} satisfy this bound for sufficiently large m.The paper identifies complete bipartite graphs as an equality case for the √m bound.Source: §5 · p. 20