On Additive Bases and Harmonious Graphs

Abstract

This paper first considers several types of additive bases. A typical problem is to find $n_\gamma ( k )$, the largest n for which there exists a set $\{ 0 = a_1 < a_2 < \cdots < a_k \}$ of distinct integers modulo n such that each r in the range $0\leqq r \leqq n - 1$ can be written at least once as $r \equiv a_i + a_j $ (modulo n) with $i < j$. For example, $n_\gamma ( 8 ) = 24$, as illustrated by the set {0, 1, 2, 4, 8, 13, 18, 22}. The other problems arise if at least is changed to at most, or $i < j$ to $i\leqq j$, or if the words modulo n are omitted. Tables and bounds are given for each of these problems. Then a closely related graph labeling problem is studied. A connected graph with n edges is called harmonious if it is possible to label the vertices with distinct numbers (modulo n) in such a way that the edge sums are also distinct (modulo n). Some infinite families of graphs (odd cycles, ladders, wheels, $ \cdots $) are shown to be harmonious while others (even cycles, most complete or complete bipartite graphs, $ \cdots $) are not. In fact most graphs are not harmonious. The function $n_\gamma ( k )$ is the size of the largest harmonious subgraph of the complete graph on k vertices.