In this paper, we propose new mixed integer linear programming (MILP) models for the p-Median problem subject to ring, tree and star backbone topology constraints on the facility locations. More precisely, we minimize simultaneously the total connection cost distances between customers and facilities, and cost distances among facilities when connected under a ring, tree or a star network topology. In principle, all our proposed models can be used in any application related with the classical p-Median problem. Application examples include wired and wireless network design, computer networks, transportation, water supply and electrical networks, just to name a few. The proposed models arise as a combination of the classical p-Median problem with the traveling salesman, spanning tree, and star network problems, respectively. We prove the correctness of each proposed model. Then, we further propose variable neighborhood search (VNS) meta-heuristic algorithms, one for each topology. Our numerical results indicate that the ring models are harder to solve with CPLEX than the tree and star ones. Whilst VNS algorithms proved to be highly efficient when compared to the optimal solutions of the problem for small, medium and large size instances. Moreover, we obtain better feasible solutions than CPLEX for the large instances and in significantly less computational cost. (C) 2018 Elsevier B.V. All rights reserved.