pith. sign in

arxiv: 2607.00770 · v2 · pith:KTGFYRSUnew · submitted 2026-07-01 · 🧮 math.CO

Further Results on the maximun number of stars in graphs with forbidden properties

Yuxuan Liu , Jia-bao Yang , Leilei Zhang This is my paper

Pith reviewed 2026-07-03 20:31 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C3505C45
keywords extremal graph theoryk-edge hamiltoniant-starshamiltonian cycleslinear forestsmaximum number of stars
0
0 comments X

The pith

The maximum number of t-stars in graphs that are not k-edge hamiltonian matches a specific extremal construction for small t.

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

The paper examines the maximum number of t-stars possible in a graph that fails to be k-edge hamiltonian. Earlier work fixed this maximum for large t and left a conjecture for smaller t. The present work supplies further results that address the conjecture directly by determining the extremal value in additional cases.

Core claim

For smaller values of t the maximum number of t-stars in an n-vertex graph that is not k-edge hamiltonian is achieved by the same family of graphs that attain the bound when t is large, confirming the form proposed in the conjecture.

What carries the argument

The extremal function counting the largest number of t-stars in an n-vertex graph without a k-edge hamiltonian cycle, together with the conjectured extremal graphs.

Load-bearing premise

The conjecture from the earlier paper correctly identifies the extremal graphs without extra restrictions that depend on the relative sizes of t, k and n.

What would settle it

An explicit graph on n vertices that is not k-edge hamiltonian yet contains strictly more t-stars than the number given by the conjectured extremal construction, for some small t and sufficiently large n.

read the original abstract

A graph $G$ is called $k$-edge hamiltonian if every linear forest (i.e., a disjoint union of paths) with at most $k$ edges is contained in a Hamilton cycle of $G$. In 2018, F\"uredi, Kostochka and Luo determined the maximum number of $t$-stars in nonhamiltonian graphs, thereby extending an earlier result of Erd\H{o}s. Recently, Berikkyzy, Hogenson, Kirsch and McDonald extended this line of research by determining the maximum number of $t$-stars in graphs that are not $k$-edge hamiltonian (as well as related notions such as traceability, hamiltonian-connectedness, and $k$-hamiltonicity). For sufficiently large $t$, they also characterized the extremal graphs, while for smaller values of $t$, they proposed a conjecture. In this paper, we investigate this conjecture.

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.

Referee Report

1 major / 0 minor

Summary. The paper investigates the conjecture of Berikkyzy et al. on the maximum number of t-stars in graphs that are not k-edge hamiltonian, focusing on the cases of smaller t where the previous work left the extremal graphs uncharacterized.

Significance. If the investigation confirms the conjecture for small t, the work would complete the extremal characterization for the number of t-stars under the forbidden property of not being k-edge hamiltonian (and related notions), extending the results of Furedi-Kostochka-Luo on nonhamiltonian graphs and providing a full picture of the extremal function.

major comments (1)
  1. [§1] §1 (conjecture statement): the investigation of the conjecture for small t rests on the assumption that the extremal construction remains maximal for all n; the paper should explicitly state and verify any required lower bound on n relative to k and t, as the bound on the number of t-stars could otherwise be violated by other non-k-edge-hamiltonian graphs on smaller vertex sets.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and the constructive comment. We address the major comment below and will revise the paper accordingly.

read point-by-point responses

  1. Referee: [§1] §1 (conjecture statement): the investigation of the conjecture for small t rests on the assumption that the extremal construction remains maximal for all n; the paper should explicitly state and verify any required lower bound on n relative to k and t, as the bound on the number of t-stars could otherwise be violated by other non-k-edge-hamiltonian graphs on smaller vertex sets.

    Authors: We agree with the referee that an explicit lower bound on n should be stated for clarity. The manuscript investigates the conjecture of Berikkyzy et al. for small t under the assumption that n is sufficiently large (as stated in the original conjecture), but we will revise Section 1 to include a specific lower bound on n in terms of k and t. This bound will be derived from the extremal constructions and the proof methods used, with a brief verification that the bound ensures the stated extremal graphs are indeed maximal. We will also note that for n below this threshold the conjecture may require separate analysis. revision: yes

Circularity Check

0 steps flagged

No circularity: paper investigates external conjecture without self-referential reductions

full rationale

The manuscript cites the conjecture of Berikkyzy et al. (distinct authors) on the maximum number of t-stars in non-k-edge-hamiltonian graphs and states that it investigates this conjecture for smaller t. No equations, derivations, fitted parameters, or self-citations appear in the abstract or described content. The central activity is external to the present paper's own inputs, so no step reduces by construction to a prior result or fit within this work. This is the expected non-finding for a conjecture-investigation paper whose load-bearing premise is imported from independent prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No technical content available; cannot enumerate free parameters, axioms, or invented entities.

pith-pipeline@v0.9.1-grok · 5697 in / 974 out tokens · 16155 ms · 2026-07-03T20:31:10.331351+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 1 canonical work pages

  1. [1]

    J. Ai, H. Lei, B. Ning and Y. Shi, Graph operations and a unified method for Turán-type problems on paths, cycles, and matchings, Canad. J. Math. (2025) 1-27

    2025

  2. [2]

    Berikkyzy, K

    Z. Berikkyzy, K. Hogenson, R. Kirsch and J. McDonald, Maximizing the number of stars in graphs with forbidden properties, Discrete Math. 349 (2026) 114846

    2026

  3. [3]

    Cambie, R

    S. Cambie, R. de Joannis de Verclos and R. J. Kang, Regular Turán numbers and some Gan- Loh-Sudakov-type problems, J. Graph Theory 102 (1) (2023) 67-85

    2023

  4. [4]

    Bondy and V

    J.A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (2) (1976) 111-135

    1976

  5. [5]

    Bondy and U.S.R

    J.A. Bondy and U.S.R. Murty, Graph theory, Graduate Texts in Mathematics, 244, Springer, New York, 2008

    2008

  6. [6]

    Erdős, Remarks on a paper of Pósa, Magy

    P. Erdős, Remarks on a paper of Pósa, Magy. Tud. Akad. Mat. Kut. Intóz. Közl. 7 (1962) 227-229

    1962

  7. [7]

    Füredi, A

    Z. Füredi, A. Kostochka and R. Luo, Extensions of a theorem of Erdős on nonhamiltonian graphs, J. Graph Theory 89 (2) (2018) 176-193

    2018

  8. [8]

    Füredi, A

    Z. Füredi, A. Kostochka and R. Luo, A variation of a theorem by Pósa, Discrete Math. 342 (7) (2019) 1919-1923

    2019

  9. [9]

    Gerbner, On Turán problems with bounded matching number, J

    D. Gerbner, On Turán problems with bounded matching number, J. Graph Theory 106 (2024) 23-29

    2024

  10. [10]

    Gerbner, Degree powers and number of stars in graphs with a forbidden broom, Discrete Math

    D. Gerbner, Degree powers and number of stars in graphs with a forbidden broom, Discrete Math. 348 (1) (2025) 114232

    2025

  11. [11]

    Gerbner, Generalized Turán problems for small graphs, Discuss

    D. Gerbner, Generalized Turán problems for small graphs, Discuss. Math. Graph Theory 43 (2023) 549-572

    2023

  12. [12]

    Gerbner and C

    D. Gerbner and C. Palmer, Survey of generalized Turán problems-counting subgraphs, arXiv:2506.03418, 2025

    work page arXiv 2025

  13. [13]

    Győri, N

    E. Győri, N. Salia, C. Tompkins and O. Zamora, The maximum number ofPl copies inP k -free graphs, Discrete Math. Theor. Comput. Sci. 21 (1) (2019) 14

    2019

  14. [14]

    Huang, J

    S. Huang, J. Qian. The maximum number of stars in a graph without linear forest, Graphs Combin. 38 (6) (2022) 1-12. 8

    2022

  15. [15]

    W. Liu, R. Ren, The number of stars in a graph that forbids a matching and any graph, Discrete Appl. Math. 388 (2026) 136-141

    2026

  16. [16]

    Y. Ma, X. Hou, Z. Yin, Generalized Turán problem with bounded matching number, Electron. J. Combin. 33 (2026) 1. 46. 9

    2026