On \([j, k]\)-sets in graphs
type: Item
instance of: scholarly article
title: On \([j, k]\)-sets in graphs
zbMATH Open document ID: 1506.05164
author: Mohamed Zemir
author: Ahmed Bouchou
author: Mustapha Chellali
published in: Bulletin of the Malaysian Mathematical Sciences Society. Second Series
publication date: 2022-10-31T00:00:00Z
review text: For postive integers \(j\) and \(k\) with \(j\leq k\), a vertex subset \(S\) of a graph \(G\) is called a \([j,k]\)-set if every vertex in \(V(G)\setminus S\) is adjacent at least \(j\) elements in \(S\) but no more than \(k\) elements in \(S\). The \([j,k]\)-domination number \(\gamma_{[j,k]}(G)\) is the minimum cardinality of a \([j,k]\)-set in \(G\). The special cases when \(j=1\) and \(k=2\), and \(j=1\) were extensively studied. In this paper, the authors show that the decision problem is NP-complete whether or not there exists a \([j,k]\)-set of cardinality at most \(p\) in a graph \(G\) with at least \(p\) vertices. In addition, some sufficient conditions for which a graph has \(\gamma_{[j,k]}(G)\in\{n-1, n\}\) are presented.
reviewed by: Baoyindureng Wu
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 7610168
zbMATH Keywords: \([j, k]\)-sets
zbMATH Keywords: \([j, k]\)-domination number
MaRDI profile type: Publication
full work available at URL: s40840-022-01376-z
OpenAlex ID: W4294740957
cites work: [1,2]-Domination in generalized Petersen graphs
cites work: \((1, j)\)-set problem in graphs
cites work: Q3001198
cites work: Independent \([1,k]\)-sets in graphs
cites work: \([1,2]\)-sets in graphs
cites work: Q3691778
cites work: \([1,k]\)-domination number of lexicographic products of graphs
cites work: Weighted efficient domination problem on some perfect graphs
cites work: On the parameterized complexity of \([1,j]\)-domination problems
cites work: \([1,2]\)-domination in graphs
cites work: The weighted perfect domination problem
DOI: 10.1007/S40840-022-01376-Z
description: scientific article; zbMATH DE number 7610168