The k‐Radius of 2‐Connected Graphs

ABSTRACT Let be a connected graph. If is a set of vertices of , and is a vertex of , then the distance is the distance between and a vertex of closest to . The eccentricity of is defined as . For , the ‐radius of is defined as the smallest eccentricity of a set of vertices of . The ‐radius is, in some sense, a dual to the ‐distance domination number of , defined as the minimum cardinality of a set of vertices of such that every vertex not in is within distance of some vertex in . We prove that the ‐radius of a 2‐connected graph of order is at most . We also extend the well‐known result that the vertex set of a 2‐connected graph can be partitioned into two subsets of prescribed order, each inducing a connected subgraph. We prove that if we allow a small overlap between the sets, then the vertex set of a 2‐connected graph can be expressed as the union of three subsets of prescribed order, each inducing a connected subgraph.