Exact Connected Domination in a Proper Enhanced Power Graph Component

Abstract

The k-connected m-dominating set problem combines multiple domination with fault-tolerant connectivity. This paper investigates the problem on a structured graph family arising naturally as a component of a proper enhanced power graph. We first study core-branch graphs H(r;a1,...,as) = K_r join (K_a1 disjoint union ... disjoint union K_as) and obtain an exact feasibility characterization. For m > r and k <= r, the minimum-cardinality problem reduces to the one-dimensional discrete optimization F(z) = z + sum_i min{a_i,m-z}. We then apply the reduction to G = C_p x C_(p^2). The identity is shown to be the unique dominating vertex of its enhanced power graph, and the proper enhanced power graph decomposes as [K_(p-1) join p K_(p(p-1))] disjoint union p K_(p-1). For the distinguished component H_p = K_(p-1) join p K_(p(p-1)), we determine the complete feasibility region and the exact minimum k-connected m-domination number through closed formulas or a one-dimensional minimization. In the only non-closed-form regime, a vertex-level problem on Theta(p^3) vertices is reduced to at most p-k scalar evaluations.