Extremal eigenvalues of graphs embedded on surfaces
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915749624283136 |
|---|---|
| author | Zhai, Mingqing Fang, Longfei Lin, Huiqiu |
| author_facet | Zhai, Mingqing Fang, Longfei Lin, Huiqiu |
| contents | Graph theory on surfaces extends classical graph structures to topological surfaces, providing a theoretical foundation for characterizing the embedding properties of complex networks in constrained spaces. The study of bounding the spectral radius $ρ(G)$ of graphs on surfaces has a rich history that dates back to the 1990s. In this paper, we establish tight bounds for graphs of order $n$ that are embeddable on a surface with Euler genus $γ$. Specifically, if graph $G$ achieves the maximum spectral radius, then \begin{equation*} \begin{array}{ll} \frac32\!+\!\sqrt{2n\!-\!\frac{15}4}\!+\!\frac{3γ\!-\!1}{n}<ρ(G)<\frac32\!+\!\sqrt{2n\!-\!\frac{15}4}\!+\!\frac{3γ\!-\!0.95}{n}, \end{array} \end{equation*} which improves upon the earlier bound $ρ(G)\leq2+\sqrt{2n+8γ-6}$ by Ellingham and Zha [JCTB, 2000]. Furthermore, we prove that any extremal graph is obtained from $K_2 \nabla P_{n-2}$ by adding exactly $3γ$ edges, where `$\nabla$' means the join product. As a corollary, for $γ= 0$ and $n \geq 4.5 \times 10^6$, the graph $K_2 \nabla P_{n-2}$ is the unique planar extremal graph, thereby confirming a long-standing conjecture resolved by Tait and Tobin [JCTB, 2017].
Let $K_r^n$ be the graph of order $n$ obtained by attaching two paths of nearly equal length to two distinct vertices of $K_r$. Integrating spectral techniques with considerable structural analysis on surface graphs, we further derive the following sharp bounds: $ρ(G) \leq ρ(K_2 \nabla K_4^{n-2})$ for projective-planar graphs, and $ρ(G) \leq ρ(K_2 \nabla K_5^{n-2})$ for toroidal graphs. Our study presents a novel framework for exploring the eigenvalue-extremal problem on surface graphs with high Euler genus. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_16380 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Extremal eigenvalues of graphs embedded on surfaces Zhai, Mingqing Fang, Longfei Lin, Huiqiu Combinatorics Graph theory on surfaces extends classical graph structures to topological surfaces, providing a theoretical foundation for characterizing the embedding properties of complex networks in constrained spaces. The study of bounding the spectral radius $ρ(G)$ of graphs on surfaces has a rich history that dates back to the 1990s. In this paper, we establish tight bounds for graphs of order $n$ that are embeddable on a surface with Euler genus $γ$. Specifically, if graph $G$ achieves the maximum spectral radius, then \begin{equation*} \begin{array}{ll} \frac32\!+\!\sqrt{2n\!-\!\frac{15}4}\!+\!\frac{3γ\!-\!1}{n}<ρ(G)<\frac32\!+\!\sqrt{2n\!-\!\frac{15}4}\!+\!\frac{3γ\!-\!0.95}{n}, \end{array} \end{equation*} which improves upon the earlier bound $ρ(G)\leq2+\sqrt{2n+8γ-6}$ by Ellingham and Zha [JCTB, 2000]. Furthermore, we prove that any extremal graph is obtained from $K_2 \nabla P_{n-2}$ by adding exactly $3γ$ edges, where `$\nabla$' means the join product. As a corollary, for $γ= 0$ and $n \geq 4.5 \times 10^6$, the graph $K_2 \nabla P_{n-2}$ is the unique planar extremal graph, thereby confirming a long-standing conjecture resolved by Tait and Tobin [JCTB, 2017]. Let $K_r^n$ be the graph of order $n$ obtained by attaching two paths of nearly equal length to two distinct vertices of $K_r$. Integrating spectral techniques with considerable structural analysis on surface graphs, we further derive the following sharp bounds: $ρ(G) \leq ρ(K_2 \nabla K_4^{n-2})$ for projective-planar graphs, and $ρ(G) \leq ρ(K_2 \nabla K_5^{n-2})$ for toroidal graphs. Our study presents a novel framework for exploring the eigenvalue-extremal problem on surface graphs with high Euler genus. |
| title | Extremal eigenvalues of graphs embedded on surfaces |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2601.16380 |