ON NTH ORDER DEGREE REGULAR TREES

For n a positive integer and v a vertex of a graph G, the nth order de gree of v in G, denoted by deg(n), v, is defined as the number of vert ices at distance n from v. For k a positive integer, the graph G is sa id to be nth order regular of degree k if, for every vertex v of G, de g(n) v = k. Further, G is defined to be nth order degree regular if G is nth order regular of degree k for some k greater than or equal to 1 . For n greater than or equal to 2, it is shown that an nth order degr ee regular tree has diameter at least 2n - 1, and it is conjectured th at an nth order degree regular tree has diameter equal to 2n - 1. For small values of n, we characterize nth order degree regular trees. For each n greater than or equal to 7 and k greater than or equal to 1, i t is shown that there exists a tree that is nth order regular of degre e k.