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

Title:

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

Creator:

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

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:19634d06-54ee-435e-9e04-276d526ed09f
uuid:19634d06-54ee-435e-9e04-276d526ed09f

Subject:

2-factor, claw-free graph, line graph, and $N^{2}$-locally connected

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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 {\rm dist}_{G}(x,y)\leq 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 $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.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

1035-1044

Source:

Czechoslovak Mathematical Journal | 2014 Volume:64 | Number:4

Harvested from:

CDK

Metadata only:

false