School Seminars and Colloquia

Difference Labellings of Complete Graphs and Some of Their Applications

ORSUM Seminar

by Prof Gary Bloom


Institution: City University of New York
Date: Fri 12th August 2005
Time: 1:00 PM
Location: Room 213, Richard Berry Building, The University of Melbourn

Abstract: A graph G with e edges and having no multiple edges or loops is gracefully
labelled if one assigns a unique label taken from a subset of the integers
{0, 1, 2, ..., e} to each of its n nodes in such a way that {1, 2, 3, ..., e} is the set of edge labels resulting from assigning label | u-v | to the edge
with u and v assigned to its endnodes. Graceful labellings may be said to be
(1) non-redundant, since no edge value is repeated, (2) gapless, since no integer between 1 to e is missing from the set of edge labels, and
(3) maximum span, since the largest value in the set of edge labels equals the size of that set.

These three properties are useful in a variety of practical settings, especially since the set of edge labels on complete graph Kn corresponds to
the set of measurements that can be made with a ruler having exactly n marks appearing at distances from one end of the ruler that correspond to the labels on the vertices of Kn.

Unfortunately (as we will show) the only complete graphs that can be gracefully labeled are K1, K2, K3, and K4.

Still there are a variety of useful applications that result when one of the three "graceful graph properties" are given up while the others are retained.
We will show how the graph (and ruler) labellings act as design principles for some applications. Examples will be chosen from x-ray crystallography, radar pulse codes, missile guidance codes, layout design for multiple detector radio telescopes, sonar codes, and specification of addresses in some communications networks.

For More Information: Mark Fackrell tel. 8344 8053 email: m.fackrell@ms.unimelb.edu.au