Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9512675 | Discrete Mathematics | 2005 | 7 Pages |
Abstract
A graph G is induced matching extendable (shortly, IM-extendable), if every induced matching of G is included in a perfect matching of G. A graph G is claw-free, if G does not contain any induced subgraph isomorphic to K1,3. The kth power of a graph G, denoted by Gk, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. In this paper, the 4-regular claw-free IM-extendable graphs are characterized. It is shown that the only 4-regular claw-free connected IM-extendable graphs are C62, C82 and Tr, r⩾2, where Tr is the graph with 4r vertices ui,vi,xi,yi, 1⩽i⩽r, such that for each i with 1⩽i⩽r, {ui,vi,xi,yi} is a clique of Tr and xiui+1,yivi+1âE(Tr)(modr). We also show that a 4-regular strongly IM-extendable graph must be claw-free. As a consequence, the only 4-regular strongly IM-extendable graphs are K4ÃK2, C62 and C82.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Wang Qin, Yuan Jinjiang,