6.2. Decompositions
A decomposition of a graph G
is a collection of nonempty subgraphs such that
for some nonempty subset
, where
is a partition of
.
Consequence: No subgraph in a
decomposition of G contains isolated vertex.
If is a
decomposition of G, then we write
,
as we do with factorization., and
say G is decomposed into sub-graphs , where then
.
What is the connection between factorization and decomposition?
If , is a decomposition of a graph G of order n
and we define
, then
,
is a factorization of G.
Every factorization of a nonempty graph also gives rise to a decomposition of G:
Suppose that is a
factorization of a nonempty graph G, so written that
are nonempty
.
Let . Then
is a decomposition of G.
If is a
decomposition of a graph G such that
for some graph H
for each i, then G is said to be H-decomposable. In that
case we also write
and say that H
divides G, or G is a multiple of H.
If G is H-decomposable, then . Although this condition is necessary, it is easy to
see that it is not sufficient. (
divides the
size 12 of G, but G
is not
-decomposable.)
The basic problem in this context: given a graph G and a subgraph H of G whose size divides that of G whether, the graph G is H-decomposable. Evidences:
-
Every graph is
-decomposable
-
Every component of a
-decomposable graph has even size.
Theorem 6.5. A nontrivial connected graph G
is -decomposable iff G has even
size.
Proof.
The necessary part of the statement is obvious.
For the converse, assume that G has even size.
Suppose, first,
that G is eulerian, where the edges of G are encountered in the order
.
Then each of the sets induce a copy of
. So G is
-decomposable.
Otherwise, G has 2k odd vertices for some .
By Theorem 6.3, can be partitioned into subsets
, where for each
is an open
trail
of even length connecting odd vertices of G.
Then, as with the eulerian circuit above, the
edges of each trail can be
paired off so that each pair of edges induces a copy of
.
Theorem 6.6. A nontrivial graph G is -decomposable iff G has even size
and
.
Theorem 6.7. The
complete graph Kn is K3-decomposable iff n
is odd and .
Theorem 6.8. (Wilson, 1975): For every graph H without isolated vertices and having size m, there exists a positive integer N such that
where
then is H-decomposable.