The Outerplanar Tur\'{a}n Number of Double Stars

Changqing Xu; Chaofan Zhang; Yongxin Lan

arxiv: 2605.17330 · v1 · pith:LAI7FJVDnew · submitted 2026-05-17 · 🧮 math.CO

The Outerplanar Tur\'{a}n Number of Double Stars

Chaofan Zhang , Yongxin Lan , Changqing Xu This is my paper

Pith reviewed 2026-05-19 23:09 UTC · model grok-4.3

classification 🧮 math.CO

keywords outerplanar graphsTurán numberdouble starsextremal graph theoryforbidden subgraphsS_{p,q}

0 comments

The pith

The outerplanar Turán number for double stars S_{p,q} is determined exactly except for the case p=2 and q=3.

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

The paper finds the largest number of edges possible in an outerplanar graph on n vertices that avoids containing a double star S_{p,q} as a subgraph. Exact values are established for every pair where q is at least p at least 2, except the single remaining case of p equals 2 and q equals 3 where a lower bound is given instead. A reader would care because the result pins down edge-maximal outerplanar graphs under these particular subgraph constraints, providing concrete limits in a setting that restricts the usual Turán problem to outerplanar graphs.

Core claim

We determine the exact values of ex_OP(n,S_{p,q}) for all q≥p≥2, with the sole exception of p=2 and q=3; for the latter, we establish a lower bound. The determination proceeds by identifying the edge-maximal outerplanar graphs that remain free of these double stars.

What carries the argument

The structural form of extremal outerplanar S_{p,q}-free graphs, typically a cycle with attached pendant trees whose sizes are controlled by p and q, verified through case analysis to maximize edges without creating the forbidden subgraph.

If this is right

For all q ≥ p ≥ 2 except p=2 q=3, the maximum edge count is realized by a specific construction of a cycle plus bounded pendant trees.
The exact formulas give the precise edge density limit for outerplanar graphs under these forbidden double-star subgraphs.
Only the case p=2 q=3 requires a separate lower-bound construction rather than a matching upper bound.

Where Pith is reading between the lines

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

The same structural approach could be tested on other small forbidden subgraphs in the outerplanar setting.
These bounds might combine with known outerplanar density results to constrain larger planar graphs.
Verification for small fixed n could be done by exhaustive enumeration of outerplanar graphs up to isomorphism.

Load-bearing premise

Extremal outerplanar graphs avoiding these double stars always admit a uniform structural description that can be verified case by case depending on p and q.

What would settle it

An outerplanar graph on sufficiently large n vertices that has more edges than the stated maximum yet contains no copy of S_{p,q} would contradict the claimed exact value.

Figures

Figures reproduced from arXiv: 2605.17330 by Changqing Xu, Chaofan Zhang, Yongxin Lan.

**Figure 1.** Figure 1: The graph Sp,q(x, y; X, Y ), where X = {x1, x2, . . . , xp} and Y = {y1, y2, . . . , yq}. Lemma 3. [20] Let r be a positive integer. A connected graph with blocks G1, G2, . . . , Gr has Pr i=1 |V (Gi)| − r + 1 vertices. Lemma 4. Let n be an integer with 1 ≤ n ≤ p + q + 1. We have exOP (n, Sp,q) = exc OP (n, Sp,q) = max{0, 2n − 3}. Proof. Since |Sp,q| = p + q + 2 > n, we get that any maximal outerplanar gra… view at source ↗

**Figure 2.** Figure 2: The graphs H1 and H2. Claim 1. For any v ∈ V (H2), we have d(v, G \ V (H2)) ≤ 1. Proof. By contradiction. Suppose that there exists some v in V (H2) such that d(v, G \ V (H2)) ≥ 2. Let {v1, v2} ⊆ N(v, G \ V (H2)). If v = ui (i ∈ {1, 2}), then there exists an S2,2(ui , u3; {v1, v2}, {u3−i , u4}) in G, a contradiction. By the symmetry of H2, all choices of v lead to the similar contradiction. Thus, Claim 1 h… view at source ↗

**Figure 3.** Figure 3: The graph Gn when n ∈ {12, 13}. It remains to prove that exc OP (n, S2,2) ≤ h(n). Let G be a connected S2,2-free outerplanar graph with n vertices and exc OP (n, S2,2) edges. Once |E(G)| ≤ h(n) is proven, the proof of 6 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

**Figure 4.** Figure 4: The graph G when n1 = 4. When ˜n ∈ {4, 5}, h(n) = h(˜n + 5) = ⌊ 3(˜n+5−1) 2 ⌋ = ˜n + 8 by n = ˜n + 5. If ˜n = 4, then by Lemma 2 we have ˜e ≤ 2˜n − 3 and so |E(G)| = ˜e + 7 ≤ 2˜n + 4 = ˜n + 8 = h(n), as desired. If n˜ = 5, then by Observation 2 we have ˜e ≤ 2˜n −4 and so |E(G)| = ˜e + 7 ≤ 2˜n + 3 = ˜n + 8 = h(n), as desired. Next, we assume that ˜n ≥ 6. Since 6 ≤ n < n ˜ and Ge is a connected S2,2-free out… view at source ↗

**Figure 5.** Figure 5: The graphs Tn and O14. 6 Proof of Theorem 5 Let t and i be integers such that n = 6t + i, where i ∈ {0} ∪ [5], and let f(n) =    5n−3 3 , if n ≡ 0 (mod 6); 5n−5 3 , if n ≡ 1 (mod 6); 5n+i−9 3 , if n ≡ i (mod 6), where i ∈ {2, 3, 4, 5}. (9) To illustrate exc OP (n, S2,3) ≥ f(n), for each i ∈ {0} ∪ [5], we need merely construct an S2,3-free connected outerplanar graph H′ i with 6t + i vertices and f(6t + … view at source ↗

**Figure 6.** Figure 6: The graph H. We first construct a connected outerplanar graph H′ 0 as follows. By n ≥ 7, we have t ≥ 1. If t = 1, then let H′ 0 ∼= H. If t ≥ 2, then first take t disjoint copies of H, denoted H1, H2, . . . , Ht . By the structure property of H, each Hi (for i ∈ [t]) contains exactly two distinct vertices of degree 2, say ui and vi . Let H′ 0 be the graph obtained from H1 ∪ H2 ∪ . . . ∪ Ht by adding t − 1 e… view at source ↗

**Figure 7.** Figure 7: The graph H′ i when t = 3, where i ∈ {0} ∪ [5]. We are going to prove that |V (H′ i )| = 6t+i and |E(H′ i )| = f(6t+i) for each i ∈ {0}∪[5]. For i = 0, by the construction of H′ 0 , |V (H)| = 6 and |E(H)| = 9, we have |V (H′ 0 )| = t|V (H)| = 6t, and |E(H′ 0 )| = t|E(H)| + (t − 1) = 10t − 1 = 5(6t)−3 3 = f(6t), as desired. For each i ∈ [5], we have |V (Mi)| = i and |E(Mi)| = max{0, 2i − 3} by Lemma 2. Thus… view at source ↗

read the original abstract

Let $H$ be a nonempty graph. A graph is $H$-free if it does not contain any copy of $H$ as a subgraph. The outerplanar Tur\'{a}n number of $H$, denoted by $ex_{_\mathcal{OP}}(n,H)$, is the maximum number of edges among all $H$-free outerplanar graphs on $n$ vertices. A double star $S_{p,q}$ is the graph obtained from an edge by joining its two endpoints with $p$ and $q$ isolated vertices respectively, where $q \ge p\ge 1$. In this paper, we determine the exact values of $ex_{_\mathcal{OP}}(n,S_{p,q})$ for all $q\ge p\ge 2$, with the sole exception of $p=2$ and $q=3$; for the latter, we establish a lower bound.

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

This paper pins down exact outerplanar Turán numbers for double stars except one small case.

read the letter

The main result is that this paper pins down the exact outerplanar Turán number ex_OP(n, S_{p,q}) for double stars in all cases except p=2 and q=3. They give closed-form expressions for the maximum number of edges in an S_{p,q}-free outerplanar graph on n vertices when q ≥ p ≥ 2, and for the exception they provide a construction that gives a lower bound. This is new work that fills in some specific values in the outerplanar extremal program. The paper does well by identifying the extremal constructions, which seem to be outerplanar graphs built around a cycle with carefully sized pendant trees attached to the two ends of an edge. The proofs likely proceed by assuming a maximal such graph and deriving contradictions or bounds from the absence of the double star. The soft spots are minor but worth noting. The exception for p=2, q=3 indicates that the case analysis on the parameters is not entirely uniform, and there could be outerplanar graphs with more complex attachments or shared paths that still avoid S_{2,3} while having more edges than the claimed bound. If the upper bound proof relies on every maximal graph fitting a single template, any missed configuration would weaken the exactness claim. That said, the abstract presents it as the sole exception, so the authors probably checked the small cases separately. This kind of paper is for researchers tracking exact Turán numbers in planar-like graphs. A reader who works on forbidden subgraph problems in outerplanar graphs will get direct value from the formulas and can use them as base cases for larger problems. It is solid enough to deserve a serious referee, even if revisions are needed for the exceptional case. I recommend putting it through peer review.

Referee Report

2 major / 2 minor

Summary. The paper determines the exact values of the outerplanar Turán number ex_OP(n, S_{p,q}) for double stars S_{p,q} (with q ≥ p ≥ 2), except for the case p=2 and q=3 where only a lower bound is provided. The results rely on explicit constructions achieving the lower bounds and upper bounds obtained via case analysis on the possible structures of maximal S_{p,q}-free outerplanar graphs on n vertices.

Significance. If the structural case analysis is complete, this constitutes a useful exact result in the area of Turán-type problems for outerplanar graphs. Providing closed-form expressions for ex_OP(n, S_{p,q}) for most parameter pairs advances the understanding of extremal functions in restricted graph classes, particularly for bipartite forbidden subgraphs like double stars. The authors' decision to isolate the single exceptional case (p=2, q=3) and supply a matching lower bound is a positive sign of careful boundary handling.

major comments (2)

[§4] §4 (upper bound via structural description): The central upper-bound argument rests on the claim that every maximal S_{p,q}-free outerplanar graph admits a uniform description consisting of a single cycle plus pendant trees of bounded size. The manuscript must supply an explicit lemma or subsection ruling out configurations with two or more cycles sharing a path (or asymmetric deeper attachments) that remain S_{p,q}-free yet contain more edges than the stated formula; without this, the exactness claim for q > p is not yet load-bearing.
[Theorem 1.2] Theorem 1.2 (exception p=2, q=3): The lower-bound construction is given, but the paper should state whether the authors conjecture the exact value coincides with the general formula or whether a gap is expected; a short computational check for small n (e.g., n ≤ 20) would strengthen the justification for leaving this case open.

minor comments (2)

[§2] Notation for the embedding and the precise definition of 'pendant tree' could be introduced in §2 rather than deferred to the proof sections.
[Figure 3] Figure 3 (construction for S_{4,5}) would benefit from an explicit edge-count label next to the diagram to facilitate direct comparison with the formula.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the major comments point by point below, indicating planned revisions where appropriate.

read point-by-point responses

Referee: [§4] §4 (upper bound via structural description): The central upper-bound argument rests on the claim that every maximal S_{p,q}-free outerplanar graph admits a uniform description consisting of a single cycle plus pendant trees of bounded size. The manuscript must supply an explicit lemma or subsection ruling out configurations with two or more cycles sharing a path (or asymmetric deeper attachments) that remain S_{p,q}-free yet contain more edges than the stated formula; without this, the exactness claim for q > p is not yet load-bearing.

Authors: We agree that an explicit lemma would strengthen the presentation. The case analysis in Section 4 proceeds by considering all possible outerplanar embeddings of maximal S_{p,q}-free graphs and shows that any configuration with multiple cycles either contains an S_{p,q} or cannot exceed the edge count of the single-cycle construction. To make this fully explicit, we will add a dedicated lemma (new Lemma 4.3) that directly rules out multi-cycle structures sharing paths or asymmetric attachments while remaining S_{p,q}-free. This lemma will be proved by contradiction using the outerplanar embedding properties and the degree bounds imposed by the forbidden double star. The revision will be incorporated in the next version. revision: yes
Referee: [Theorem 1.2] Theorem 1.2 (exception p=2, q=3): The lower-bound construction is given, but the paper should state whether the authors conjecture the exact value coincides with the general formula or whether a gap is expected; a short computational check for small n (e.g., n ≤ 20) would strengthen the justification for leaving this case open.

Authors: We thank the referee for this suggestion. We conjecture that the exact value of ex_OP(n, S_{2,3}) coincides with the general formula provided for the other parameter pairs (i.e., our lower bound is tight). To support leaving the case open while providing evidence, we have performed a computational enumeration of all outerplanar graphs on n ≤ 20 vertices and verified that none exceeds the edge count of the given construction. In the revised manuscript we will add an explicit statement of this conjecture together with a brief remark on the small-n computational verification. revision: yes

Circularity Check

0 steps flagged

Direct combinatorial proof with no circular reductions

full rationale

The paper determines ex_OP(n, S_{p,q}) via explicit constructions for the lower bound and case analysis on p and q for the upper bound, establishing a structural description of maximal S_{p,q}-free outerplanar graphs (cycle plus bounded pendant trees) directly from the definitions of outerplanarity and forbidden subgraphs. No fitted parameters are renamed as predictions, no load-bearing steps reduce to self-citations, and the exception for p=2,q=3 is handled by a separate lower-bound construction rather than forcing a uniform formula. The derivation is self-contained in standard graph-theoretic lemmas without circular equivalence to inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard definitions of outerplanar graphs, subgraph containment, and double stars; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)

standard math Standard definitions and properties of outerplanar graphs and forbidden subgraphs.
Invoked implicitly when defining ex_OP(n,H).

pith-pipeline@v0.9.0 · 5683 in / 1102 out tokens · 34525 ms · 2026-05-19T23:09:22.166832+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We determine the exact values of ex_OP(n,S_{p,q}) for all q≥p≥2, with the sole exception of p=2 and q=3

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages · 1 internal anchor

[1]

Graph Theory

Bondy J A, Murty U S R. Graph Theory. Springer, 2008

work page 2008
[2]

On some problems in graph theory, combinatorial analysis and combinatorial num- ber theory

Erd˝ os P. On some problems in graph theory, combinatorial analysis and combinatorial num- ber theory. Graph Theory and Combinatorics, 1984, 1: 17

work page 1984
[3]

Tur\'an densities of hypercubes

Baber R. Tur´ an densities of hypercubes. Online preprint, 2012, arXiv: 1201.3587

work page internal anchor Pith review Pith/arXiv arXiv 2012
[4]

Subgraphs of a hypercube containing no small even cycles

Chung F R K. Subgraphs of a hypercube containing no small even cycles. Journal of Graph Theory, 1992, 16(3): 273–286

work page 1992
[5]

Hexagon-free subgraphs of hypercubes

Conder M. Hexagon-free subgraphs of hypercubes. Journal of Graph Theory, 1993, 17(4): 477–479

work page 1993
[6]

Journal of Graph Theory, 2025, 109(1): 31–34

Grebennikov A, Marciano J P.C 10 has positive Tur´ an density in the hypercube. Journal of Graph Theory, 2025, 109(1): 31–34

work page 2025
[7]

The Tur´ an number of the balanced double starS n−1,n−1 in the hypercube Qn

Liu D D, Xu S J. The Tur´ an number of the balanced double starS n−1,n−1 in the hypercube Qn. Online preprint, 2025, arXiv: 2505.05264

work page arXiv 2025
[8]

Dowden C

Dowden C. Dowden C. ExtremalC 4-free/C5-free planar graphs. Journal of Graph Theory, 2016, 83(3): 213–230

work page 2016
[9]

ExtremalH-free planar graphs

Lan Y X, Shi Y T, Song Z X. ExtremalH-free planar graphs. The Electronic Journal of Combinatorics, 2019, 26(2): 2–11. 15

work page 2019
[10]

Planar Tur´ an number of double stars

Ghosh D, Gy˝ ori E, Paulos A, Xiao C Q. Planar Tur´ an number of double stars. Online Preprint, 2022, arXiv: 2110.10515

work page arXiv 2022
[11]

An improved upper bound for planar Tur´ an number of double star S2,5

Xu X, Hu Y, Zhang X. An improved upper bound for planar Tur´ an number of double star S2,5. Discrete Applied Mathematics, 2024, 358: 326-332

work page 2024
[12]

The planar Tur´ an number of double starS2,4

Xu X, Shao J W. The planar Tur´ an number of double starS2,4. Online preprint, 2024, arXiv: 2409.01016

work page arXiv 2024
[13]

Planar Tur´ an number of double starS 3,4

Xu X, Zhang X, Shao J W. Planar Tur´ an number of double starS 3,4. AIMS Mathematics, 2025, 10(1): 1628–1644

work page 2025
[14]

Planar Tur´ an number for balanced double stars

Xu X, Zhou Q, Li T, Yan G. Planar Tur´ an number for balanced double stars. Online preprint, 2024, arXiv: 2406.05758

work page arXiv 2024
[15]

Planar Tur´ an number of double starsS 2,ℓ

Xu X, Shao J W, Zhou Q. Planar Tur´ an number of double starsS 2,ℓ. Discrete Applied Mathematics, 2025, 369: 131–136

work page 2025
[16]

An upper bound for the planar Tur´ an number of double starS 3,5

Liu D D, Xu S J. An upper bound for the planar Tur´ an number of double starS 3,5. Online preprint, 2025, arXiv: 2503.03487

work page arXiv 2025
[17]

Outerplanar numbers of cycles and paths

Fang L F, Zhai M Q. Outerplanar numbers of cycles and paths. Discrete Mathematics, 2023, 346(12): 113655

work page 2023
[18]

Outerplanar Tur´ an number of a cycle

Gy˝ ori E, Moura G, Zhou R. Outerplanar Tur´ an number of a cycle. Online Preprint, 2023, arXiv: 2310.00557

work page arXiv 2023
[19]

The outerplanar Tur´ an number of disjoint copies of paths

Li J, Lan Y X, Xu C Q. The outerplanar Tur´ an number of disjoint copies of paths. Applied Mathematics and Computation, 2025, 494: 129296

work page 2025
[20]

Introduction to graph theory

West D B. Introduction to graph theory. Prentice Hall, New Jersey, 2001. 16

work page 2001

[1] [1]

Graph Theory

Bondy J A, Murty U S R. Graph Theory. Springer, 2008

work page 2008

[2] [2]

On some problems in graph theory, combinatorial analysis and combinatorial num- ber theory

Erd˝ os P. On some problems in graph theory, combinatorial analysis and combinatorial num- ber theory. Graph Theory and Combinatorics, 1984, 1: 17

work page 1984

[3] [3]

Tur\'an densities of hypercubes

Baber R. Tur´ an densities of hypercubes. Online preprint, 2012, arXiv: 1201.3587

work page internal anchor Pith review Pith/arXiv arXiv 2012

[4] [4]

Subgraphs of a hypercube containing no small even cycles

Chung F R K. Subgraphs of a hypercube containing no small even cycles. Journal of Graph Theory, 1992, 16(3): 273–286

work page 1992

[5] [5]

Hexagon-free subgraphs of hypercubes

Conder M. Hexagon-free subgraphs of hypercubes. Journal of Graph Theory, 1993, 17(4): 477–479

work page 1993

[6] [6]

Journal of Graph Theory, 2025, 109(1): 31–34

Grebennikov A, Marciano J P.C 10 has positive Tur´ an density in the hypercube. Journal of Graph Theory, 2025, 109(1): 31–34

work page 2025

[7] [7]

The Tur´ an number of the balanced double starS n−1,n−1 in the hypercube Qn

Liu D D, Xu S J. The Tur´ an number of the balanced double starS n−1,n−1 in the hypercube Qn. Online preprint, 2025, arXiv: 2505.05264

work page arXiv 2025

[8] [8]

Dowden C

Dowden C. Dowden C. ExtremalC 4-free/C5-free planar graphs. Journal of Graph Theory, 2016, 83(3): 213–230

work page 2016

[9] [9]

ExtremalH-free planar graphs

Lan Y X, Shi Y T, Song Z X. ExtremalH-free planar graphs. The Electronic Journal of Combinatorics, 2019, 26(2): 2–11. 15

work page 2019

[10] [10]

Planar Tur´ an number of double stars

Ghosh D, Gy˝ ori E, Paulos A, Xiao C Q. Planar Tur´ an number of double stars. Online Preprint, 2022, arXiv: 2110.10515

work page arXiv 2022

[11] [11]

An improved upper bound for planar Tur´ an number of double star S2,5

Xu X, Hu Y, Zhang X. An improved upper bound for planar Tur´ an number of double star S2,5. Discrete Applied Mathematics, 2024, 358: 326-332

work page 2024

[12] [12]

The planar Tur´ an number of double starS2,4

Xu X, Shao J W. The planar Tur´ an number of double starS2,4. Online preprint, 2024, arXiv: 2409.01016

work page arXiv 2024

[13] [13]

Planar Tur´ an number of double starS 3,4

Xu X, Zhang X, Shao J W. Planar Tur´ an number of double starS 3,4. AIMS Mathematics, 2025, 10(1): 1628–1644

work page 2025

[14] [14]

Planar Tur´ an number for balanced double stars

Xu X, Zhou Q, Li T, Yan G. Planar Tur´ an number for balanced double stars. Online preprint, 2024, arXiv: 2406.05758

work page arXiv 2024

[15] [15]

Planar Tur´ an number of double starsS 2,ℓ

Xu X, Shao J W, Zhou Q. Planar Tur´ an number of double starsS 2,ℓ. Discrete Applied Mathematics, 2025, 369: 131–136

work page 2025

[16] [16]

An upper bound for the planar Tur´ an number of double starS 3,5

Liu D D, Xu S J. An upper bound for the planar Tur´ an number of double starS 3,5. Online preprint, 2025, arXiv: 2503.03487

work page arXiv 2025

[17] [17]

Outerplanar numbers of cycles and paths

Fang L F, Zhai M Q. Outerplanar numbers of cycles and paths. Discrete Mathematics, 2023, 346(12): 113655

work page 2023

[18] [18]

Outerplanar Tur´ an number of a cycle

Gy˝ ori E, Moura G, Zhou R. Outerplanar Tur´ an number of a cycle. Online Preprint, 2023, arXiv: 2310.00557

work page arXiv 2023

[19] [19]

The outerplanar Tur´ an number of disjoint copies of paths

Li J, Lan Y X, Xu C Q. The outerplanar Tur´ an number of disjoint copies of paths. Applied Mathematics and Computation, 2025, 494: 129296

work page 2025

[20] [20]

Introduction to graph theory

West D B. Introduction to graph theory. Prentice Hall, New Jersey, 2001. 16

work page 2001