Spectral extremal problem for the odd prism
Xinhui Duan, Lu Lu · 2025
Read Spectral extremal problem for the odd prism by Xinhui Duan, Lu Lu (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-2507-01266.txt.
Introduction
Xinhui Duan and Lu Lu published this mathematics paper in 2025. It settles an extremal question about graphs that avoid the odd prism, a shape built by joining two copies of an odd cycle with matching rungs. The spectral Turan number asks how large a graph's spectral radius can grow while dodging that shape. Duan and Lu determine the number exactly for all large enough graphs and identify the unique graph that reaches it.
Catalog record
| CREATOR | Xinhui Duan, Lu Lu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-01266
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Spectral extremal problem for the odd prism Xinhui Duan, Lu Lu Abstract The spectral Turán number spex ( n , F ) \textrm{spex}(n,F) denotes the maximum spectral radius ρ ( G ) \rho(G) of an F F -free graph G G of order n n . This paper determines spex ( n , C 2 k + 1 □ ) \textrm{spex}\left(n,C_{2k+1}^{\square}\right) for all sufficiently large n n , establishing the unique extremal graph. Here, C 2 k + 1 □ C_{2k+1}^{\square} is the odd prism, which is the Cartesian product C 2 k + 1 □ K 2 C_{2k+1}\square K_{2} , where the Cartesian product G □ F G\square F has vertex set V ( G ) × V ( F ) V(G)\times V(F) , and edges between ( u 1 , v 1 ) (u_{1},v_{1}) and ( u 2 , v 2 ) (u_{2},v_{2}) if either u 1 = u 2 u_{1}=u_{2} and v 1 v 2 ∈ E ( F ) v_{1}v_{2}\in E(F) , or v 1 = v 2 v_{1}=v_{2} and u 1 u 2 ∈ E ( G ) u_{1}u_{2}\in E(G) . AMS Classification : 05C50 Keywords : Spectral radius, Spectral extremal graph, Turán problem. 1 Introduction In this paper, all graphs considered are undirected, finite and simple. Let G be a graph with vertex set V(G) and edge set E(G) . Let K_{n} be the complete graph on n vertices, and K_{s,t} be the complete bipartite graph with parts of sizes s and t . We write C_{n} and P_{n} for the cycle and path on n vertices, respectively. The complement \overline{G} of G is the graph with vertex set V(G) and edge set \{uv\mid uv\notin E(G)\} . For two vertex-disjoint graphs G and H , the union of G and H is the graph G\cup H with vertex set V(G)\cup V(H) and edge set E(G)\cup E(H) . In particular, we write kG to denote the vertex-disjoint union of k copies of G . The join of G and H , denoted by G\vee H , is the graph obtained from G\cup H by adding edges between every vertex of G and every vertex of H . For positive integers n_{1},\cdots,n_{r} , the complete r -partite graph K_{n_{1},\cdots,n_{r}} is defined as \overline{K_{n_{1}}\cup\cdots\cup K_{n_{r}}} . The r -partite Turán graph on n vertices, T_{n,r} , is the completer-partite graph K_{n_{1},\cdots,n_{r}} with \max\{|n_{i}-n_{j}|\mid 1\leq i,j\leq r\}\leq 1 . The Cartesian product of graphs G and F , denoted by G\square F , has vertex set V(G)\times V(F) , in which two distinct vertices (u_{1},v_{1}) and (u_{2},v_{2}) are adjacent in G\square F if either u_{1}=u_{2} and v_{1}v_{2}\in E(F) , or v_{1}=v_{2} and u_{1}u_{2}\in E(G) . A graph G is F -free if it contains no subgraph isomorphic to F . For a family of graphs \mathcal{F} , G is \mathcal{F} -free if it is F -free for every F\in\mathcal{F} . The Turán number \textrm{ex}(n,F) is defined as \textrm{ex}(n,F)=\max\left\{e(G)\mid G\in\mathcal{G}_{n}\text{ and }G\text{ is }F\text{-free}\right\}, with \textrm{EX}(n,F) denoting the set of extremal graphs: \textrm{EX}(n,F)=\left\{G\in\mathcal{G}_{n}\mid G\text{ is }F\text{-free and }e(G)=\textrm{ex}(n,F)\right\}. The classical Turán theorem states \textrm{EX}(n,K_{r+1})=\{T_{n,r}\} . Since K_{4} is the tetrahedron, Turán further posed an analogous problem: Determine the Turán number for graphs defined by the vertices and edges of regular polyhedrons. Examples include the cube Q_{8} and octahedron O_{6} (Fig. 1.1 ). This problem has been extensively studied: see [ 8 , 10 , 18 , 19 , 21 ] for Q_{8} ; [ 9 ] for O_{6} ; [ 22 ] for the dodecahedron D_{20} ; and [ 23 ] for the icosahedron I_{12} . Related work includes Turán numbers for wheels (Dzido [ 5 ] , Dzido and Jastrzebski [ 6 ] , Yuan [ 24 ] ) and extremal graphs for cycyle (Ore [ 20 ] , Füredi and Gunderson [ 11 ] ). Figure 1.1 : The three regular polyhedrons. In 2022, Bradac̆, Janzer, Sudakov and Tomon [ 1 ] studied the Turán number of the grid P_{t}\square P_{t} , where P_{t} is the path on t vertices. More precisely, the proved that for t\geq 2 , threr exist positive numbers C_{1} and C_{2} depending only on t such that C_{1}n^{3/2}\leq\textrm{ex}(n,P_{t}\square P_{t})\leq C_{2}n^{3/2} . The odd prism C_{2k+1}^{\square} is defined as C_{2k+1}^{\square}:=C_{2k+1}\square K_{2} . The triangular prism is shown in Fig. 1.2 . He, Li and Feng [ 12 ] consider the Turán number of C_{2k+1}^{\square} . Figure 1.2 : The C_{3}^{\square} graph. Theorem 1.1 ( [ 12 ] ) . Let k\geq 1 be fixed and n be sufficiently large. Then \textrm{ex}(n,C_{2k+1}^{\square})=\underset{n_{a}+n_{b}=n}{\max}\left\{n_{a}(1+n_{b})+\frac{1}{2}(j^{2}-3j):j\in\{0,1,2\},j\equiv n_{a}(\bmod 3)\right\}. Moreover, all extremal graphs for C_{2k+1}^{\square} are of the form of a complete bipartite graph K_{n_{a},n_{b}} with an extremal graph for P_{4} added to the part of size n_{a} . Given a graph G , let A(G) be its adjacency matrix, and \lambda(G) its spectral radius. The spectral Turán number for a graph F is defined as \textrm{spex}(n,F)=\max\left\{\lambda(G)\mid G\in\mathcal{G}_{n}\text{ and }G\text{ is }F\text{-free}\right\}, with \textrm{SPEX}(n,F) denoting the set of extremal graphs: \textrm{SPEX}(n,F)=\left\{G\in\mathcal{G}_{n}\mid G\text{ is }F\text{-free and }\lambda(G)=\textrm{spex}(n,F)\right\}. This problem has attracted significant attention over the past decades, with results established for numerous specific graphs F ; comprehensive surveys are found in [ 4 , 13 , 17 ] . Specially, Nikiforov [ 15 ] determined \textrm{spex}(n,C_{2k+1}) for sufficiently large n . Nikiforov [ 14 ] and Zhai and Wang [ 25 ] determined the unique extremal graph with respect to \textrm{spex}(n,C_{4}) for odd and even n , respectively. Subsequently, Zhai and Lin [ 25 ] determined the unique extremal graph with respect to \textrm{spex}(n,C_{6}) . Very recently, Cioabă, Desai and Tait [ 2 ] determined the unique extremal graph with respect to \textrm{spex}(n,C_{2k}) for k\geq 3 and n large enough. In this paper, we completely determine \textrm{SPEX}(n,C_{2k+1}^{\square}) for large enough n . Theorem 1.2 . Let k\geq 1 be integer. Let n be an sufficiently large integer, and G a n -vertex C_{2k+1}^{\square} -free graph. Then \lambda(G)\leq\lambda(K_{1}\vee T_{n-1,2}), with equality holds if and only if G=K_{1}\vee T_{n-1,2} . 2 Preliminary Let G be a simple connected graph on n vertices with vertex set V(G) and edge set E(G) . For a vertex v\in V(G) and a subset S\subseteq V(G) , let N(v) be the neighborhood of v , N_{S}(v)=N(v)\cap S , and N(S)=\bigcup_{u\in S}N(u) . Denote d(v)=|N(v)| as the degree of v , and d_{S}(v)=|N_{S}(v)| as the degree of v in S . For V_{1},V_{2}\subseteq V(G) , let E(V_{1},V_{2}) denote the set of edges of G with one endpoint in V_{1} and the other endpoint in V_{2} , and e(V_{1},V_{2})=|E(V_{1},V_{2})| . Denote G-S as the graph obtained from G by deleting all vertices in S along with their incident edges. This subgraph is also called the subgraph induced by \overline{S}=V(G)\setminus S and is denoted by G[\overline{S}] . Particularly, if S=\left\{u\right\} , then we write G-u for G-S . The adjacency matrix of G is A(G)=(a_{ij})_{n\times n} , where a_{ij}=1 if ij\in E(G) , and a_{ij}=0 otherwise. The spectral radius of G is the largest eigenvalue of A(G) , denoted by \lambda(G) . For a connected graph G on n vertices, by the famous Perron-Frobenius