Premium
Hypercube subgraphs with minimal detours
Author(s) -
Erdös Pál,
Hamburger Peter,
Pippert Raymond E.,
Weakley William D.
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199610)23:2<119::aid-jgt3>3.0.co;2-w
Subject(s) - combinatorics , hypercube , mathematics , cube (algebra) , induced subgraph , upper and lower bounds , product (mathematics) , induced subgraph isomorphism problem , discrete mathematics , graph , vertex (graph theory) , line graph , mathematical analysis , geometry , voltage graph
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 ) ≤ d Q n ( 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 thatThe 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. © 1996 John Wiley & Sons, Inc.