Y. Tsunoda, Y. Oh, and Y. Fujiwara, "Probabilistic Upper Bound on the Domination Number," 50th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Florida, USA, March 2019.
Y. Tsunoda, Y. Oh, and Y. Fujiwara, "Probabilistic Upper Bound on the Domination Number," 50th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Florida, USA, March 2019.
Given a graph $G$ with vertex set $V$, a set $S\subseteq V$ of vertices in $G$ is a dominating set if for every vertex $v\in V\setminus S$, there exists a vertex $u\in S$ such that $v$ is adjacent to $u$. The domination number $\gamma(G)$ of $G$ is the cardinality of a minimum dominating set of $G$. Since the problem of determining the domination number is known to be NP-complete for an arbitrary graph, it is natural to find bounds on the domination number. In this talk, a probabilistic upper bound on $\gamma(G)$ of a graph $G$ with $n$ vertices, minimum degree $\delta$, and maximum degree $\Delta$ is proved. The derived bound is a modification of the well-known upper bound (Alon and Spencer, 1992) and indicates a new relationship between the domination number and independence number.
Slides from Yu Tsunoda's SEICCGTC2019 talk
The 50th Southeastern International Conference on Combinatorics, Graph Theory & Computing was held at Florida Atrantic University in Florida, USA, from March 4 to 8, 2019 [Conference website]. The travel was supported by Gradate School of Engineering, Chiba University.