Paired domination in graphs with minimum degree four

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

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

• Jezik: Angleški jezik
• Ključne besede: paired domination, bounds, minimum degree four
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Datum objave: 01.04.2026
• Leto izida: 2026
• Št. strani: 10 str.
• Številčenje: Vol. 349, iss. 4, art. no. 114923
• PID: 20.500.12556/RUL-180272
• UDK: 519.17
• ISSN pri članku: 0012-365X
• DOI: 10.1016/j.disc.2025.114923
• COBISS.SI-ID: 270544131
• Datum objave v RUL: 05.03.2026

Gradivo je del revije

• Naslov: Discrete mathematics
• Skrajšan naslov: Discrete math.
• Založnik: Elsevier
• ISSN: 0012-365X
• COBISS.SI-ID: 1118479

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: dominacija v parih, meje, minimalna stopnja štiri