Name
Abstract | ||
|---|---|---|
Define a minimal detour subgraph of the n-dimensional cube to be a spanning subgraph G of Q(n) having the property that for vertices x, y of Q(n), distances are related by d(G)(x, y) less than or equal to d(Qn) (x, y) + 2. Let f(n) be the minimum number of edges of such a subgraph of Q(n). After preliminary work on distances in subgraphs of product graphs, we show that f(n)/\E((Qn)\ < c/root n. The subgraphs we construct to establish this bound have the property that the longest distances are the same as in Q(n), and thus the diameter does not increase. We establish a lower bound for f(n), show that vertices of high degree must be distributed throughout a minimal detour subgraph of Q(n), and end with conjectures and questions. (C) 1996 John Wiley & Sons, Inc. |
Year | DOI | Venue |
|---|---|---|
1996 | 3.3.CO;2-9" target="_self" class="small-link-text"10.1002/(SICI)1097-0118(199610)23:23.3.CO;2-9 | Journal of Graph Theory |
Field | DocType | Volume |
Topology,Discrete mathematics,Combinatorics,Hypercube,Mathematics | Journal | 23 |
Issue | ISSN | Citations |
2 | 0364-9024 | 8 |
PageRank | References | Authors |
1.35 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Erdös | 1 | 192 | 39.34 |
| Peter Hamburger | 2 | 54 | 14.61 |
| Raymond E. Pippert | 3 | 41 | 5.89 |
| William D. Weakley | 4 | 56 | 10.40 |