Distance Transfer and Exact Convex Hop Domination in Powers of Paths

Abstract

Graph powers change vertex distances in a way that can be described directly from the metric of the original graph. This makes them useful for examining domination parameters defined by distance. Here we study convex hop domination in powers of paths and determine its value for all relevant values of n and k. The analysis begins with the relation dGᵏ(u, v) = ⌈dG(u, v)/k⌉. Thus, distance two in Gᵏ corresponds in the original graph to k < dG(u, v) ≤ 2k. For path powers, this distance condition can be considered together with geodesic convexity. Arithmetic progressions with step k give the required constructions, while the positions of their endpoints provide the lower bounds. For k ≥ 2, we obtain γconh(Pₙᵏ) = n for 2 ≤ n ≤ k + 1; γconh(Pₙᵏ) = min{k + 1, 2k − n + 4} for k + 2 ≤ n ≤ 2k; and γconh(Pₙᵏ) = max{3, ⌈(n − 1)/k⌉ − 3} for n ≥ 2k + 1. The case k = 1 is handled separately and gives γconh(Pₙ) = max{2, n − 4}. These cases determine the convex hop domination number for every nontrivial power of a path. The formulas also give explicit optimal certificates. As a separate computational check, exhaustive enumeration was carried out for 102 instances with 1 ≤ k ≤ 6 and 2 ≤ n ≤ 18; every computed minimum agreed with Theorem 23.