Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If a graph G is H-decomposable does it imply that G has H-factor?

share|improve this question
add comment

1 Answer

No. An $H$-factor is a set of vertex-disjoint copies of $H$ that partition the vertex set of a graph, while an $H$-decomposition is a set of edge-disjoint copies of $H$ that partition the edge set of a graph.

For example, let $H = K_3$ and let $G$ be the $5$-vertex graph consisting of two triangles with a point in common. Then $G$ clearly has an $H$-decomposition, but, since $3 \nmid 5$, it cannot have an $H$-factor.

share|improve this answer
    
Say i have a graph G with 3m vertices, and that G is $C_3$-decomposable. Can i say now that G has $C_3_-factor? –  kim_kibun Feb 21 '13 at 14:44
    
@kim_kibun Again, not necessarily. Let $G$ be the $6$-vertex graph obtained by taking a triangle and adding three vertices, each adjacent to two of the vertices of the triangle. (More formally, let the vertices of the triangle be $u$, $v$, and $w$, and let the other three vertices be $a$, $b$, and $c$. Let $a$ be adjacent to $u$ and $v$, $b$ to $v$ and $w$, and $c$ to $w$ and $u$.) Then $G$ has a $K_3$-decomposition but no $K_3$-factor. –  Andrew Uzzell Feb 21 '13 at 18:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.