Trade-offs among degree, diameter, and number of paths.

The degree diameter problem is a fundamental and well-studied problem in extremal graph theory, which deals with trade-offs among three parameters: the maximum degree, the diameter, and the number of vertices in a graph. In this paper, we introduce another parameter that represents the robustness of a network and investigate trade-offs among the parameters. For positive integers r and k , we say that a graph is (r , k) -connected if it contains r internally vertex-disjoint paths of length at most k between any pair of vertices. We consider an (r , k) -connected graph with n vertices whose maximum degree is minimized. Our contribution is to show that the minimum of the maximum degree of such a graph is Θ (max { r n k , r }) , which is a tight bound up to constant factors. [ABSTRACT FROM AUTHOR]