DIMACS TR: 2002-02

Additive Bases and Extremal Problems in Groups, Graphs and Networks

Authors: D. Frank Hsu, and Xingde Jia


Bases in sets and groups and their extremal problems have been studied in additive number theory such as the postage stamp problem. On the other hand, Cayley graphs based on specific finite groups have been studied in algebraic graph theory and applied to constant efficient communication networks such as circulant networks with minimum diameter (or transmission delay). In this paper we establish a framework which defines and unifies additive bases in groups, graphs and networks and survey results on the bases and their extremal problems. Some well known and well studied problems such as harmonious graphs and perfect addition sets are also shown to be special cases of the framework.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-02.ps.gz
DIMACS Home Page