Refined Nordhaus–Gaddum-Type Bounds for Roman and Total Domination on δ-Complement Graphs
Mathematics · 22.05.2026 · 14 (11) · 1797
DOI: 10.3390/math14111797 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics, online erschienen am 22.05.2026. Verfasst von Pinhe Chen. Die Arbeit nennt 18 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Chen, P. (2026). Refined Nordhaus–Gaddum-Type Bounds for Roman and Total Domination on δ-Complement Graphs. Mathematics, 14(11), 1797. https://doi.org/10.3390/math14111797
Vancouver
Chen P. Refined Nordhaus–Gaddum-Type Bounds for Roman and Total Domination on δ-Complement Graphs. Mathematics. 2026;14(11):1797. doi:10.3390/math14111797
BibTeX
@article{Chen2026,
author = {Chen, Pinhe},
title = {Refined Nordhaus–Gaddum-Type Bounds for Roman and Total Domination on δ-Complement Graphs},
journal = {Mathematics},
year = {2026},
volume = {14},
number = {11},
pages = {1797},
doi = {10.3390/math14111797}
}
EUVIMED