Maximizing the number of stars in graphs with forbidden properties

Abstract

Erdős proved an upper bound on the number of edges in an $n$-vertex non-Hamiltonian graph with given minimum degree and showed sharpness via two members of a particular graph family. Füredi, Kostochka and Luo showed that these two graphs play the same role when ``number of edges'' is replaced by ``number of t-stars,'' and that two members of a more general graph family maximize the number of edges among non-$k$-edge-Hamiltonian graphs. In this paper we generalize their former result from Hamiltonicity to related properties (traceability, Hamiltonian-connectedness, $k$-edge Hamiltonicity, $k$-Hamiltonicity) and their latter result from edges to $t$-stars. We identify a family of extremal graphs for each property that is forbidden. This problem without the minimum degree condition was also open; here we conjecture a complete description of the extremal family for each property, and prove the characterization in some cases. Finally, using a different family of extremal graphs, we find the maximum number of $t$-stars in non-$k$-connected graphs.

19 pages