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.