ON A CONJECTURE ON nTH ORDER DEGREE REGULAR GRAPHS

Abstract

For n a positive integer and v a vertex of a graph G, the nth order degree of v in G, denoted by deg_nv, is the number of vertices at distance n from v. The graph G is said to be nth order regular of degree k if, for every vertex v of G, deg_nv = k. The following conjecture due to Alavi, Lick, and Zou is proved: For n ≥ 2, if G is a connected nth order regular graph of degree 1, then G is either a path of length 2n—1 or G has diameter n. Properties of nth order regular graphs of degree k, k ≥ 1, are investigated.