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

CREATORXinhui Duan, Lu Lu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text