Geodesic
New probabilistic upper bounds on the domination number of a graph
Nader Jafari Rad1
1Shahed University
The electronic journal of combinatorics, Tome 26 (2019) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A subset $S$ of vertices of a graph $G$ is a dominating set of $G$ if every vertex in $V(G)-S$ has a neighbor in $S$. The domination number $\gamma(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.
DOI : 10.37236/8345
Classification : 05C69
Mots-clés : vertex-independence number, bipartite subgraph, star-decomposition, genus, planar graphs

Nader Jafari Rad  1

1 Shahed University 
@article{10_37236_8345,
     author = {Nader Jafari Rad},
     title = {New probabilistic upper bounds on the domination number of a graph},
     journal = {The electronic journal of combinatorics},
     year = {2019},
     volume = {26},
     number = {3},
     doi = {10.37236/8345},
     zbl = {1418.05104},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8345/}
}
TY  - JOUR
AU  - Nader Jafari Rad
TI  - New probabilistic upper bounds on the domination number of a graph
JO  - The electronic journal of combinatorics
PY  - 2019
VL  - 26
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8345/
DO  - 10.37236/8345
ID  - 10_37236_8345
ER  - 
%0 Journal Article
%A Nader Jafari Rad
%T New probabilistic upper bounds on the domination number of a graph
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/8345/
%R 10.37236/8345
%F 10_37236_8345
Nader Jafari Rad. New probabilistic upper bounds on the domination number of a graph. The electronic journal of combinatorics, Tome 26 (2019) no. 3. doi: 10.37236/8345

Cité par Sources :