Minus \(k\)-subdomination in graphs. II
type: Item
instance of: scholarly article
title: Minus \(k\)-subdomination in graphs. II
zbMATH Open document ID: 0876.05043
DOI: 10.1016/S0012-365X(96)00003-9
author: Johannes H. Hattingh
author: Elna Ungerer
published in: Discrete Mathematics
publication date: 1997-10-29T00:00:00Z
review text: \(N(v)\), the open neighbourhood of a vertex \(v\) in an undirected graph \(G=(V,E)\), is the set of vertices adjacent to \(v\); for \(S\subseteq V\), \(N(S)=\bigcup_{v\in S}N(v)\), the ``closed'' neighbourhood \(N[S]\) is \(N(V)\cup S\). For a positive integer \(k \leq |V|\), a function \(f:V\rightarrow \{-1,0,1\}\) is a \(k\)-subdominating function if \(f(N[v])\geq1\) for at least \(k\) vertices \(v\in V\), where, for any \(S\subseteq V\), \(f(S)\) is defined to be \(\sum_{v\in S}f(v)\). The \(k\)-subdomination number of \(G\), \(\gamma_{ks}^{-101}(G)\) is the minimum of \(f(V)\) over all \(k\)-subdominating functions. Theorem 3. If \(T\) is a tree of order \(n\geq 2\), and \(k\) is an integer such that \(1\leq k\leq n-1\), then \(\gamma_{ks}^{-101}(T)\geq k-n+2\). Moreover, this bound is best possible. Theorem 5. If \(k\) and \(n\) are integers such that \(1\leq k\leq n-1\), then \(\gamma_{ks}^{-101}(C_n)= \left\lceil\frac{n-2}3\right\rceil\) if \(k=n-1\) and (\(k\equiv 0\) or \(k\equiv 1\pmod{3}\)), and \(\gamma_{ks}^{-101}(C_n)= 2\left\lfloor\frac{2k+4}3\right\rfloor-n\) otherwise. The paper applies results of a paper ``Minus \(k\)-subdomination in graphs'' by J. Broere, J. E. Dunbar, and the first named author, and shown as ``submitted''.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1047084
zbMATH Keywords: neighbourhood
zbMATH Keywords: \(k\)-subdominating function
zbMATH Keywords: \(k\)-subdomination number
reviewed by: William G. Brown
MaRDI profile type: Publication
cites work: Minus \(k\)-subdomination in graphs
cites work: Majority domination in graphs
cites work: Q4374706
cites work: Minus domination in graphs
cites work: Q4871151
full work available at URL: s0012-365x(96)00003-9
OpenAlex ID: W2014823147
description: scientific article; zbMATH DE number 1047084