| Title:
|
On the minus domination number of graphs (English) |
| Author:
|
Liu, Hailong |
| Author:
|
Sun, Liang |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
54 |
| Issue:
|
4 |
| Year:
|
2004 |
| Pages:
|
883-887 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
minus dominating function |
| Keyword:
|
minus domination number |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 1080.05523 |
| idMR:
|
MR2100001 |
| . |
| Date available:
|
2009-09-24T11:18:33Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127937 |
| . |
| Reference:
|
[1] J. A. Bondy and U. S. R. Murty: Graph Theory with Applications.Macmillan, New York, 1976. MR 0411988 |
| Reference:
|
[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. MR 1393310, 10.1016/0166-218X(95)00056-W |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[6] T. W. Haynes, S. T. Hedetniemi and P. J. Slater: Fundamentals of Domination in Graphs.Marcel Dekker, New York, 1998. MR 1605684 |
| Reference:
|
[7] J. Petersen: Die Theorie der regulären Graphs.Acta Math. 15 (1891), 193–220. MR 1554815, 10.1007/BF02392606 |
| Reference:
|
[8] W. T. Tutte: Connectivity in Graphs.University Press, Toronto, 1966. Zbl 0146.45603, MR 0210617 |
| . |
