Median eigenvalues of subcubic graphs
Hricha Acharya, Benjamin Jeter, Zilin Jiang · 2025
Read Median eigenvalues of subcubic graphs by Hricha Acharya, Benjamin Jeter, Zilin Jiang (2025) 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-2502-13139.txt.
Introduction
Hricha Acharya, Benjamin Jeter, and Zilin Jiang settle open questions about the middle eigenvalues of sparse networks. A graph links points by edges, and its eigenvalues summarize its shape. For networks where each point has at most three edges, the middle values were long suspected to stay small. One special graph, the Heawood graph, breaks the pattern. The authors prove that every other connected graph of this kind has median eigenvalues no larger than one in size. Two open problems, posed by Fowler and Pisanski and by Mohar, are resolved.
Catalog record
| CREATOR | Hricha Acharya, Benjamin Jeter, Zilin Jiang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 241 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-13139
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Median eigenvalues of subcubic graphs Hricha Acharya, Benjamin Jeter, Zilin Jiang Abstract We show that the median eigenvalues of every connected graph of maximum degree at most three, except for the Heawood graph, are at most 1 1 in absolute value, resolving open problems posed by Fowler and Pisanski, and by Mohar. \setlistdepth 7 1 Introduction A graph is subcubic if its maximum degree is at most 3 . In mathematical chemistry, connected subcubic graphs are often referred to as chemical graphs because they naturally model the skeletons of organic molecules, where atoms such as carbon typically form bonds with up to three neighboring atoms. The study of connected subcubic graphs has significant applications in theoretical chemistry, particularly in the analysis of molecular orbital models. For instance, in the Hückel molecular orbital model, the eigenvalues of a molecule’s skeleton graph correspond to its \pi -electron energy levels. Among these, the median eigenvalues — associated with the highest occupied molecular orbital (HOMO) and the lowest unoccupied molecular orbital (LUMO) — are of particular interest (see [ 11 , 17 ] and the references therein). To formalize, let G be an n -vertex graph, and let \lambda_{1}(G)\geq\lambda_{2}(G)\geq\dots\geq\lambda_{n}(G) denote the eigenvalues of its adjacency matrix. The median eigenvalues are defined as \lambda_{h} and \lambda_{l} , where h=\lfloor(n+1)/2\rfloor and l=\lceil(n+1)/2\rceil . Computational studies of Fowler and Pisanski [ 4 , 5 ] suggest that the median eigenvalues of most connected subcubic graphs lie in the interval [-1,1] . However, there is a single notable exception: the Heawood graph, whose median eigenvalues are \pm\sqrt{2} (see Figure 1 ). The Heawood graph is the incidence graph of the Fano plane, that is, the projective plane of order 2 . Figure 1 : The Heawood graph. Fowler and Pisanski [ 4 ] conjectured that the median eigenvalues of all but finitely many connected subcubic graphs lie in [-1,1] , and they confirmed their conjecture for all connected subcubic trees. The interval [-1,1] would be optimal because of the construction of an infinite family of bipartite connected subcubic graphs whose median eigenvalues are \pm 1 by Guo and Mohar [ 6 ] . Subsequently, Mohar [ 13 ] conjectured that the median eigenvalues of all planar subcubic graphs lie in [-1,1] , and he confirmed in [ 12 ] his conjecture for all bipartite planar subcubic graphs. We point out that the Heawood graph is bipartite but not planar. Later, Mohar [ 14 ] greatly extended his result to all bipartite connected subcubic graphs, except for the Heawood graph. In addition, he refined his proof to show that a positive fraction of the eigenvalues around the median eigenvalues belong to [-1,1] (see [ 14 , Theorem 1.4] ). Recently, Wang and Zhang [ 16 ] supplemented Mohar’s main result in [ 14 ] by treating connected subcubic graphs that contain K_{2,3} as a subgraph, as well as those that contain no K_{4} as a minor. The latter generalizes an earlier result of Benediktovich [ 2 ] for outerplanar connected subcubic graphs. Concurrent with our work, Chen, Wang and Zhang [ 3 ] proved that the median eigenvalues lie in [-1,1] for connected subcubic graphs in which every subgraph has average degree less than 44/17 , and also for planar connected subcubic graphs of girth at least 8 . We completely settle the aforementioned conjectures in a strong form. Theorem 1.1 . The median eigenvalues of every connected subcubic graph, except for the Heawood graph, lie in the interval [-1,1] . Just like Mohar’s result [ 14 , Theorem 1.4] , our proof can also be extended to a positive fraction of the eigenvalues around the medians for large connected subcubic graphs. Theorem 1.2 . There exists a constant \eta>0 such that for every connected subcubic graph G on n vertices, the i -th largest eigenvalue \lambda_{i}(G) of G lies in [-1,1] for every integer i\in[\tfrac{1}{2}(1-\eta)(n+1),\tfrac{1}{2}(1+\eta)(n+1)] . Remark . When G is the Heawood graph, or more generally, when G is a small graph on an even number of vertices, Theorem 1.2 holds for the trivial reason that [\tfrac{1}{2}(1-\eta)(n+1),\tfrac{1}{2}(1+\eta)(n+1)] contains no integers. 2 Proof ideas The use of the Cauchy interlacing theorem in the context of median eigenvalues of connected subcubic graphs first appeared in [ 12 ] . We use the following immediate consequence of the Cauchy interlacing theorem to control graph eigenvalues. Definition 2.1 (Tails and their estimates) . Given a graph G , its positive tail , denoted by t^{+}_{G} , is the number of eigenvalues greater than 1 , and its negative tail , denoted by t^{-}_{G} , is the number of eigenvalues less than -1 . Furthermore, given a vertex subset A of G , the positive tail estimate of G with respect to A is defined by t^{+}_{G}(A):=\lvert A\rvert+t^{+}_{G-A}, and the negative tail estimate of G with respect to A is defined by t^{-}_{G}(A):=\lvert A\rvert+t^{-}_{G-A}. Lemma 2.2 . For every vertex subset A of a graph G , the positive tail t^{+}_{G} of G is at most the positive tail estimate t^{+}_{G}(A) , and the negative tail t^{-}_{G} of G is at most the negative tail estimate t^{-}_{G}(A) . Proof. Set k=t_{G-A}^{+} . Thus \lambda_{k+1}(G-A)\leq 1 . By the Cauchy interlacing theorem, \lambda_{\lvert A\rvert+k+1}(G)\leq 1 , and so t_{G}^{+}\leq\lvert A\rvert+k=t_{G}^{+}(A) . Similarly, one can also show that t^{-}_{G}\leq t^{-}_{G}(A) . ∎ The maximum cut naturally provides a good starting point for tail estimates. Proposition 2.3 . For every maximum cut (A,B) of a subcubic graph G , the edges of G[A]\cup G[B] form a matching in G , and, in particular, t_{G}^{\pm}(A)=\lvert A\rvert and t_{G}^{\pm}(B)=\lvert B\rvert . Proof. Suppose that some vertex v\in A has at least two neighbors in A . Since G is subcubic, v has at most one neighbor in B . Moving v from A to B therefore increases the size of the cut-set, contradicting the maximality of (A,B) . The same argument applies to vertices in B , and so every vertex has degree at most 1 in G[A]\cup G[B] . Hence the edges of G[A]\cup G[B] form a matching in G . In particular, G[A] and G[B] are disjoint unions of isolated vertices and edges, so all their eigenvalues lie in [-1,1] . Therefore t^{\pm}_{G-A}=t^{\pm}_{G[B]}=0 and t^{\pm}_{G-B}=t^{\pm}_{G[A]}=0 , which gives t_{G}^{\pm}(A)=\lvert A\rvert and t_{G}^{\pm}(B)=\lvert B\rvert . ∎ If \lvert A\rvert\neq\lvert B\rvert for some maximum cut (A,B) of G , then Lemmas 2.2 and 2.3 imply that t_{G}^{\pm}\leq\min(\lvert A\rvert,\lvert B\rvert)<\lvert G\rvert/2 , and so the median eigenvalues of G lie in [-1,1] . It remains to handle graphs whose maximum cuts are all balanced, that is, \lvert A\rvert=\lvert B\rvert for every maximum cut (A,B) of G . The remaining case requires more work. The strategy is to adjust the maximum cut to improve the tail estimates of G . This follows the philosophy of Mohar’s imbalance argument [ 14 ] . We package the adjustments that decrease tail estimates in the following definitions. Definition 2.4 (Tail reducers) . Given a cut (A,B) of a graph G , a vertex subset D of G is a positive tail reducer (respectively, negative tail reducer ) of G with respect to (A,B) if either D\subseteq A or D\subseteq B , and