Some remarks on domination in cubic graphs
type: Item
instance of: scholarly article
title: Some remarks on domination in cubic graphs
zbMATH Open document ID: 0861.05034
DOI: 10.1016/0012-365X(94)00324-C
author: Bohdan Zelinka
published in: Discrete Mathematics
publication date: 1997-05-04T00:00:00Z
review text: Let \(G\) be a finite, undirected graph with no loops or multiple edges. The vertex set of a graph \(G\) is denoted by \(V(G)\). For a vertex \(x\) in \(V(G)\), \(N[x]\) denotes the set consisting of \(x\) and 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\Sigma=\{-1, 1\}\) such that \(\sum_{v\in N[x]}f(v)\geq 1\) for each \(x\in V(G)\). A minus dominating function \(f\) can be defined similar to above except that \(\Sigma=\{-1, 0, 1\}\). A majority dominating function \(f\) is a function \(f:V(G)\to\{-1, 1\}\) such that \(\sum_{v\in N[x]}f(v)\geq 1\) for at least \({|V(G)|\over 2}\) vertices of \(G\). The minimum of \(f(V(G))\) over all signed (minus, majority) dominating functions \(f\) of a graph \(G\) is called the signed (minus, majority) domination number of \(G\) and is denoted by \(\gamma_s(G)\) \((\gamma^{-}(G), \gamma_{\max}(G))\). The author studies these three types of domination numbers for the case in which \(G\) is a cubic graph. The author proves an upper bound for \(\gamma_s(G)\) and lower bounds for \(\gamma^-(G)\) and \(\gamma_{\max}(G)\), in terms of the order of the cubic graph \(G\).
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 943231
zbMATH Keywords: signed dominating function
zbMATH Keywords: minus dominating function
zbMATH Keywords: majority dominating function
zbMATH Keywords: domination number
zbMATH Keywords: cubic graph
zbMATH Keywords: bound
MaRDI profile type: Publication
cites work: Majority domination in graphs
cites work: Minus domination in graphs
cites work: Q4871151
cites work: Inequalities relating domination parameters in cubic graphs
cites work: Q4374702
full work available at URL: 0012-365x(94)00324-c
OpenAlex ID: W2021308184
Recommended article: Some more remarks on domination in cubic graphs
Recommended article: On domination in connected cubic graphs
Recommended article: Q3972021
Recommended article: A note on domination and minus domination numbers in cubic graphs
Recommended article: The domination parameters of cubic graphs
Recommended article: Total domination versus domination in cubic graphs
Recommended article: Domination and irredundance in cubic graphs
Recommended article: Domination in Cubic Graphs of Large Girth
Recommended article: A note on \(\alpha\)-total domination in cubic graphs
Recommended article: Domination and total domination in cubic graphs of large girth
description: scientific article; zbMATH DE number 943231