Results about Graph Decomposition, Greatest Common Divisor Index for Graphs and for Digraphs

Abstract

A graph $H$ is $G$-decomposable if $H$ can be decomposed into subgraphs, each of which is isomorphic to $G$. A graph $G$ is a greatest common divisor of two graphs $G_1$ and $G_2$ if $G$ is a graph of maximum size such that both $G_1$ and $G_2$ are $G$-decomposable. The greatest common divisor index of a graph $G$ of size $q$ is the greatest positive integer $n$ for which there exist graphs $G_1$ and $G_2$, both of size at least $nq$, such that $G$ is the unique greatest common divisor of $G_1$ and $G_2$. The corresponding concepts are defined for digraphs. Relationships between greatest common divisor index for a digraph and for its underlying graph are studied. Several digraphs are shown to have infinite index, including matchings, short paths, union of stars, transitive tournaments, the oriented 4-cycle. It is shown that for $5\le p\le 10$, if a graph $F$ of sufficiently large size is $C_p$-decomposable, then $F$ is also $(P_{p-1}\cup P_3)$-decomposable. From this it follows that the even cycles $C_6$, $C_8$ and $C_{10}$ have finite greatest common divisor index.