Refined Nordhaus–Gaddum-Type Bounds for Roman and Total Domination on δ-Complement Graphs

The δ-complement Gδ of a graph G, introduced by Pai et al., is a variant of the ordinary complement that toggles edges only between vertices of equal degree. Tangjai et al. recently established Nordhaus–Gaddum-type bounds for the ordinary domination number on G and Gδ, raising the natural question of analogous bounds for stronger domination invariants. We prove a sharp Nordhaus–Gaddum-type bound on the Roman domination number of the form γR(G)+γR(Gδ)≤n+3k−2s1−s2, where n is the order of G, k is the number of distinct vertex degrees, and s1,s2 count degree classes of size 1 and 2, respectively. The bound strictly refines the trivial estimate 2(n+k) and is attained on an explicit infinite family of graphs of the form mK2. For the total domination number, we pose the corresponding conjecture γt(G)+γt(Gδ)≤n+2k whenever G and Gδ have no isolated vertices. We are able to settle this bound only in part: we prove it unconditionally on the subclass of graphs whose every degree-class subgraph and its complement are free of isolated vertices, and we verify it computationally for all orders 3≤n≤8, but a proof in full generality remains open, so the bound is stated as a conjecture. The Roman bound is likewise checked by exhaustive enumeration of all 13,595 non-isomorphic simple graphs of orders 3≤n≤8, with zero violations and all 26 sharp instances identified.