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 \geq 1\) 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\). If no such integer \(n\) exists, the greatest common divisor index of \(G\) is infinite. Several graphs are shown to have infinite greatest common divisor index, including matchings, stars, small paths, and the cycle \(C_4\). It is shown for an edge-transitive graph \(F\) of order \(p\) with vertex independence number less than \(p/2\) that if \(G\) is an \(F\)-decomposable graph of sufficiently large size, then \(G\) is also \((F – e) \cup K_2 -\)decomposable. From this it follows that each such edge-transitive graph has finite index. In particular, all complete graphs of order at least $3$ are shown to have greatest common divisor index \(1\) and the greatest common divisor index of the odd cycle \(C_{2k+1}\) lies between \(k\) and \(4k^2 – 2k – 1\). The graphs \(K_{p} – e\), \(p \geq 3\), have infinite or finite index depending on the value of \(p\); in particular, \(K_{p} – e\) has infinite index if \(p \leq 5\) and index \(1\) if \(p \geq 6\).