EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Pinhe Chen

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →