Remarks on the minus (signed) total domination in graphs

详细信息    查看全文

• 作者：Erfang Shan ; T.C.E. Cheng
• 关键词：Minus total domination ; Signed total domination ; k-partite graph ; Triangle-free graph
• 刊名：Discrete Mathematics
• 出版年：2008
• 出版时间：6 August 2008
• 年：2008
• 卷：308
• 期：15
• 页码：3373-3380
• 全文大小：298 K

文摘

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 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 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 and for triangle-free graphs and characterize the extremal graphs achieving these bounds.