Paired domination in graphs with minimum degree four

Csilla Bujtás; Michael A. Henning

doi:10.1016/j.disc.2025.114923

Paired domination in graphs with minimum degree four

Csilla Bujtás
, Michael A. Henning

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

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 γ_pr(G) of G . We show that if G is a graph of order n and δ(G)≥4, then γ_pr(G)≤1017n<0.5883n.

Original language	English
Article number	114923
Journal	Discrete Mathematics
Volume	349
Issue number	4
DOIs	https://doi.org/10.1016/j.disc.2025.114923
Publication status	Published - Apr 2026

Keywords

Bounds
Minimum degree four
Paired domination

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2025.114923

Cite this

@article{8275a4336a0d42c2bc8332926115367e,

title = "Paired domination in graphs with minimum degree four",

abstract = "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 γpr(G) of G . We show that if G is a graph of order n and δ(G)≥4, then γpr(G)≤1017n<0.5883n.",

keywords = "Bounds, Minimum degree four, Paired domination",

author = "Csilla Bujt{\'a}s and Henning, \{Michael A.\}",

note = "Publisher Copyright: {\textcopyright} 2025 The Author(s).",

year = "2026",

month = apr,

doi = "10.1016/j.disc.2025.114923",

language = "English",

volume = "349",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - Paired domination in graphs with minimum degree four

AU - Bujtás, Csilla

AU - Henning, Michael A.

PY - 2026/4

Y1 - 2026/4

N2 - 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 γpr(G) of G . We show that if G is a graph of order n and δ(G)≥4, then γpr(G)≤1017n<0.5883n.

AB - 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 γpr(G) of G . We show that if G is a graph of order n and δ(G)≥4, then γpr(G)≤1017n<0.5883n.

KW - Bounds

KW - Minimum degree four

KW - Paired domination

UR - https://www.scopus.com/pages/publications/105024004332

U2 - 10.1016/j.disc.2025.114923

DO - 10.1016/j.disc.2025.114923

M3 - Article

AN - SCOPUS:105024004332

SN - 0012-365X

VL - 349

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 4

M1 - 114923

ER -

Paired domination in graphs with minimum degree four

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this