Spectral extremal problem of the p p th power of cycles

Xinhui Duan, Lu Lu · 2025

Read Spectral extremal problem of the p p th power of cycles 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-2508-03746.txt.

Introduction

Xinhui Duan and Lu Lu solve a spectral extremal problem about powers of cycles. Their twenty twenty-five mathematics paper works with graphs that avoid a fixed pattern. A cycle power joins vertices that sit close along the cycle. Two measures matter here: the most edges possible, and the largest spectral radius.

The authors pin down the single best graph for large vertex counts. That graph wins on both measures at once. Earlier work often handled edge counts and spectra separately. Getting one unique winner for both sharpens the picture. Graph theorists can use the result as a benchmark for related forbidden pattern problems.

Catalog record

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

Source: https://arxiv.org/abs/2508-03746

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 of the p p th power of cycles Xinhui Duan, Lu Lu Abstract For a cycle C k C_{k} on k k vertices, its p p -th power, denoted C k p C_{k}^{p} , is the graph obtained by adding edges between all pairs of vertices at distance at most p p in C k C_{k} . Let ex ​ ( n , F ) \textrm{ex}(n,F) and spex ​ ( n , F ) \textrm{spex}(n,F) denote the maximum possible number of edges and the maximum possible spectral radius, respectively, among all n n -vertex F F -free graphs. In this paper, we determine precisely the unique extremal graph achieving ex ​ ( n , C k p ) \textrm{ex}(n,C_{k}^{p}) and spex ​ ( n , C k p ) \textrm{spex}(n,C_{k}^{p}) for sufficiently large n n . 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 . Denote by \nu(G) the matching number, \chi(G) the chromatic number and \delta(G) the minimum degree. Let G^{k} be the k -power of a graph G , which is obtained by joining all pairs of vertices with distance at most k in G . We write C_{k}^{p} and P_{k}^{p} for the p -power of a cycle C_{k} and a path P_{k} , respectively. 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 study of Turán numbers for P_{k}^{p} and C_{k}^{p} has a long history in extremal graph theory. Xiao et al. [ 16 ] determined \textrm{ex}(n,P_{5}^{2}) and \textrm{ex}(n,P_{6}^{2}) for all n and conjectured a general formula for \textrm{ex}(n,P_{k}^{2}) . This conjecture was later resolved by Yuan [ 17 ] , who fully characterized \textrm{EX}(n,P_{k}^{p}) . For cycles, Ore [ 13 ] first determined \textrm{ex}(n,C_{n}) in 1961, while Khan and Yuan [ 8 ] established \textrm{ex}(n,C_{n}^{2}) in 2022. The classical Mantel Theorem gives \textrm{ex}(n,C_{3}) , and Füredi and Gunderson [ 5 ] described \textrm{ex}(n,C_{2k+1}) for k\geq 2 . The most recent results on \textrm{ex}(n,C_{2k+2}) can be found in [ 7 ] . When considering squared cycles ( p=2 ), the Turán number \textrm{ex}(n,C_{k}^{2}) is immediate from Turán’s Theorem [ 15 ] for 3\leq k\leq 5 , since C_{k}^{2}\cong K_{k} in these cases. For k\geq 6 , Fang and Zhao [ 6 ] completely determined \textrm{EX}(n,C_{k}^{2}) for sufficiently large n when 3\nmid k . Motivated by these works, we aim to fully characterize \textrm{EX}(n,C_{k}^{p}) , generalizing Fang and Zhao’s result. Since C_{k}^{p}\cong K_{k} when p\geq\lfloor k/2\rfloor , it suffices to consider the case p<\lfloor k/2\rfloor . Our main result is as follows. Theorem 1.1 . For two integers k and p with k\geq 2p+1 , assume k=s(p+1)+r for some s\geq 1 and 0\leq r<p+1 . Let 0\leq m and 1\leq t\leq s be the unique integer satisfying r=ms+t . If r\neq 0 , then \textrm{EX}(n,C_{k}^{p})=\{K_{t-1}\vee T_{n-t+1,p+m+1}\} for large enough n . 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\}. The problem of spectral Turán number has attracted significant attention over the past decades, with results established for numerous specific graphs F ; comprehensive surveys are found in [ 3 , 9 , 12 ] . Specially, Nikiforov [ 11 ] determined \textrm{spex}(n,C_{2k+1}) for sufficiently large n . Nikiforov [ 10 ] and Zhai and Wang [ 19 ] determined \textrm{SPEX}(n,C_{4}) for odd n and even n , respectively. Subsequently, Zhai and Lin [ 19 ] determined \textrm{SPEX}(n,C_{6}) . Very recently, Cioabă, Desai and Tait [ 1 ] obtained \textrm{SPEX}(n,C_{2k}) for k\geq 3 and n large enough. Yan, He, Feng and Liu [ 18 ] obtained \textrm{SPEX}(n,C^{2}_{n}) for n\geq 15 , and they expected that the extremal graph with respect to \textrm{spex}(n,C^{k}_{n}) for n large enough may be the graph K_{n}\setminus E(S_{n-2k+1}) , where S_{n-2k+1} is the star of order n-2k+1 . For any integer k\geq 6 with 3\nmid k , Fang and Zhao [ 6 ] also characterized \textrm{SPEX}(n,C_{k}^{2}) for sufficient n . So, we would like to characterize \textrm{SPEX}(n,C_{k}^{p}) . Theorem 1.2 . For two integers k and p with k\geq 2p+1 , assume k=s(p+1)+r for some s\geq 1 and 0\leq r<p+1 . Let 0\leq m and 1\leq t\leq s be the unique integer satisfying r=ms+t . If r\neq 0 and t\neq s , then \textrm{SPEX}(n,C_{k}^{p})=\{K_{t-1}\vee T_{n-t+1,p+m+1}\} for large enough n . 2 Proof of Theorem 1.1 For any positive integer k , a graph G is called color- k -critical if there exist k suitable edges whose removal decreases its chromatic number, and deleting any k-1 vertices does not decrease its chromatic number. It is clear from the definition that any k edges whose removal decreases \chi(G) must form a matching of size k . In particular, color-1-critical graphs are just color-critical graphs. In [ 14 ] , Simonovits determined the unique extremal graph for every color- k -critical graph. Lemma 2.1 ( [ 14 ] ) . Let k\geq 1 and let H be a a color- k -critical graph with chromatic number \chi(H)=r+1 . Then \textrm{EX}(n,H)=\{K_{k-1}\vee T_{n-k+1,r}\} for sufficiently large n . Lemma 2.2 . For two integers k and p with k\geq 2p+1 , assume k=s(p+1)+r for some s\geq 1 and 0\leq r<p+1 . If r=0 , then \chi(C_{k}^{p})=p+1 . If r\neq 0 , let r=ms+t for m\geq 0 and 1\leq t\leq s , then \chi(C_{k}^{p})=p+m+2 and C_{k}^{p} is a color- t -critical. Proof. Assume V(C_{k}^{p})=\{v_{0},v_{1},\ldots,v_{k-1}\} such that v_{0}v_{1}\cdots v_{k-1}v_{0} forms the cycle C_{k} . First, we consider the case r=0 . Color the vertex v_{i} with the color a if

Read the complete text