In the classical p-center location model on a network there is a set of customers, and the primary objective is to select p service centers that will minimize the maximum distance of a customer to a closest center. Suppose that the p centers receive their supplies from an existing central depot on the network, e.g. a warehouse. Thus, a secondary objective is to locate the centers that optimize the primary objective ‘as close as possible’ to the central depot. The paper considers tree networks and two p-center models. It shows that the set of optimal solutions to the primary objective has a semilattice structure with respect to some natural ordering. Using this property the paper proves that there is a p-center solution to the primary objective that simultaneously minimizes every secondary objective function which is monotone nondecreasing in the distances of the p centers from the existing central depot. Restricting the location models to a rooted path network (real line) it proves that the above results hold for the respective classical p-median problems as well.