Journal of Combinatorics

Volume 7 (2016)

Number 2–3

Guest editors: Rong Luo and Cun-Quan Zhang

Cyclable sets of vertices in 3-connected graphs

Pages: 495 – 508

DOI: https://dx.doi.org/10.4310/JOC.2016.v7.n2.a14

Authors

Hao Li (Laboratoire de Recherche en Informatique, Université Paris-Saclay, Orsay, France; and Institute for Interdisciplinary Research, Jianghan University, Wuhan, China)

Yan Zhu (Laboratoire de Recherche en Informatique, Université Paris-Saclay, Orsay, France; and Department of Mathematics, East China University of Science and Technology, Shanghai, China)

Abstract

Given a graph $G$, a set $S \subseteq V (G)$ is called cyclable (in $G$) if $G$ has a cycle containing every vertex of $S$; $G$ is hamiltonian if $V (G)$ is cyclable in $G$. Beginning with a result of Dirac in 1952, many results on sufficient conditions that relate degree sum and neighborhood conditions for hamiltonicity and cyclability, have been obtained. We give a new sufficient condition on degree sums and neighborhoods of any four independent vertices in a graph. We also study the extremal cases of this condition.

Full Text (PDF format)

Published 23 February 2016