Premium
Undirected graphs rearrangeable by 2‐length walks
Author(s) -
Barth Dominique,
Panaite Petrişor
Publication year - 1998
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199807)31:4<239::aid-net4>3.0.co;2-e
Subject(s) - vertex (graph theory) , combinatorics , computer science , graph , permutation (music) , mathematics , discrete mathematics , physics , acoustics
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. © 1998 John Wiley & Sons, Inc. Networks 31: 239–247, 1998