From Hall's matching theorem to the star diameter of abelian Cayley graphs
by
Beth Novick
Clemson University
Coauthors: Shuhong Gao (Clemson Univerity)

The concept of so-called disjoint ordering for any collection of finite sets introduced by Gao, Novick and Qiu can be viewed as a generalization of a system of distinct representatives for the sets. Hall's "marriage" condition for a collection of finite sets guarantees the existence of a disjoint ordering for the sets. We review disjoint orderings and their connection to disjoint paths in n-dimensional hypercubes. We present some further results on disjoint ordering due to Gao and Hsu. These give bounds on the star diameters of certain classes of Cayley graphs from abelian groups.

Date received: April 18, 2008