Upper minus total domination in small-degree regular graphs

详细信息    查看全文

• 作者：Hong Yan ; Xiaoqi Yang ; Erfang Shan
• 关键词：Minus total domination ; Regular graph ; Bounds
• 刊名：Discrete Mathematics
• 出版年：2007
• 出版时间：6 October 2007
• 年：2007
• 卷：307
• 期：21
• 页码：2453-2463
• 全文大小：266 K

文摘

A function f:V(G)→{-1,0,1} defined on the vertices of a graph G is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. An MTDF f is minimal if there does not exist an MTDF g:V(G)→{-1,0,1}, f≠g, for which g(v)f(v) for every vV(G). The weight of an MTDF is the sum of its function values over all vertices. The minus total domination number of G is the minimum weight of an MTDF on G, while the upper minus domination number of G is the maximum weight of a minimal MTDF on G. In this paper we present upper bounds on the upper minus total domination number of a cubic graph and a 4-regular graph and characterize the regular graphs attaining these upper bounds.