2001-18: Short containers in Cayley graphs

DIMACS TR: 2001-18

Short containers in Cayley graphs

Authors: Shuhong Gao and D. Frank Hsu

ABSTRACT
The star diameter of a graph measures the minimum distance from any source node to several other target nodes in the graph. For a class of Cayley graphs from abelian groups, a good upper bound for their star diameters is given in terms of the usual diameters and the orders of elements in the generating subsets. This bound is tight for several classes of graphs including hypercubes and directed $n$-dimensional tori. The technique used is the so-called disjoint ordering for a system of subsets, due to Gao, Novick and Qiu (1998).

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-18.ps.gz

DIMACS Home Page