NEIGHBORHOOD REGULAR GRAPHS

摘要

A regular graph G is called vertex transitive if the automorphism group of G contains a single orbit. In this paper we define and consider another class of regular graphs called neighborhood regular graphs abbreviated NR. In particular, let G be a graph and N[v] be the closed neighborhood of a vertex v of G. Denote by G(N[v]) the subgraph of G induced by N[v]. We call G NR if G(N[v]) ≈ G(N[v']) for each pair of vertices v and v' in V(G). A vertex transitive graph is necessarily NR. The converse, however, is in general not true as is shown by the union of the cycles C_4 U C_5. Here we provide a method for constructing an infinite class of connected NR graphs which are not vertex transitive. A NR graph G is called neighborhood regular relative to N if N[v] ≈ N for each v ∈ V(G). Necessary conditions for N are given along with several theorems which address the problem of finding the smallest order (size) graph that is NR relative to a given N. A table of solutions to this problem is given for all graphs TV up to order five.