Further Results on the maximun number of stars in graphs with forbidden properties
이 뉴스, 어떠셨어요?
한 번의 탭으로 반응을 남겨요 · 로그인 불필요
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$.
Motivated by earlier results of Erdős, Föredi, Kostochka and Luo determined the maximum number of $t$-stars in nonhamiltonian graphs.
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.