Packing 3-Vertex Paths in Claw-Free Graphs

Details Packing 3-Vertex Paths in Claw-Free Graphs Packing 3-Vertex Paths in Claw-Free Graphs

2007-11-25

arxiv.org/abs/0711.3871v1

Mathematics

Combinatorics

12 pages

Scientific paper

An L-factor of a graph G is a spanning subgraph of G whose every component is a 3-vertex path. Let v(G) denote the number of vertices of G. A graph is called claw-free if it does not have a subgraph isomorphic to the graph with 4 vertices and 3 edges having a common vertex. Our results include the following. Let G$ be a 3-connected claw-free graph, x be a vertex, e = xy be an edge, and P be a 3-vertex path in G. Then (c1) if v(G) = 0 mod 3, then G has an L-factor containing (avoiding) e, (c2) if v(G) = 1 mod 3, then G - x has a L-factor, (c3) if v(G) = 2 mod 3, then G - x -y has an L-factor, (c4) if v(G) = 0 mod 3 and G is either cubic or 4-connected, then G - P has an L-factor, and (c5) if G is cubic and E is a set of three edges in G, then G - E has an L -factor if and only if the subgraph induced by E in G is not a claw and not a triangle. Keywords: claw-free graph, cubic graph, L-packing, L-factor.

Affiliated with

Also associated with

No associations

Rating

Packing 3-Vertex Paths in Claw-Free Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Packing 3-Vertex Paths in Claw-Free Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packing 3-Vertex Paths in Claw-Free Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-511950