A graph theoretic division algorithm
Abstract
For two graphs H and G, a decomposition D ={H1, H 2...Hκ R} of G is called an H-maximal κ-decomposition if Hi ≅ H for 1 < i < κ and R contains no subgraph isomorphic to H. Let Min(G,H) and Max(G,H) be the minimum and maximum κ, respectively, for which G has an H-maximal κ-decomposition. A graph H without isolated vertices is said to possess the intermediate decomposition property if for each connected graph G and each integer κ with Min(G, H) < κ < Max(G, H), there exists an H-maximal κ-decomposition of G. For a set S of graphs and a graph G a decomposition D = {H1,H2,...,HκR} of G is called an S-maximal κ-decomposition if Hi ≅ H for some H ∈ S for each integer i with 1 < i <κ and R contains no subgraph isomorphic to any subgraph in S. Let Min(G, S) and Max(G, S) be the minimum and maximum κ , respectively, for which G has an S-maximal κ-decomposition. A set S of graphs without isolated vertices is said to possess the intermediate decomposition property if for every connected graph G and each integer κ with Min(G,5) < κ < Max(G,S), there exists an S- maximal κ-decomposition of G. All graphs of size 3 or less are determined that possess the intermediate decomposition property. Sets of graphs having size 3 that possess the intermediate decomposition property are investigated. In particular, all such sets consisting of two graphs are determined.
