Graphs which locally mirror the hypercube structure
Let Q(n) be the n-cube and let Q(n)(k) be the subgraph of Q(n) induced by the vertices at distance less than or equal to k from a given vertex. Q(n)(k)- like graphs are introduced as graphs in which for any vertex u the set of vertices at distance less than or equal to k from u induces a Q(n)(k). Two characterizations of Q(k)(n)-like graphs are given and an O(d/V(G)/(2)) recognition algorithm is presented, where d is the degree of a given d-regular graph G. Several examples of Q(n)(k)-like graphs are also listed. (C) 1999 Published by Elsevier Science B.V. All rights reserved.
hypercube recognition algorithm algorithms interconnection network folded cube