Edge-iterated graph parameters: theory and applications to wireless sensor networks

Abstract

In this paper, we study three graph parameters–the iterated chromatic number xn(G), the iterated domination number yn(G), and the iterated covering num- ber Bn(G)—through the line-graph transformations applied successively on a connected graph G. These edge-iterated parameters track how coloring, domination, and covering structures evolve as the graph undergoes successive linegraph transformations. For standard graph families such as paths, cycles, and grid graphs, we derive exact formulas and establish upper and lower bounds, revealing both periodic and divergent behaviours depending on graph structure. Since exact computation of these parameters becomes intractable for large networks, we propose a BFS-based greedy algorithm for estimating xn(G), and benchmark it against the Welsh–Powell and DSATUR algorithms. The simulation results validate the theoretical bounds and show that the proposed method is computationally efficient without significant loss in coloring quality. We further show that these parameters have natural interpretations in wireless sensor networks (WSNs): xn(G) informs frequency and time-slot assignment under multi-hop interference, yn(G) identifies minimal supervisory structures for fault tolerance, and Bn(G) guides energy-aware link monitoring. The framework thus connects iterated graph theory to concrete design problems in sensor network optimization.