Municipal water delivery networks face increasing demands due to population growth. We focus on enhancing a water utility's infrastructure to meet its growing demands in a cost effective manner. Specifically, we consider the problem of placing pressure boosting pumps in a water network such that the minimum required delivery pressure is maintained at all the consumption points in the network for a given demand and the pump placement costs are minimized. The cost could be either energy cost or total cost dollars. Iterative optimization strategies and evolutionary computation techniques are typically used for solving such enhancement problems. We take a different perspective exploiting the structure of the network using graph theoretic principles. For water networks with tree topologies, we determine the optimal pump placement in terms of energy costs. We find that this energy optimal solution need not always minimize the total cost of ownership (TCO) involved in the pump placement. Therefore, we propose heuristic methodologies that reduce the TCO involved in placing pressure boosting pumps in tree networks. For water networks with complex topologies involving loops, we use the best of our tree solutions to find the initial seeds for iterative search strategies such as genetic algorithms (GA) and successive linear programming (SLP). We use EPANET for hydraulic modeling and study the efficacy of the proposed solution in terms of the TCO. In real-world topologies we considered, our heuristic seeding improves the performance of GA and SLP by about 68 % and 26 % respectively. © 2012 IEEE.