New Probabilistic Upper Bounds on the Domination Number of a Graph

Nader Jafari Rad

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=116750
Date :  2019/08/16
Publish in :    Electronic Journal of Combinatorics

Link :  https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i3p28/7888
Keywords :,improvements,Probabilistic, -upper bound

Abstract :

---

A subset S of vertices of a graph G is a dominating set of G if every vertex inV(G)−S has a neighbor in S. The domination number γ(G) of G is the minimum cardinality of a dominating set of G. In this paper, we obtain new (probabilistic)upper bounds for the domination number of a graph, and improve previous bounds given by Arnautov (1974), Payan (1975), and Caro and Roditty (1985) for any graph, and Harant, Pruchnewski and Voigt (1999) for regular graphs