Upper minus domination in regular graphs
type: Item
instance of: scholarly article
title: Upper minus domination in regular graphs
zbMATH Open document ID: 0948.05039
DOI: 10.1016/S0012-365X(99)00245-9
published in: Discrete Mathematics
publication date: 2000-11-19T00:00:00Z
review text: A minus dominating function of a graph \(G\) is a function \(f: V(G)\to \{-1,0,1\}\) such that the sum of its values over the closed neighbourhood \(N[v]\) of any vertex \(v\) of \(G\) is at least \(1\). (The closed neighbourhood \(N[v]\) is the set consisting of \(v\) and of all vertices adjacent to \(v\) in \(G\).) A minus dominating function \(f\) of \(G\) is minimal, if for any minus dominating function \(g\) of \(G\) the inequalities \(g(x)\leq f(x)\) for all \(x\in V(G)\) imply \(g= f\). The symbol \(f(V(G))\) denotes \(\sum_{x\in V(G)} f(x)\). The maximum value of \(f(V(G))\) taken over all minimal minus dominating functions \(f\) of \(G\) is the upper minus domination number \(\Gamma^-(G)\) of \(G\). The main result states that if \(G\) has \(n\) vertices and is regular of degree \(r\), then \(\Gamma^-(G)\leq (r+ 1)n/(r+ 3)\) for even \(r\) and \(\Gamma^-(G)\leq (r^2+ 1)n/(r+ 1)\) for odd \(r\). At the end, \(\Gamma^-(G)\) is related to the upper signed domination number \(\Gamma_s(G)\), which is a similar numerical invariant of a graph.
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1462323
zbMATH Keywords: minus dominating function
zbMATH Keywords: upper minus domination number
zbMATH Keywords: upper signed domination number
author: Liying Kang
author: Mao-Cheng Cai
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00245-9
OpenAlex ID: W1975586942
description: scientific article; zbMATH DE number 1462323