Graph operations and a unified method for kinds of Tur\'an-type problems on paths, cycles and matchings

Bo Ning; Hui Lei; Jiangdong Ai; Yongtang Shi

arxiv: 2312.08226 · v2 · submitted 2023-12-13 · 🧮 math.CO

Graph operations and a unified method for kinds of Tur\'an-type problems on paths, cycles and matchings

Jiangdong Ai , Hui Lei , Bo Ning , Yongtang Shi This is my paper

Pith reviewed 2026-05-24 04:55 UTC · model grok-4.3

classification 🧮 math.CO

keywords Turán-type problemsextremal graph theoryKelmans operationfeasible parameterspathscyclesmatchingsspectral radius

0 comments

The pith

Any feasible graph parameter is maximized by specific join graphs among 2-connected C_{≥k}-free graphs, connected P_k-free graphs, or M_{k+1}-free graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines a feasible parameter P as one that never decreases under a Kelmans operation and strictly increases when any missing edge is added. It proves that the n-vertex graphs maximizing such a P, subject to being 2-connected and free of cycles of length k or more, must belong to one explicit family of graphs formed by joining a clique of size s to a disjoint union of isolated vertices and a smaller clique. Parallel structural theorems are given for the connected P_k-free case and the connected M_{k+1}-free case. The three characterizations immediately yield extremal results for many concrete choices of P, including the number of copies of a fixed subgraph, powers of vertex degrees, and both adjacency and signless-Laplacian spectral radii.

Core claim

Let G be a 2-connected n-vertex C_{≥k}-free graph with maximum feasible P(G). Then G belongs to the family G¹_{n,k} = {K_s ∨ ((n-k+s)K_1 ∪ K_{k-2s}) : 2 ≤ s ≤ ⌊(k-1)/2⌋}. Analogous statements hold for connected P_k-free graphs, where the extremal graphs are K_s ∨ ((n-k+s+1)K_1 ∪ K_{k-2s-1}) for 1 ≤ s ≤ ⌊k/2⌋-1, and for connected M_{k+1}-free graphs, where the extremal graphs are K_s ∨ ((n-2k+s-1)K_1 ∪ K_{2k-2s+1}) for 1 ≤ s ≤ k when n ≥ 2k+2 (and the complete graph when n = 2k+1).

What carries the argument

A feasible parameter together with the Kelmans operation, which forces any maximizer to be a join of cliques and independent sets by the two monotonicity conditions.

If this is right

The ordinary Turán number ex(n, C_{≥k}) and its generalizations follow by taking P to count copies of a fixed subgraph.
Maximum degree powers and other degree-based invariants are determined by the same structural result.
Upper bounds on the adjacency spectral radius and signless-Laplacian spectral radius of C_{≥k}-free graphs are obtained by setting P equal to those radii.
The same families solve the corresponding problems for P_k-free and M_{k+1}-free graphs without additional case analysis.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The method supplies a single proof template that simultaneously settles many previously separate extremal problems once the two feasibility axioms are verified for the chosen parameter.
If a new parameter satisfies the same two axioms, its extremal graphs are immediately known without repeating the structural argument.
The technique may extend to other hereditary families closed under the Kelmans operation, yielding analogous classifications.

Load-bearing premise

The parameter must satisfy both monotonicity conditions that define feasibility.

What would settle it

Exhibit a feasible parameter P together with an n-vertex graph G that avoids the relevant forbidden subgraphs, is not isomorphic to any member of the claimed extremal family, yet satisfies P(G) strictly larger than P on every graph in the family.

read the original abstract

Let $G$ be a connected graph and $\mathcal{P}(G)$ a graph parameter. We say that $\mathcal{P}(G)$ is feasible if $\mathcal{P}(G)$ satisfies the following properties: (I) $\mathcal{P}(G)\leq \mathcal{P}(G_{uv})$, if $G_{uv}=G[u\to v]$ for any $u,v$, where $G_{uv}$ is the graph obtained by applying Kelmans operation from $u$ to $v$; (II) $\mathcal{P}(G) <\mathcal{P}(G+e)$ for any edge $e\notin E(G)$. Let $P_k$ be a path of order $k$, $\mathcal{C}_{\geq k}$ the set of all cycles of length at least $k$ and $M_{k+1}$ a matching containing $k+1$ independent edges. In this paper, we mainly prove the following three results: (i) Let $n\geq k\geq 5$ and let $t=\left\lfloor\frac{k-1}{2}\right\rfloor$. Let $G$ be a $2$-connected $n$-vertex $\mathcal{C}_{\geq k}$-free graph with the maximum $\mathcal{P}(G)$ where $\mathcal{P}(G)$ is feasible. Then, $G\in \mathcal{G}^1_{n,k}=\{W_{n,k,s}=K_{s}\vee ((n-k+s)K_1\cup K_{k-2s}): 2\leq s\leq t\}$. (ii) Let $n\geq k\geq 4$ and let $t=\left\lfloor\frac{k}{2}\right\rfloor-1$. Let $G$ be a connected $n$-vertex $P_{k}$-free graph with the maximum $\mathcal{P}(G)$ where $\mathcal{P}(G)$ is feasible. Then, $G\in \mathcal{G}^2_{n,k}=\{W_{n,k-1,s}=K_{s}\vee ((n-k+s+1)K_1\cup K_{k-2s-1}): 1\leq s\leq t\}.$ (iii) Let $G$ be a connected $n$-vertex $M_{k+1}$-free graph with the maximum $\mathcal{P}(G)$ where $\mathcal{P}(G)$ is feasible. Then, $G\cong K_n$ when $n=2k+1$ and $G\in \mathcal{G}^3_{n,k}=\{K_s\vee ((n-2k+s-1)K_1\cup K_{2k-2s+1}):1\leq s\leq k\}$ when $n\geq 2k+2$. Directly derived from these three main results, we obtain a series of applications in Tur\'an-type problems, generalized Tur\'an-type problems, powers of graph degrees in extremal graph theory, and problems related to spectral radius, and signless Laplacian spectral radius in spectral graph theory.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper unifies several Turán-type problems by defining feasible parameters and characterizing their maximizers with three explicit graph families.

read the letter

The core claim is that any feasible parameter P reaches its maximum on one of three specific families of graphs when the host graph avoids long cycles, long paths, or large matchings. The feasible condition requires P to be non-decreasing under Kelmans operations and strictly increasing on edge addition. From those two rules the authors derive the exact extremal graphs: joins of a clique with isolated vertices plus a smaller clique for the cycle case, a similar but adjusted construction for paths, and a matching-free version that collapses to the complete graph at the boundary n=2k+1. This is the new piece. Earlier papers handled one parameter or one forbidden subgraph at a time; here the same families work for spectral radius, degree powers, and other variants once they satisfy the two properties. That is useful bookkeeping inside extremal graph theory. The abstract states the three theorems cleanly and lists the derived applications without extra machinery. The construction of the families follows directly from the definition and standard operations, so there is no obvious circularity. The main limitation is that the provided text gives only the statements. Without the full proofs it is impossible to check whether the Kelmans steps cover all cases or whether the connectivity assumptions introduce hidden restrictions. The feasible condition itself is restrictive by design, but the paper treats it as the hypothesis rather than something to be verified for every P. This work is aimed at researchers who already know the individual Turán and spectral problems and want a single reference that supplies the extremal graphs for any new feasible parameter. A reader who needs the explicit maximizers for a spectral variant will get immediate value from the corollaries. The paper deserves peer review because the unification is concrete and the claims are falsifiable once the proofs are examined.

Referee Report

0 major / 3 minor

Summary. The paper defines a graph parameter P as feasible if it is non-decreasing under Kelmans operations (P(G) ≤ P(G_uv)) and strictly increases upon edge addition (P(G) < P(G+e)). It proves three structural theorems: for 2-connected n-vertex C_{≥k}-free graphs (n≥k≥5), the maximizer of feasible P belongs to the family G¹_{n,k} of graphs K_s ∨ ((n-k+s)K_1 ∪ K_{k-2s}) for 2≤s≤⌊(k-1)/2⌋; for connected n-vertex P_k-free graphs (n≥k≥4), the maximizer is in G²_{n,k} = {K_s ∨ ((n-k+s+1)K_1 ∪ K_{k-2s-1}) : 1≤s≤⌊k/2⌋-1}; and for connected n-vertex M_{k+1}-free graphs, the maximizer is K_n when n=2k+1 and otherwise in G³_{n,k} = {K_s ∨ ((n-2k+s-1)K_1 ∪ K_{2k-2s+1}) : 1≤s≤k}. These characterizations are used to derive applications to Turán-type problems, degree powers, and spectral radii.

Significance. If the characterizations hold, the paper supplies a unified method that reduces many extremal problems (edge extremal, generalized Turán, spectral) to verifying that the target parameter is feasible, then reading off the extremal graph from one of the three explicit families. This avoids separate case analyses for each parameter and directly yields results for the number of edges, sum of degree powers, adjacency spectral radius, and signless Laplacian spectral radius.

minor comments (3)

§1 (abstract): the statement of result (iii) for n=2k+1 claims G ≅ K_n, but the family G³_{n,k} is only defined for n≥2k+2; a brief remark on why the complete graph is the unique maximizer in the boundary case would improve clarity.
The notation W_{n,k,s} is introduced for the graphs in G¹_{n,k} but not reused in the statements of (ii) and (iii); consistent naming across the three families would aid readability.
The applications section is announced as 'directly derived' from the three theorems, but no explicit list or table of corollaries (e.g., which parameters satisfy feasibility) appears in the abstract; adding a short enumerated list would strengthen the claim of unification.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation for minor revision. No major comments appear in the report, so we have nothing to address point-by-point.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained from definition

full rationale

The paper defines a feasible parameter P via two explicit monotonicity properties (non-decreasing under Kelmans operations, strictly increasing under edge addition). It then proves that any maximizer of such a P in the relevant forbidden-subgraph classes must belong to the listed families. This is a direct structural characterization from the hypothesis, not a reduction of the claim to itself by construction, fitted parameters, or self-citation chains. The abstract and results contain no load-bearing self-citations or renamings of known results as new derivations. The method unifies applications but does not create circularity in the central claims.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper introduces the notion of a feasible parameter as its central working definition and relies on the standard axioms of graph theory together with the properties of the Kelmans operation.

axioms (1)

standard math Standard axioms of simple undirected graphs and the definition of the Kelmans operation G_uv.
Invoked throughout the argument that feasible parameters are maximized only on the claimed families.

pith-pipeline@v0.9.0 · 6125 in / 1289 out tokens · 23687 ms · 2026-05-24T04:55:24.528747+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

[1]

Akiyama, P

J. Akiyama, P. Frankl, On the size of graphs with complete factors, J. Graph Theory 9 (1985), no.1, 197–201

work page 1985
[2]

N. Alon, C. Shikhelman, Many T copies in H-free graphs, J. Combin. Theory Ser. B 121 (2016), 146-172

work page 2016
[3]

Balister, E

P.N. Balister, E. Gy˝ ori, J. Lehel, R.H. Schelp, Connect ed graphs without long paths, Discrete Math. 308 (2008), no. 19, 4487–4494

work page 2008
[4]

Bondy, V

J.A. Bondy, V. Chv´ atal, A method in graph theory, Discrete Math. 15 (1976), 111– 135. 23

work page 1976
[5]

Y. Caro, R. Yuster, A Tur´ an type problem concerning the p owers of the degrees of a graph, Electron. J. Combin. 7 (2000), Research Paper 47, 14 pp

work page 2000
[6]

Csikv´ ari, On a conjecture of V

P. Csikv´ ari, On a conjecture of V. Nikiforov. Discrete Math. 309 (2009), 4522–4526

work page 2009
[7]

Erd˝ os, T

P. Erd˝ os, T. Gallai, On maximal paths and circuits of gra phs, Acta Math. Acad. Sci. Hungar. 10 (1959), 337–356

work page 1959
[8]

Faudree, R.H

R.J. Faudree, R.H. Schelp, Path-path Ramsey-type numbe rs for the complete bipar- tite graph, J. Combinatorial Theory Ser. B 19 (1975), no. 2, 161–173

work page 1975
[9]

Fiedler, V

M. Fiedler, V. Nikiforov, Spectral radius and Hamiltoni city of graphs, Linear Algebra Appl. 432 (2010), no. 9, 2170–2173

work page 2010
[10]

Gao, X-M

J. Gao, X-M. Hou, The spectral radius of graphs without l ong cycles, Linear Algebra Appl. 566 (2019), 17–33

work page 2019
[11]

Gy˝ ori, N

E. Gy˝ ori, N. Salia, C. Tompkins, O. Zamora, The maximum number of Pl copies in Pk-free graphs, Discrete Math. Theor. Comput. Sci. 21 (2019), no. 1, Paper No. 14, 21 pp

work page 2019
[12]

Kelmans, On graphs with randomly deleted edges, Acta Math

A.K. Kelmans, On graphs with randomly deleted edges, Acta Math. Acad. Sci. Hun- gar. 37 (1981), 77–88

work page 1981
[13]

G. N. Kopylov: Maximal paths and cycles in a graph, Dokl. Akad. Nauk SSSR 234 (1977), 19–21. (English translation: Soviet Math. Dokl. 18 (1977), 593–596.)

work page 1977
[14]

B.L. Li, B. Ning, Spectral analogues of Erd˝ os’ and Moon -Moser’s theorems on Hamil- ton cycles, Linear Multilinear Algebra 64 (2016), no. 11, 2252–2269

work page 2016
[15]

B.L. Li, B. Ning, A strengthening of Erd˝ os-Gallai theo rem and proof of Woodall’s conjecture, J. Combin. Theory Ser. B 146 (2021), 76–95

work page 2021
[16]

B.L. Li, B. Ning, Stability of Woodall’s theorem and spe ctral conditions for large cycles, Electron. J. Combin. 30 (2023), P1.39

work page 2023
[17]

Li, W, Li, L

Y. Li, W, Li, L. F, A survey on spectral conditions for som e extremal graph problems, arXiv preprint arXiv:2111.03309 (2021)

work page arXiv 2021
[18]

Lewin, On maximal circuits in directed graphs, J

M. Lewin, On maximal circuits in directed graphs, J. Combin. Theory Ser. B 18 (1975), 175-179

work page 1975
[19]

C. Lu, L. Yuan, P. Zhang, The maximum number of copies of Kr,s in graphs without long cycles or paths, Electron. J. Combin. 74 (2021), P4.4

work page 2021
[20]

Luo, The maximum number of cliques in graphs without l ong cycles, J

R. Luo, The maximum number of cliques in graphs without l ong cycles, J. Combin. Theory Ser. B 128 (2018), 219–226

work page 2018
[21]

J. Ma, B. Ning, Stability results on the circumference o f a graph, Combinatorica 40 (2020), 105–147

work page 2020
[22]

Nikiforov, The spectral radius of graphs without pat hs and cycles of speciﬁed length, Linear Algebra Appl

V. Nikiforov, The spectral radius of graphs without pat hs and cycles of speciﬁed length, Linear Algebra Appl. 432 (2010), no. 9, 2243–2256. 24

work page 2010
[23]

Nikiforov, Some new results in extremal graph theory

V. Nikiforov, Some new results in extremal graph theory . Surveys in combinatorics 2011, 141–181, London Math. Soc. Lecture Note Ser., 392, Cam bridge Univ. Press, Cambridge, 2011

work page 2011
[24]

Nikiforov, X.Y

V. Nikiforov, X.Y. Yuan, Maxima of the Q-index: graphs without long paths, Elec- tron. J. Linear Algebra 27 (2014), 504–514

work page 2014
[25]

Sun, K.C

S.W. Sun, K.C. Das, A conjecture on the spectral radius o f graphs, Linear Algebra Appl. 588 (2020), 74–80

work page 2020
[26]

Woodall, Maximal circuits of graphs I, Acta Math

D.R. Woodall, Maximal circuits of graphs I, Acta Math. Acad. Sci. Hung. 28 (1976), 77-80

work page 1976
[27]

Yuan, Anti-Ramsey numbers for paths, arXiv:2102 .00807 (2021)

L.-T. Yuan, Anti-Ramsey numbers for paths, arXiv:2102 .00807 (2021)

work page 2021
[28]

Zhan, Matrix theory

X. Zhan, Matrix theory. Graduate Studies in Mathematic s, 147. American Mathe- matical Society, Providence, RI, 2013. x+253 pp. ISBN: 978- 0-8218-9491-0. 25

work page 2013

[1] [1]

Akiyama, P

J. Akiyama, P. Frankl, On the size of graphs with complete factors, J. Graph Theory 9 (1985), no.1, 197–201

work page 1985

[2] [2]

N. Alon, C. Shikhelman, Many T copies in H-free graphs, J. Combin. Theory Ser. B 121 (2016), 146-172

work page 2016

[3] [3]

Balister, E

P.N. Balister, E. Gy˝ ori, J. Lehel, R.H. Schelp, Connect ed graphs without long paths, Discrete Math. 308 (2008), no. 19, 4487–4494

work page 2008

[4] [4]

Bondy, V

J.A. Bondy, V. Chv´ atal, A method in graph theory, Discrete Math. 15 (1976), 111– 135. 23

work page 1976

[5] [5]

Y. Caro, R. Yuster, A Tur´ an type problem concerning the p owers of the degrees of a graph, Electron. J. Combin. 7 (2000), Research Paper 47, 14 pp

work page 2000

[6] [6]

Csikv´ ari, On a conjecture of V

P. Csikv´ ari, On a conjecture of V. Nikiforov. Discrete Math. 309 (2009), 4522–4526

work page 2009

[7] [7]

Erd˝ os, T

P. Erd˝ os, T. Gallai, On maximal paths and circuits of gra phs, Acta Math. Acad. Sci. Hungar. 10 (1959), 337–356

work page 1959

[8] [8]

Faudree, R.H

R.J. Faudree, R.H. Schelp, Path-path Ramsey-type numbe rs for the complete bipar- tite graph, J. Combinatorial Theory Ser. B 19 (1975), no. 2, 161–173

work page 1975

[9] [9]

Fiedler, V

M. Fiedler, V. Nikiforov, Spectral radius and Hamiltoni city of graphs, Linear Algebra Appl. 432 (2010), no. 9, 2170–2173

work page 2010

[10] [10]

Gao, X-M

J. Gao, X-M. Hou, The spectral radius of graphs without l ong cycles, Linear Algebra Appl. 566 (2019), 17–33

work page 2019

[11] [11]

Gy˝ ori, N

E. Gy˝ ori, N. Salia, C. Tompkins, O. Zamora, The maximum number of Pl copies in Pk-free graphs, Discrete Math. Theor. Comput. Sci. 21 (2019), no. 1, Paper No. 14, 21 pp

work page 2019

[12] [12]

Kelmans, On graphs with randomly deleted edges, Acta Math

A.K. Kelmans, On graphs with randomly deleted edges, Acta Math. Acad. Sci. Hun- gar. 37 (1981), 77–88

work page 1981

[13] [13]

G. N. Kopylov: Maximal paths and cycles in a graph, Dokl. Akad. Nauk SSSR 234 (1977), 19–21. (English translation: Soviet Math. Dokl. 18 (1977), 593–596.)

work page 1977

[14] [14]

B.L. Li, B. Ning, Spectral analogues of Erd˝ os’ and Moon -Moser’s theorems on Hamil- ton cycles, Linear Multilinear Algebra 64 (2016), no. 11, 2252–2269

work page 2016

[15] [15]

B.L. Li, B. Ning, A strengthening of Erd˝ os-Gallai theo rem and proof of Woodall’s conjecture, J. Combin. Theory Ser. B 146 (2021), 76–95

work page 2021

[16] [16]

B.L. Li, B. Ning, Stability of Woodall’s theorem and spe ctral conditions for large cycles, Electron. J. Combin. 30 (2023), P1.39

work page 2023

[17] [17]

Li, W, Li, L

Y. Li, W, Li, L. F, A survey on spectral conditions for som e extremal graph problems, arXiv preprint arXiv:2111.03309 (2021)

work page arXiv 2021

[18] [18]

Lewin, On maximal circuits in directed graphs, J

M. Lewin, On maximal circuits in directed graphs, J. Combin. Theory Ser. B 18 (1975), 175-179

work page 1975

[19] [19]

C. Lu, L. Yuan, P. Zhang, The maximum number of copies of Kr,s in graphs without long cycles or paths, Electron. J. Combin. 74 (2021), P4.4

work page 2021

[20] [20]

Luo, The maximum number of cliques in graphs without l ong cycles, J

R. Luo, The maximum number of cliques in graphs without l ong cycles, J. Combin. Theory Ser. B 128 (2018), 219–226

work page 2018

[21] [21]

J. Ma, B. Ning, Stability results on the circumference o f a graph, Combinatorica 40 (2020), 105–147

work page 2020

[22] [22]

Nikiforov, The spectral radius of graphs without pat hs and cycles of speciﬁed length, Linear Algebra Appl

V. Nikiforov, The spectral radius of graphs without pat hs and cycles of speciﬁed length, Linear Algebra Appl. 432 (2010), no. 9, 2243–2256. 24

work page 2010

[23] [23]

Nikiforov, Some new results in extremal graph theory

V. Nikiforov, Some new results in extremal graph theory . Surveys in combinatorics 2011, 141–181, London Math. Soc. Lecture Note Ser., 392, Cam bridge Univ. Press, Cambridge, 2011

work page 2011

[24] [24]

Nikiforov, X.Y

V. Nikiforov, X.Y. Yuan, Maxima of the Q-index: graphs without long paths, Elec- tron. J. Linear Algebra 27 (2014), 504–514

work page 2014

[25] [25]

Sun, K.C

S.W. Sun, K.C. Das, A conjecture on the spectral radius o f graphs, Linear Algebra Appl. 588 (2020), 74–80

work page 2020

[26] [26]

Woodall, Maximal circuits of graphs I, Acta Math

D.R. Woodall, Maximal circuits of graphs I, Acta Math. Acad. Sci. Hung. 28 (1976), 77-80

work page 1976

[27] [27]

Yuan, Anti-Ramsey numbers for paths, arXiv:2102 .00807 (2021)

L.-T. Yuan, Anti-Ramsey numbers for paths, arXiv:2102 .00807 (2021)

work page 2021

[28] [28]

Zhan, Matrix theory

X. Zhan, Matrix theory. Graduate Studies in Mathematic s, 147. American Mathe- matical Society, Providence, RI, 2013. x+253 pp. ISBN: 978- 0-8218-9491-0. 25

work page 2013