$R$-Total Domination on Convex Bipartite Graphs

Abstract

Let $\mathcal{P}=\{I,I_1+d,I_1+2d,\dots ,I_1+(\ell -1)d\}$, where $\ell ,d,I_1$ are fixed integers and $\ell ,d>0$. Suppose that $G=(V,E)$ is a graph and $R$ is a labeling function which assigns an integer $R(v)$ to each $v\in V$. An $R-totaldominatingfunction$ of $G$ is a function $f:V\to \mathcal{P}$ such that $\sum _{u\in N_G(v)}f(u)\ge R(v)$ for all vertices $v\in V$, where $N_G(v)=\{u\mid (u,v)\in E\}$. The $R-totaldominationproblem$ is to find an $R$-total dominating function $f$ of $G$ such that $\sum _{v\in V}f(v)$ is minimized. In this paper, we present a linear-time algorithm to solve the $R$-total domination problem on convex bipartite graphs. Our algorithm gives a unified approach to the $k$-total, signed total, and minus total domination problems for convex bipartite graphs.