## Abstract

Let G = (V, E) be a graph and let k ∈ Z^{+}. A minus total k-subdominating function (mTkSF) is a function f:V→ {-1, 0,1} such that for at least k vertices v of G, the sum of the function values of f in the open neighborhood of v is positive. The minus total k-subdomination number of G is the minimum value of f(V) over all mTkSF s f of G where f(V) denotes the sum of the function values assigned to the vertices under f. In this paper, we show that the associated decision problem is NP complete for bipartite graphs and also present cubic time algorithms to compute the minus total k-subdomination and minus k-subdomination numbers of a tree.

Original language | English |
---|---|

Pages (from-to) | 101-111 |

Number of pages | 11 |

Journal | Australasian Journal of Combinatorics |

Volume | 36 |

Publication status | Published - 2006 |

Externally published | Yes |

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics