Advanced Search

A three-valued function $fV\to \{-1,0,1\}$ defined on the vertices of a graph $G=(V,E)$ is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. That is, for every $v\in V$, $f\left(N\right(v\left)\right)\ge 1$, where $N\left(v\right)$ consists of every vertex adjacent to $v$. The weight of an MTDF is $f\left(V\right)=\sum f\left(v\right)$, over all vertices $v\in V$. The minus total domination number of a graph $G$, denoted ${\gamma }_t^{-}\left(G\right)$, equals the minimum weight of an MTDF of $G$. In this paper, we discuss some properties of minus total domination on a graph $G$ and obtain...

The signed distance-$k$-domination number of a graph is a certain variant of the signed domination number. If $v$ is a vertex of a graph $G$, the open $k$-neighborhood of $v$, denoted by $N_k\left(v\right)$, is the set $N_k\left(v\right)=\{u\mid u\ne v$ and $d(u,v)\le k\}$. $N_k\left[v\right]=N_k\left(v\right)\cup \left\{v\right\}$ is the closed $k$-neighborhood of $v$. A function $fV\to \{-1,1\}$ is a signed distance-$k$-dominating function of $G$, if for every vertex $v\in V$, $f\left(N_k\left[v\right]\right)={\sum }_{u\in N_k\left[v\right]}f\left(u\right)\ge 1$. The signed distance-$k$-domination number, denoted by ${\gamma }_{k,s}\left(G\right)$, is the minimum weight of a signed distance-$k$-dominating function on $G$. The values of ${\gamma }_{2,s}\left(G\right)$ are found for graphs with small diameter,...

We initiate the study of signed majority total domination in graphs. Let $G=(V,E)$ be a simple graph. For any real valued function $fV\to ℝ$ and $S\subseteq V$, let $f\left(S\right)={\sum }_{v\in S}f\left(v\right)$. A signed majority total dominating function is a function $fV\to \{-1,1\}$ such that $f\left(N\right(v\left)\right)\ge 1$ for at least a half of the vertices $v\in V$. The signed majority total domination number of a graph $G$ is ${\gamma }_{\mathrm{m}aj}^{\mathrm{t}}\left(G\right)=min\{f\left(V\right)\mid f$ is a signed majority total dominating function on $G\}$. We research some properties of the signed majority total domination number of a graph $G$ and obtain a few lower bounds of ${\gamma }_{\mathrm{m}aj}^{\mathrm{t}}\left(G\right)$.

Let $G=(V,E)$ be a simple graph. A subset $S\subseteq V$ is a dominating set of $G$, if for any vertex $u\in V-S$, there exists a vertex $v\in S$ such that $uv\in E$. The domination number, denoted by $\gamma \left(G\right)$, is the minimum cardinality of a dominating set. In this paper we will prove that if $G$ is a 5-regular graph, then $\gamma \left(G\right)\le \frac{5}{14}n$.

The independent domination number $i\left(G\right)$ (independent number $\beta \left(G\right)$) is the minimum (maximum) cardinality among all maximal independent sets of $G$. Haviland (1995) conjectured that any connected regular graph $G$ of order $n$ and degree $\delta \le \frac{1}{2}n$ satisfies $i\left(G\right)\le \lceil \frac{2n}{3\delta }\rceil \frac{1}{2}\delta$. For $1\le k\le l\le m$, the subset graph $S_m(k,l)$ is the bipartite graph whose vertices are the $k$- and $l$-subsets of an $m$ element ground set where two vertices are adjacent if and only if one subset is contained in the other. In this paper, we give a sharp upper bound for $i\left(S_m(k,l)\right)$ and prove that...