Generalized Maximum Degree
Document Type
Article
Publication Date
5-1-2001
Description
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.
Citation Information
Haynes, Teresa W.; and Markus, Lisa R.. 2001. Generalized Maximum Degree. Utilitas Mathematica. Vol.59 155-165. ISSN: 0315-3681