2-factors in claw-free graphs with locally disconnected vertices

An, Mingqiang ; Xiong, Liming ; Tian, Runli

Czechoslovak Mathematical Journal, Tome 65 (2015) no. 2, pp. 317-330.

Résumé

An edge of $G$ is singular if it does not lie on any triangle of $G$; otherwise, it is non-singular. A vertex $u$ of a graph $G$ is called locally connected if the induced subgraph $G[N(u)]$ by its neighborhood is connected; otherwise, it is called locally disconnected. In this paper, we prove that if a connected claw-free graph $G$ of order at least three satisfies the following two conditions: (i) for each locally disconnected vertex $v$ of degree at least $3$ in $G,$ there is a nonnegative integer $s$ such that $v$ lies on an induced cycle of length at least $4$ with at most $s$ non-singular edges and with at least $s-5$ locally connected vertices; (ii) for each locally disconnected vertex $v$ of degree $2$ in $G,$ there is a nonnegative integer $s$ such that $v$ lies on an induced cycle $C$ with at most $s$ non-singular edges and with at least $s-3$ locally connected vertices and such that $G[V (C)\cap V_{2} (G)]$ is a path or a cycle, then $G$ has a 2-factor, and it is the best possible in some sense. This result generalizes two known results in Faudree, Faudree and Ryjáček (2008) and in Ryjáček, Xiong and Yoshimoto (2010).

Détail

DOI : 10.1007/s10587-015-0177-2

Classification : 05C35, 05C38, 05C45
Keywords: claw-free graph; 2-factor; closure; locally disconnected vertex; singular edge