Generalized maximum degree (Q2725021)

The generalized maximum degree \(\Delta_k(G)\) of a graph \(G\) of order \(n\geq k\) is the maximum cardinality of the union of the neighbourhoods of \(k\) of its vertices. The authors study bounds on \(\Delta_k(G)\) in terms of the order \(n\), the maximum degree \(\Delta(G)=\Delta_1(G)\) and the total domination number of \(G\). They also study \((k,r)\)-regular graphs, i.e. graphs for which the union of the neighbourhoods of every set of \(k\) vertices has cardinality \(r\). Using results of \textit{R. Faudree} and \textit{D. Knisley} [Congr. Numerantium 121, 105-108 (1996; Zbl 0896.05052)] they show that for large order the complete graph is the only \((2,r)\)-regular graph for \(r\geq 3\). They prove further results on \((2,r)\)-regular graphs and show that the complete graph is the only regular \((2,r)\)-regular graph for \(r\geq 3\).