Menu
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 \leq p \leq 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.