|
|||||
|
|
Short containers in Cayley graphs |
|
| Authors: | Shuhong Gao D. Frank Hsu |
| Affiliation: | a Department of Mathematical Sciences, Clemson University, Clemson, SC 29634, USA b Department of Computer and Information Science, 113 West 60th Street, LL 813, Fordham University, New York, NY 10023, USA c DIMACS, Rutgers University, Piscataway, NJ 08854-8018, USA |
| 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 [S. Gao, B. Novick, K. Qiu, From Hall’s matching theorem to optimal routing on hypercubes, J. Comb. Theory B 74 (1998) 291-301]. |
| Keywords: | Cayley graphs Groups Disjoint ordering Disjoint paths Hypercubes Star distances Star diameters |
| 本文献已被 ScienceDirect 等数据库收录！ | |