Geodesic
On the minus domination number of graphs
Czechoslovak Mathematical Journal, Tome 54 (2004) no. 4, pp. 883-887
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C69
Keywords: minus dominating function; minus domination number 
@article{CMJ_2004_54_4_a4,
     author = {Liu, Hailong and Sun, Liang},
     title = {On the minus domination number of graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {883--887},
     year = {2004},
     volume = {54},
     number = {4},
     mrnumber = {2100001},
     zbl = {1080.05523},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2004_54_4_a4/}
}
TY  - JOUR
AU  - Liu, Hailong
AU  - Sun, Liang
TI  - On the minus domination number of graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2004
SP  - 883
EP  - 887
VL  - 54
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/CMJ_2004_54_4_a4/
LA  - en
ID  - CMJ_2004_54_4_a4
ER  - 
%0 Journal Article
%A Liu, Hailong
%A Sun, Liang
%T On the minus domination number of graphs
%J Czechoslovak Mathematical Journal
%D 2004
%P 883-887
%V 54
%N 4
%U http://geodesic.mathdoc.fr/item/CMJ_2004_54_4_a4/
%G en
%F CMJ_2004_54_4_a4
Liu, Hailong; Sun, Liang. On the minus domination number of graphs. Czechoslovak Mathematical Journal, Tome 54 (2004) no. 4, pp. 883-887. http://geodesic.mathdoc.fr/item/CMJ_2004_54_4_a4/

[1] J. A. Bondy and U. S. R. Murty: Graph Theory with Applications. Macmillan, New York, 1976. | MR

[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 | MR

[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

[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

[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

[6] T. W. Haynes, S. T. Hedetniemi and P. J. Slater: Fundamentals of Domination in Graphs. Marcel Dekker, New York, 1998. | MR

[7] J. Petersen: Die Theorie der regulären Graphs. Acta Math. 15 (1891), 193–220. | DOI | MR

[8] W. T. Tutte: Connectivity in Graphs. University Press, Toronto, 1966. | MR | Zbl