Signed total domination in graphs.
type: Item
instance of: scholarly article
title: Signed total domination in graphs.
zbMATH Open document ID: 1036.05035
author: Michael A. Henning
published in: Discrete Mathematics
publication date: 2004-03-14T00:00:00Z
review text: The paper continues the study of the signed total domination in graphs which was started by the reviewer. Let \(G\) be a graph with vertex set \(V\). For each \(v\in V\) let \(N(v)\) be the open neighbourhood of \(v\) in \(G\), i.e. the set of all vertices adjacent to \(v\) in \(G\). If \(f\) is a mapping of \(V\) into a number set and \(S\subseteq V\), then \(f(S)= \sum_{X\in V} f(x)\). The sum \(w(f)= f(V)\) is the weight of \(f\). A function \(f: V\to \{-1,1\}\) is called a signed total dominating function on \(G\) (shortly STDF), if \(f(N(v))\geq 1\) for each \(v\in G\). It is minimal, if no \(g< f\) is a STDF. The minimum weight of an STDF on \(G\) is the signed total domination number \(\gamma^s_t(G)\) of \(G\). The maximum weight of a minimal STDF on \(G\) is the upper signed total domination number \(\Gamma^s_t(G)\) of \(G\). The paper presents bounds for these numbers in terms of the minimum degree \(\delta\) and the maximum degree \(\Delta\). Special attention is paid to regular graphs, trees and bipartite graphs. The problem of recognizing whether \(\gamma^s_t(H)\leq j\) for a given graph \(H\) and positive integer \(j\) is proved to be NP-complete.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 2055735
zbMATH Keywords: upper signed total domination number
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
full work available at URL: j.disc.2003.06.002
OpenAlex ID: W2057180123
cites work: Total domination in graphs
cites work: A characterisation of universal minimal total dominating functions in trees
cites work: Q4374706
cites work: Q4367785
cites work: Universal minimal total dominating functions in graphs
cites work: Total dominating functions in trees: Minimality and convexity
cites work: Minus domination in graphs
cites work: Q4871151
cites work: Signed domination in regular graphs
cites work: Q4487071
cites work: Q5284022
cites work: Signed domination in regular graphs and set-systems
cites work: Q4858149
cites work: Q4368728
cites work: Q4368729
cites work: Q4374702
cites work: Q4378623
cites work: Graphs with large total domination number
cites work: Inequalities relating domination parameters in cubic graphs
cites work: On the signed domination in graphs
cites work: Universal minimal total dominating functions of trees
cites work: Convexity of minimal total dominating functions in graphs
cites work: Some remarks on domination in cubic graphs
cites work: Signed Total Domination Nnumber of a Graph
cites work: A note on the lower bounds of signed domination number of a graph
DOI: 10.1016/J.DISC.2003.06.002
description: scientific article; zbMATH DE number 2055735