TY - JOUR
T1 - Hypercube subgraphs with local detours
AU - Hamburger, Peter
AU - Kostochka, Alexandr V.
AU - Sidorenko, Alexander
PY - 1999/2
Y1 - 1999/2
N2 - A minimal detour subgraph of the n-dimensional cube is a spanning subgraph G of Qn having the property that, for vertices x, y of Qn, distances are related by dG(x, y) ≤ dQn (x, y)+2. Fora spanning subgraph G of Qn to be a local detour subgraph, we require only that the above inequality be satisfied whenever x and y are adjacent in Qn. Let f(n) (respectively, fl(n)) denote the minimum number of edges in any minimal detour (respectively, local detour) subgraph of Qn (cf. Erdos et al. [1]). In this article, we find the asymptotics of fl(n) by showing that 3 · 2n(1 - O(n-1/2)) < fl(n) < 3 · 2n(1 + 0(1)). We also show that f(n) > 3.00001 · 2n (for n > n0), thus eventually fl(n) < f(n), answering a question of [1] in the negative. We find the order of magnitude of fl(n), the minimum possible maximum degree in a local detour subgraph of Qn: √2n + 0.25 - 0.5 ≤ Fl(n) ≤ 1.5√2n - 1.
AB - A minimal detour subgraph of the n-dimensional cube is a spanning subgraph G of Qn having the property that, for vertices x, y of Qn, distances are related by dG(x, y) ≤ dQn (x, y)+2. Fora spanning subgraph G of Qn to be a local detour subgraph, we require only that the above inequality be satisfied whenever x and y are adjacent in Qn. Let f(n) (respectively, fl(n)) denote the minimum number of edges in any minimal detour (respectively, local detour) subgraph of Qn (cf. Erdos et al. [1]). In this article, we find the asymptotics of fl(n) by showing that 3 · 2n(1 - O(n-1/2)) < fl(n) < 3 · 2n(1 + 0(1)). We also show that f(n) > 3.00001 · 2n (for n > n0), thus eventually fl(n) < f(n), answering a question of [1] in the negative. We find the order of magnitude of fl(n), the minimum possible maximum degree in a local detour subgraph of Qn: √2n + 0.25 - 0.5 ≤ Fl(n) ≤ 1.5√2n - 1.
KW - Hypercube
KW - Local detour
KW - Minimal detour
UR - http://www.scopus.com/inward/record.url?scp=0033479277&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0033479277&partnerID=8YFLogxK
U2 - 10.1002/(SICI)1097-0118(199902)30:2<101::AID-JGT4>3.0.CO;2-9
DO - 10.1002/(SICI)1097-0118(199902)30:2<101::AID-JGT4>3.0.CO;2-9
M3 - Article
AN - SCOPUS:0033479277
SN - 0364-9024
VL - 30
SP - 101
EP - 111
JO - Journal of Graph Theory
JF - Journal of Graph Theory
IS - 2
ER -