Signed domination in regular graphs
type: Item
instance of: scholarly article
title: Signed domination in regular graphs
zbMATH Open document ID: 0861.05033
DOI: 10.1016/0012-365X(96)00026-X
published in: Discrete Mathematics
publication date: 1997-05-04T00:00:00Z
review text: Let \(G\) be a finite, undirected graph without loops or multiple edges. For a vertex \(x\) in \(V(G)\), \(N[x]\) denotes the set consisting of \(x\) and of all vertices adjacent to \(x\). If \(f\) is a function which assigns real numbers to vertices of a graph \(G\) and \(S\subseteq V(G)\), then \(f(S)\) is defined as \(\sum_{x\in S}f(x)\). A signed dominating function \(f\) of a graph \(G\) is defined as a function \(f:V(G)\to\{-1, 1\}\) such that \(\sum_{v\in N[x]}f(v)\geq 1\) for each \(x\in V(G)\). A signed dominating function \(g\) is a minimal signed dominating function if every signed dominating function \(h\) satisfying \(h(v)\leq g(v)\) for every \(v\in V\), is equal to \(g\). The signed domination number of \(G\) is defined as \(\gamma_s(G)=\text{min}\{g(V)\mid g\) a signed dominating function\}. Define \(\Gamma_s(G)=\text{max}\{g(V)\mid g\) a minimal signed dominating function\}. The author shows that if \(G\) is a \(k\)-regular graph, \(k\geq 1\), of order \(n\), then \(\Gamma_s(G)\leq n(k+1)/(k+3)\) if \(k\) is even and \(\Gamma_s(G)\leq n(k+1)^2/(k^2+4k-1)\) if \(k\) is odd. These bounds are sharp and the graphs realizing the equality are described. He also shows that \(\gamma_s\leq n-2\lceil{n\over 8}\rceil\leq {3n\over 4}\) holds for any connected cubic graph other than the Petersen graph.
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 943236
zbMATH Keywords: regular graph
zbMATH Keywords: signed dominating function
zbMATH Keywords: signed domination number
zbMATH Keywords: bounds
zbMATH Keywords: cubic graph
author: Odile Favaron
MaRDI profile type: Publication
cites work: Independence, clique size and maximum degree
cites work: Q4374702
cites work: Inequalities relating domination parameters in cubic graphs
cites work: Some remarks on domination in cubic graphs
full work available at URL: 0012-365x(96)00026-x
OpenAlex ID: W2098828190
description: scientific article; zbMATH DE number 943236