On the minus domination number of graphs

Liu, Hailong ; Sun, Liang

Czechoslovak Mathematical Journal, Tome 54 (2004) no. 4, pp. 883-887

Résumé

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.

Détail

Classification : 05C69
Keywords: minus dominating function; minus domination number