New probabilistic upper bounds on the domination number of a graph: II

Michael A. Henning; Nader Jafari Rad

doi:10.1016/j.disc.2025.114656

New probabilistic upper bounds on the domination number of a graph: II

Michael A. Henning
, Nader Jafari Rad

Mathematics and Applied Mathematics

Shahed University

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

1 Citation (Scopus)

Abstract

A set S of vertices in a graph G is a dominating set of G if every vertex not in S has a neighbor in S, where two vertices are neighbors if they are adjacent. The domination number, γ(G), of G is the minimum cardinality among all dominating sets of G. In this paper, we obtain new (probabilistic) upper bounds for the domination number of a graph in terms of its order, minimum degree and maximum degree. These new bounds improve previous bounds given in Jafari Rad (2019) [15].

Original language	English
Article number	114656
Journal	Discrete Mathematics
Volume	349
Issue number	1
DOIs	https://doi.org/10.1016/j.disc.2025.114656
Publication status	Published - Jan 2026

Keywords

Domination number
Probabilistic bounds

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2025.114656

Cite this

@article{665890afb438422b881c3417cf9f5437,

title = "New probabilistic upper bounds on the domination number of a graph: II",

abstract = "A set S of vertices in a graph G is a dominating set of G if every vertex not in S has a neighbor in S, where two vertices are neighbors if they are adjacent. The domination number, γ(G), of G is the minimum cardinality among all dominating sets of G. In this paper, we obtain new (probabilistic) upper bounds for the domination number of a graph in terms of its order, minimum degree and maximum degree. These new bounds improve previous bounds given in Jafari Rad (2019) [15].",

keywords = "Domination number, Probabilistic bounds",

author = "Henning, \{Michael A.\} and \{Jafari Rad\}, Nader",

note = "Publisher Copyright: {\textcopyright} 2025 Elsevier B.V.",

year = "2026",

month = jan,

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

language = "English",

volume = "349",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - New probabilistic upper bounds on the domination number of a graph

T2 - II

AU - Henning, Michael A.

AU - Jafari Rad, Nader

PY - 2026/1

Y1 - 2026/1

N2 - A set S of vertices in a graph G is a dominating set of G if every vertex not in S has a neighbor in S, where two vertices are neighbors if they are adjacent. The domination number, γ(G), of G is the minimum cardinality among all dominating sets of G. In this paper, we obtain new (probabilistic) upper bounds for the domination number of a graph in terms of its order, minimum degree and maximum degree. These new bounds improve previous bounds given in Jafari Rad (2019) [15].

AB - A set S of vertices in a graph G is a dominating set of G if every vertex not in S has a neighbor in S, where two vertices are neighbors if they are adjacent. The domination number, γ(G), of G is the minimum cardinality among all dominating sets of G. In this paper, we obtain new (probabilistic) upper bounds for the domination number of a graph in terms of its order, minimum degree and maximum degree. These new bounds improve previous bounds given in Jafari Rad (2019) [15].

KW - Domination number

KW - Probabilistic bounds

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

U2 - 10.1016/j.disc.2025.114656

DO - 10.1016/j.disc.2025.114656

M3 - Article

AN - SCOPUS:105009418094

SN - 0012-365X

VL - 349

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

M1 - 114656

ER -

New probabilistic upper bounds on the domination number of a graph: II

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this