The Greatest Common Divisor Index of a Graph

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\ge 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\ge 3$, have infinite or finite index depending on the value of $p$; in particular, $K_p–e$ has infinite index if $p\le 5$ and index $1$ if $p\ge 6$.