Many Hamiltonian subsets in large graphs with given density

MaRDI QIDQ6423721zbMATH OpenFDO

Authors Stijn Cambie, Jun Gao, Hong Liu

Publication date 18 January 2023

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Expander graphs (05C48)

Abstract: A set of vertices in a graph is a Hamiltonian subset if it induces a subgraph containing a Hamiltonian cycle. Kim, Liu, Sharifzadeh and Staden proved that among all graphs with minimum degree $d$, $K_{d+1}$ minimises the number of Hamiltonian subsets. We prove a near optimal lower bound that takes also the order and the structure of a graph into account. For many natural graph classes, it provides a much better bound than the extremal one ($approx{2}^{d+1}$). Among others, our bound implies that an $n$-vertex $C_4$-free graphs with minimum degree $d$ contains at least $n{2}^{d^{2-o(1)}}$ Hamiltonian subsets.

This page was built for publication: Many Hamiltonian subsets in large graphs with given density

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6423721)