5.3. Factorization
A graph G is
said to be factorable into the factors if for these factors
-
for ech
,
-
if
then
if
.
-
If G is factored into then we
represent this by
,
which is called a factorization of G.
If there exists a factorization of a graph G such that each factor is a r-factor ( for a fixed r), then G is r-factorable.
Fact. If G is r factorable then necessarily G is k-regular for some integer k that is a multiple of r.
If a graph G is factorable into , where each
for some graph H,
then we say that G is H-factorable and that G has an
isomorphic factorization into the factor H.
Fact. If a graph G is H-factorable, then the size of H divides the size of G.