Undirected graphs rearrangeable by 2‐length walks

Journal Article


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

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.