Premium
Common Multiples of Complete Graphs
Author(s) -
Bryant Darryn,
Maenhaut Barbara
Publication year - 2003
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/s0024611502013771
Subject(s) - combinatorics , mathematics , graph , discrete mathematics , existential quantification , order (exchange) , complete graph , least common multiple , finance , economics
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.