Generalized maximum degree and totally regular graphs

Abstract

For a positive integer t, a graph G has generalized maximum degree Δ_t(G) = s if the cardinality of the union of the neighborhoods of each set of t independent vertices is at most s. The generalized minimum degree δ_t(G) is defined similarly. If Δ_t(G) = δ_t(G) = r, then we say G is a (t, r)-regular graph. We present relationships involving Δ_t(G) and other graph parameters. All (2, 1)-regular and (2,2)-regular graphs are determined and properites of (t, r)-regular graphs are presented. In addition, we define and initiate the study of totally regular and totally r-regular graphs. Finally, we characterize the totally r-regular graphs.