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

Czechoslovak Mathematical Journal

An¹  Hong-Jian ²  Li³  Mingqiang ⁴  Lai⁵  Hao ⁶ 

[1] Department of Mathematics, West Virginia University, P.O.Box 620, Morgantown, West Virginia, 265 06, USA;School of Information, Renmin University of China, No. 59 Zhongguancun Street, Haidian District Beijing, 100 872, P. R. China;School of Mathematics and Statistics, Beijing Institute of Technology, 5th North Zhongguancun Street, Haidian District Beijing, 100 081, P. R. China;School of Mathematics and Statistics, Beijing Institute of Technology, 5th North Zhongguancun Street, Haidian District Beijing, 100 081, P. R. China, and College of Science, Tianjin University of Science and Technology, No. 29, 13th Avenue, Tianjin Economic and Technological Development Area, Tianjin, 300 457, P. R. China;School of Mathematics, Beijing Institute of Technology, 5th North Zhongguancun Street, Haidian District Beijing, 100 081, P. R. China, and School of Science, Beijing University of Technology, Beijing, 10029, P. R. China;School of Science, Central South University of Forestry and Technology, No. 498, Shaoshan South Road, Changsha, Hunan, 410 004, P. R. China

关键词: 2-factor;    claw-free graph;    line graph;    $N^2$-locally connected;   

DOI  :  

学科分类：数学（综合）

来源: Akademie Ved Ceske Republiky

【 摘 要 】

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 $N^2$-locally connected if for every vertex $x\in V(G),$ $G[\{y\in V(G)1\leq dist_G(x,y)\leq2\}]$ 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 $N^2$-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.

【 授权许可】

Unknown