On graphs whose cycle space is spanned by their Hamilton cycles

Abstract

The cycle space of a graph $G$, denoted $\mathcal{C}(G)$, is a vector space over ${\mathbb{F}}_2$, spanned by all incidence vectors of edge-sets of cycles of $G$. If $G$ has $n$ vertices, then ${\mathcal{C}}_n(G)$ denotes the subspace of $\mathcal{C}(G)$, spanned by the incidence vectors of Hamilton cycles of $G$. We consider several known sufficient conditions for Hamiltonicity and show that an appropriate and fairly mild strengthening of each such condition in fact ensures the stronger property ${\mathcal{C}}_n(G)=\mathcal{C}(G)$. In particular, we consider the classical Chvátal-Erdős criterion and prove that (under various additional restrictions) if $n$ is odd and $\hat{I}º(G)\ge c\hat{I}\pm (G)$, where $c$ is a sufficiently large absolute constant, then ${\mathcal{C}}_n(G)=\mathcal{C}(G)$. Moreover, considering the McDiarmid-Yolov criterion we prove that if $n$ is odd and $\hat{I}´(G)\ge \max \left\{2\tilde{\hat{I}}\pm (G)+9,\tilde{\hat{I}}\pm (G)+18\right\}$, where $\tilde{\hat{I}}\pm (G)$ is the so-called bipartite independence number of $G$, then ${\mathcal{C}}_n(G)=\mathcal{C}(G)$. We also prove that if $n$ is odd and $G$ admits $16\hat{I}\pm (G)+12$ pairwise disjoint connected dominating sets, ${\mathcal{C}}_n(G)=\mathcal{C}(G)$. Finally, we consider an effective Chvátal-Erdős type criterion for bipartite graphs and prove that if $G$ is a balanced bipartite graph on $2n$ vertices, satisfying $\hat{I}{\pm }_{\text{BIP}}(G)\le 2\hat{I}´(G)-24$, then ${\mathcal{C}}_{2n}(G)=\mathcal{C}(G)$.