Paired domination in graphs with minimum degree four

Bujtás, Csilla (author), Henning, Michael A. (author)

A set $S$ of vertices in a graph $G$ is a paired dominating set if every vertex of $G$ is adjacent to a vertex in $S$ and the subgraph induced by $S$ admits a perfect matching. The minimum cardinality of a paired dominating set of $G$ is the paired domination number $\gamma_{pr}(G)$ of $G$. We show that if $G$ is a graph of order $n$ and $\delta(G) \ge 4$, then $\gamma_{pr}(G) \le 10n/17 < 0.5883n$.

• Language: English
• Keywords: paired domination, bounds, minimum degree four
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.04.2026
• Year: 2026
• Number of pages: 10 str.
• Numbering: Vol. 349, iss. 4, art. no. 114923
• PID: 20.500.12556/RUL-180272
• UDC: 519.17
• ISSN on article: 0012-365X
• DOI: 10.1016/j.disc.2025.114923
• COBISS.SI-ID: 270544131
• Publication date in RUL: 05.03.2026

Record is a part of a journal

• Title: Discrete mathematics
• Shortened title: Discrete math.
• Publisher: Elsevier
• ISSN: 0012-365X
• COBISS.SI-ID: 1118479

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: dominacija v parih, meje, minimalna stopnja štiri