✦ LIBER ✦
Undirected graphs rearrangeable by 2-length walks
✍ Scribed by Barth, Dominique; Panaite, Petri?or
- Publisher
- John Wiley and Sons
- Year
- 1998
- Tongue
- English
- Weight
- 147 KB
- Volume
- 31
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper, we deal with 2-rearrangeable graphs, that is, graphs in which every permutation can be routed in two steps, such that each packet moves on a walk of length 2 without vertex-contention. We give necessary and sufficient conditions for a graph to be 2-rearrangeable. We end by proposing a construction of k-rearrangeable graphs, where k ¢ 2.