On a Graph Theoretic Division Algorithm and Maximal Decompositions of Graphs

Abstract

For two graphs $H$ and $G$, a decomposition $\mathcal{D}=\{H_1,H_2,\dots ,H_k,R\}$ of $G$ is called an $H$-maximal $k$-decomposition if $H_i\cong H$ for $1\le i\le k$ and $R$ contains no subgraph isomorphic to $H$. Let $\text{Min}(G,H)$ and $\text{Max}(G,H)$ be the minimum and maximum $k$, respectively, for which $G$ has an $H$-maximal $k$-decomposition. A graph $G$ without isolated vertices is said to possess the intermediate decomposition property if for each connected graph $G$ and each integer $k$ with $\text{Min}(G,H)\le k\le \text{Max}(G,H)$, there exists an $H$-maximal $k$-decomposition of $G$. For a set $S$ of graphs and a graph $G$, a decomposition $\mathcal{D}=\{H_1,H_2,\dots ,H_k,R\}$ of $G$ is called an $S$-maximal $k$-decomposition if $H_i\cong H$ for some $H\in S$ for each integer $i$ with $1\le i\le k$ and $R$ contains no subgraph isomorphic to any subgraph in $S$. Let $\text{Min}(G,S)$ and $\text{Max}(G,S)$ be the minimum and maximum $k$, respectively, for which $G$ has an $S$-maximal $k$-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 $k$ with $\text{Min}(G,S)\le k\le \text{Max}(G,S)$, there exists an $S$-maximal $k$-decomposition of $G$. While all those graphs of size $3$ have been determined that possess the intermediate decomposition property, as have all sets consisting of two such graphs, here all remaining sets of graphs having size $3$ that possess the intermediate decomposition property are determined.