Further Results on the Maximum Number of Stars in Graphs with Forbidden Properties

Summary · qwen2.5:32b

The study investigates the maximum number of $t$-stars in graphs that are not $k$-edge-hamiltonian, building on earlier work by Füredi et al. and Berikkyzy et al., who explored similar properties including traceability and hamiltonian-connectedness. The research reveals that a previously proposed conjecture fails at a critical value of $t$, leading to a threshold-type result for extremal graphs near this value.

Suggested post angle

Mathematicians investigate a conjecture about the maximum number of stars in graphs with forbidden properties, extending previous research on graph theory.

Excerpt

arXiv:2607.00770v3 Announce Type: replace 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 in graphs failing to satisfy related properties 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. We show that the conjecture fails at the critical value and further establish a threshold-type result describing the behavior of the extremal graphs when $t$ is close to this critical value.