Publication Date:
2003-03-01
Description:
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 equiv 0 , ({
m mod}, 3)$, $q equiv 0 , ({
m mod}, inom n2)$ and(1) $q
eq 3 inom n2$ when $n equiv 5 , ({
m mod}, 6)$; (2) $q geq (n + 1) inom n2$ when $n$ is even; (3) $q
otin {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.
Print ISSN:
0024-6115
Electronic ISSN:
1460-244X
Topics:
Mathematics
Permalink