Generalized Maximum Degree and Totally Regular Graphs

Document Type


Publication Date



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.

This document is currently not available here.