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 t he 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 o f vertices at distance less than or equal to k from u induces a Q(n)(k). Tw o characterizations of Q(k)(n)-like graphs are given and an O(d/V(G)/(2)) r ecognition algorithm is presented, where d is the degree of a given d-regul ar graph G. Several examples of Q(n)(k)-like graphs are also listed. (C) 19 99 Published by Elsevier Science B.V. All rights reserved.