Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
minus dominating function; minus domination number
minus dominating function; minus domination number
Summary:
Let $G = (V,E)$ be a simple graph. A $3$-valued function $f\:V(G)\rightarrow \lbrace -1,0,1\rbrace $ is said to be a minus dominating function if for every vertex $v\in V$, $f(N[v]) = \sum _{u\in N[v]}f(u)\ge 1$, where $N[v]$ is the closed neighborhood of $v$. The weight of a minus dominating function $f$ on $G$ is $f(V) = \sum _{v\in V}f(v)$. The minus domination number of a graph $G$, denoted by $\gamma ^-(G)$, equals the minimum weight of a minus dominating function on $G$. In this paper, the following two results are obtained. (1) If $G$ is a bipartite graph of order $n$, then \[ \gamma ^-(G)\ge 4\bigl (\sqrt{n + 1}-1\bigr )-n. \] (2) For any negative integer $k$ and any positive integer $m\ge 3$, there exists a graph $G$ with girth $m$ such that $\gamma ^-(G)\le k$. Therefore, two open problems about minus domination number are solved.
References:
[1] J. A. Bondy and U. S. R. Murty: Graph Theory with Applications. Macmillan, New York, 1976. MR 0411988
[2] J. E. Dunbar, W. Goddard, S. T. Hedetniemi, M. A. Henning and A. McRae: The algorithmic complexity of minus domination in graphs. Discrete Appl. Math. 68 (1996), 73–84. DOI 10.1016/0166-218X(95)00056-W | MR 1393310
[3] J. E. Dunbar, S. T. Hedetniemi, M. A. Henning and A. A. McRae: Minus domination in graphs. Discrete Math. 199 (1999), 35–47. MR 1675909
[4] J. E. Dunbar, S. T. Hedetniemi, M. A. Henning and A. A. McRae: Minus domination in regular graphs. Discrete Math. 49 (1996), 311–312. MR 1375119
[5] J. H. Hattingh, M. A. Henning and P. J. Slater: Three-valued neighborhood domination in graphs. Australas. J. Combin. 9 (1994), 233–242. MR 1271204
[6] T. W. Haynes, S. T. Hedetniemi and P. J. Slater: Fundamentals of Domination in Graphs. Marcel Dekker, New York, 1998. MR 1605684
[7] J. Petersen: Die Theorie der regulären Graphs. Acta Math. 15 (1891), 193–220. DOI 10.1007/BF02392606 | MR 1554815
[8] W. T. Tutte: Connectivity in Graphs. University Press, Toronto, 1966. MR 0210617 | Zbl 0146.45603
Search
Partner of
