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

Mingqiang An*, Liming Xiong, Runli Tian

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

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)∩V2(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).

Original languageEnglish
Pages (from-to)317-330
Number of pages14
JournalCzechoslovak Mathematical Journal
Volume65
Issue number2
DOIs
Publication statusPublished - 26 Jun 2015

Keywords

  • 2-factor
  • claw-free graph
  • closure
  • locally disconnected vertex
  • singular edge

Fingerprint

Dive into the research topics of '2-Factors in claw-free graphs with locally disconnected vertices'. Together they form a unique fingerprint.

Cite this