Denote the dominating number of a graph $G$ by $\gamma(G)$. I have found a number of upper bounds on $\gamma(G)$. For example, in Theorem 1.2.2 of Alon & Spencer's book, named "The Probabilistic Method", for a graph $G$ with minimal degree $d$, we have: $\gamma(G)\leq n\cdot\frac{1+ln(d+1)}{d+1}$. Unfortunately, this bound is not suitable for my work. I want to know if a better upper bound exists.
$\begingroup$
$\endgroup$
5
-
3$\begingroup$ This sounds too general to answer. What kind of bound would you like to have? $\endgroup$– SevaCommented Dec 23, 2017 at 20:10
-
$\begingroup$ I am looking for a bound which gives better results to me at least for regular graphs. I know that for some graphs, \gamma(G) is not unique, but I want to know do we have better bounds to limit our answers more or not? Just in comparison to above stated bound. $\endgroup$– SaharCommented Dec 25, 2017 at 13:29
-
$\begingroup$ Dear @Sahar: what do you mean by "for some graphs, \gamma(G) is not unique" in your comment at 2017-12-25 13:28:12Z ? This does not make sense. After all, the domination number $\gamma(\cdot)$ is a graph invariant, and in particular a function, so of course it has a unique value at every finite graph. Would you please clarify? $\endgroup$– Peter HeinigCommented Feb 23, 2018 at 19:35
-
$\begingroup$ Relevant: mathoverflow.net/questions/54621/… $\endgroup$– Peter HeinigCommented Feb 23, 2018 at 19:35
-
$\begingroup$ I think Sahar wanted to say a dominating set of the minimum size is not unique. $\endgroup$– Babak SamadiCommented Dec 7, 2018 at 2:12
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
It is quiet logically that this result is not very accurate. In this bound is used from minimum degree of vertices of the graphs. Minimum degree of the graph is a local property. With knowing the minimum degree of a graph, we don't have any information about other vertices or edges of a graph. For example, for all trees with $n$ vertices, we have $d=1$ and so this bound gives the same bound for all of them. Therefore, you must recognize the properties of your graph. Is your graph a bipartite graph, a chordal graph, a regular graph and etc.
-
$\begingroup$ Thank you for replying to my question. To clarify, I was first working on regular graphs. For example, I found that there are 60 nonisomorphic 5-regular graphs with n=10. I checked all of them and recognized that in each case, there exist 2 vertices which other vertices are connected to at least one of them. Hence for these graphs we have \gamma(G) = 2. Unfortunately, the above stated bound for them is about 4.6 which means that \gamma(G) can also be 3 or 4. In addition, it is difficult to prove that for G, \gamma(G) is 2. $\endgroup$– SaharCommented Dec 25, 2017 at 13:25
-
1$\begingroup$ I am looking for a bound which gives better results to me at least for regular graphs. I know that for some graphs, \gamma(G) is not unique, but I want to know do we have better bounds to limit our answers more or not? $\endgroup$– SaharCommented Dec 25, 2017 at 13:28
-
$\begingroup$ Dear @Sahar: what do you mean by "for some graphs, \gamma(G) is not unique" in your comment at 2017-12-25 13:28:12Z ? This does not make sense to me. After all, the domination number $\gamma(\cdot)$ is a graph invariant, and in particular a function, so of course it has a unique value at every finite graph. Would you please clarify? $\endgroup$ Commented Feb 23, 2018 at 19:27
-
$\begingroup$ Dear Sahar : This formula is constructed by probabilistic methods. $\endgroup$– srmusawiCommented Feb 25, 2018 at 8:29
-
$\begingroup$ Dear Sahar : This formula is constructed by probabilistic methods. Indeed, the value 4.6 is the average of the cardinality of all dominating sets of the graph, for example, The set of all vertices. In this average, the dominating sets with bigger cardinality appear more. While the minimum dominating sets appear once. $\endgroup$– srmusawiCommented Feb 25, 2018 at 8:54
$\begingroup$
$\endgroup$
As far as I know, $\gamma(G)\leq kn/(3k-1)$ is the most famous conjectured upper bound on the domination number of a graph $G$ with $\delta(G)\geq k$.
In the book
T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of domination in graphs, Marcel Dekker, New York, 1998.
the authors conjectured that $$\gamma(G)\leq kn/(3k-1),$$ for all graph $G$ with $\delta(G)\geq k$.
For $\delta(G)\geq7$, Caro and Rodity, in the paper
Y. Caro, Y. Roditty, A note on the $k$-domination number of a graph, Internat. J. Math. Sci. 13 (1990), 205--206.
gave a better upper bound. On the other hand, in the paper
H. Liu and L. Sun, On domination number of $4$-regular graphs, Czechoslovak Math. J. 54 (2004), 889--898.
the authors showed that the conjecture is true for $4$-regular graphs. Moreover, in the paper
Hua-Ming Xing, Liang Sun, and Xue-Gang Chen, Czechoslovak Math. J. 56 (2006), 1049--1061.
the authors showed that the conjecture is true for $5$-regular graphs. So, the problem is open for graphs with $\delta(G)=6$.
