Remarks on the minus (signed) total domination in graphs

Research output: Journal article publicationJournal articleAcademic researchpeer-review

24 Citations (Scopus)

Abstract

A function f : V (G) → { + 1, 0,- 1 } defined on the vertices of a graph G is a minus total dominating function if the sum of its function values over any open neighborhood is at least 1. The minus total domination number γt-(G) of G is the minimum weight of a minus total dominating function on G. By simply changing "{ + 1, 0,- 1 }" in the above definition to "{ + 1,- 1 }", we can define the signed total dominating function and the signed total domination number γts(G) of G. In this paper we present a sharp lower bound on the signed total domination number for a k-partite graph, which results in a short proof of a result due to Kang et al. on the minus total domination number for a k-partite graph. We also give sharp lower bounds on γtsand γt-for triangle-free graphs and characterize the extremal graphs achieving these bounds.
Original languageEnglish
Pages (from-to)3373-3380
Number of pages8
JournalDiscrete Mathematics
Volume308
Issue number15
DOIs
Publication statusPublished - 6 Aug 2008

Keywords

  • k-partite graph
  • Minus total domination
  • Signed total domination
  • Triangle-free graph

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Theoretical Computer Science

Cite this