The rapid global shift towards sustainable transportation underscores the urgent need for efficient electric vehicle (EV) infrastructure. A major barrier to widespread EV adoption is the irregular and inadequate distribution of charging stations. This paper introduces a graph-theoretic model, termed auto charge domination, to optimize the placement of EV charging stations across transportation networks. By modeling roads as graphs—with vertices representing cities and intersections, and edges representing road segments—we apply domination theory to determine the minimum number of strategically located charging stations. A new parameter, the auto charge domination number, is introduced to ensure that all locations, including pendant vertices (minor or unsurveyed roads), remain within 200 km round-trip distance of a station. The methodology involves constructing graphs from highway layouts, ensuring all nodes are covered within reach, and analyzing the auto charge domination number for classical graphs such as path, cycle, Petersen, and bipartite graphs. Our results reveal that fewer, strategically placed stations can provide comprehensive coverage, improving infrastructure cost-efficiency without compromising accessibility.
Punitha et al. (Wed,) studied this question.