Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 857.05027
Autor: Erdös, Pál; Hamburger, Peter; Pippert, Raymond E.; Weakley, William D.
Title: Hypercube subgraphs with minimal detours. (In English)
Source: J. Graph Theory 23, No.2, 119-128 (1996).
Review: What happens to distances in a graph when moving to a subgraph? In an n-dimensional hypercube some distance always increases by at least 2. The minimum number of edges for the subgraph, necessary to keep such detours within 2 for all vertex-pairs, is shown to be at most max{{n+5\over 4n}; {3\over \sqrt{2n}}} of the number of n-hypercube edges, and at least (4-{14n-38\over n2+n-10})2n-1.
Reviewer: F.Plastria (Brussels)
Classif.: * 05C12 Distance in graphs
05C35 Extremal problems (graph theory)
68R10 Graph theory in connection with computer science
Keywords: subgraph; hypercube; distance; detours
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag