Premium
Diameter‐preserving orientations of the torus
Author(s) -
Konig JeanClaude,
Krumme David W.,
Lazard Emmanuel
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(199808)32:1<1::aid-net1>3.0.co;2-g
Subject(s) - torus , combinatorics , mathematics , graph , impossibility , toroid , undirected graph , curse of dimensionality , geometry , physics , statistics , plasma , quantum mechanics , political science , law
The diameter of a directed graph is the maximum of the lengths of the shortest paths between all pairs of vertices. A directed graph is said to be tightly oriented if it has the same diameter as its undirected image graph. Our main result is tight orientations for all sufficiently large toroids, except those whose sizes in both dimensions are odd. We also prove the impossibility of tightly orienting all the toroids for which we do not present tight orientations, and we give partial results for dimensionality higher than two. © 1998 John Wiley & Sons, Inc. Networks 32: 1–11, 1998