Supereulerian Graphs and Chvátal-Erdős Type Conditions

Abstract

In 1972, Chvatal and Erdős showed that the graph $G$ with independence number $\alpha (G)$ no more than its connectivity $\kappa (G)$ (i.e., $\kappa (G)\ge \alpha (G)$) is hamiltonian. In this paper, we consider a kind of Chvatal and Erdős type condition on edge-connectivity $\lambda (G)$ and matching number (edge independence number). We show that if $\lambda (G)\ge {\alpha }^{\prime }(G)–1$, then $G$ is either supereulerian or in a well-defined family of graphs. Moreover, we weaken the condition $\kappa (G)\ge \alpha (G)–1$ in [11] to $\lambda (G)\ge \alpha (G)–1$ and obtain a similar characterization on non-supereulerian graphs. We also characterize the graph which contains a dominating closed trail under the assumption $\lambda (G)\ge {\alpha }^{\prime }(G)–2$.