Journal
DISCRETE APPLIED MATHEMATICS
Volume 157, Issue 7, Pages 1354-1363Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.dam.2008.11.005
Keywords
Cayley graphs; Groups; Disjoint ordering; Disjoint paths; Hypercubes; Star distances; Star diameters
Categories
Funding
- National Science Foundation (NSF) [DMS9970637]
- National Security Agency (NSA) [MDA904-02-1-0067]
- DOD Multidisciplinary University Research Initiative (MURI) program administered by the Office of Naval Research [N00014-00-1-0565]
- South Carolina Commission on Higher Education
Ask authors/readers for more resources
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 Qju [S. Gao, B. Novick, K. Qiu, From Hall's matching theorem to optimal routing on hypercubes, J. Comb. Theory B 74 (1998) 291-301]. (C) 2008 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
