Generalized Maximum Degree

Document Type


Publication Date



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 Kr. Finally, we characterize the regular (2, r)-regular graphs.

This document is currently not available here.