Common Multiples of Complete Graphs

A graph H is said to divide a graph G if there exists a set S of subgraphs of G , all isomorphic to H , such that the edge set of G is partitioned by the edge sets of the subgraphs in S . Thus, a graph G is a common multiple of two graphs if each of the two graphs divides G . This paper considers common multiples of a complete graph of order m and a complete graph of order n . The complete graph of order n is denoted K n . In particular, for all positive integers n , the set of integers q for which there exists a common multiple of K 3 and K n having precisely q edges is determined. It is shown that there exists a common multiple of K 3 and K n having q edges if and only if q ≡ 0 (mod 3), q ≡ 0 (mod n 2) and (1) q ≠ 3 n 2 when n ≡ 5 (mod 6); (2) q ⩾ (n + 1) n 2 when n is even; (3) q ∉ {36, 42, 48} when n = 4. The proof of this result uses a variety of techniques including the use of Johnson graphs , Skolem and Langford sequences , and equitable partial Steiner triple systems . 2000 Mathematical Subject Classification : 05C70, 05B30, 05B07.