We consider a generalized version of the (weighted) one-center problem on graphs. Given an undirected graph G of n vertices and m edges and a positive integer \(k\le n\) , the problem aims to find a point on G so that the maximum (weighted) distance from it to k connected vertices on its shortest path tree(s) is minimized. No previous work has been proposed for this problem except for the case \(k=n\) , that is, the classical graph one-center problem. In this paper, an \(O(mn\log n\log mn + m^2\log n\log mn)\) -time algorithm is proposed for the weighted case, and an \(O(mn\log n)\) -time algorithm is presented for the unweighted case, provided that the distance matrix is given. When G is a tree graph, we give an \(O(n\log ^2 n\log k)\) -time algorithm for the weighted case and improve it to \(O(n\log ^2 n)\) for the unweighted case.