Generalized maximum degree

Abstract

For a graph G = (V, E) with order n, we define the the generalized maximum degree Δ_k(G) as follows: Δ_k(G) = max{\N (S)\ : S is a set of k vertices} for 1 ≤ k ≤ n. We give bounds on Δ_k(G) and characterize the trees which achieve one of these lower bounds. We define and study (k, r)-regular graphs, that is, graphs for which every subset of V with cardinality k has degree r. In particular, we show that if G is (2, r)-regular for r ≥ 3 and has sufficiently large or sufficiently small order, then G is the complete graph K_r. Finally, we characterize the regular (2, r)-regular graphs.