Two operations on a graph preserving the (non)existence of 2-factors in its line graph

Mingqiang An*, Hong Jian Lai, Hao Li, Guifu Su, Runli Tian, Liming Xiong

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Let G = (V (G),E(G)) be a graph. Gould and Hynds (1999) showed a well-known characterization of G by its line graph L(G) that has a 2-factor. In this paper, by defining two operations, we present a characterization for a graph G to have a 2-factor in its line graph L(G). A graph G is called N2-locally connected if for every vertex x ∈ V (G), G[{y ∈ V (G); 1 ⩽ distG(x, y) ⩽ 2}] is connected. By applying the new characterization, we prove that every claw-free graph in which every edge lies on a cycle of length at most five and in which every vertex of degree two that lies on a triangle has two N2-locally connected adjacent neighbors, has a 2-factor. This result generalizes the previous results in papers: Li, Liu (1995) and Tian, Xiong, Niu (2012), and is the best possible.

Original languageEnglish
Pages (from-to)1035-1044
Number of pages10
JournalCzechoslovak Mathematical Journal
Volume64
Issue number4
DOIs
Publication statusPublished - Dec 2014

Keywords

  • 2-factor
  • N-locally connected
  • claw-free graph
  • line graph

Fingerprint

Dive into the research topics of 'Two operations on a graph preserving the (non)existence of 2-factors in its line graph'. Together they form a unique fingerprint.

Cite this