Tell me more ×
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.
up vote 3 down vote favorite

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

share|improve this question

1 Answer

up vote 2 down vote

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 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 at 18:13

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.