(1, j)-set problem in graphs

DOI10.1016/J.DISC.2016.04.008MaRDI QIDQ294556zbMATH OpenOpenAlexFDO

Authors Arijit Bishnu, Kunal Dutta, Arijit Ghosh, S. Paul

Publication date 16 June 2016

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.3091

zbMATH Keywords

NP-completenessdominationprobabilistic method\((1, j)\)-setchordal graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: A subset $DsubseteqV$of a graph $G=(V,E)$ is a $(1,j)$-set if every vertex $vinVsetminusD$ is adjacent to at least $1$ but not more than $j$ vertices in D. The cardinality of a minimum $(1,j)$-set of $G$, denoted as $gamm{a}_{(1,j)}(G)$, is called the $(1,j)$-domination number of $G$. Given a graph $G=(V,E)$ and an integer $k$, the decision version of the $(1,j)$-set problem is to decide whether $G$ has a $(1,j)$-set of cardinality at most $k$. In this paper, we first obtain an upper bound on $gamm{a}_{(1,j)}(G)$ using probabilistic methods, for bounded minimum and maximum degree graphs. Our bound is constructive, by the randomized algorithm of Moser and Tardos [MT10], We also show that the $(1,j)$- set problem is NP-complete for chordal graphs. Finally, we design two algorithms for finding $gamm{a}_{(1,j)}(G)$ of a tree and a split graph, for any fixed $j$, which answers an open question posed in [CHHM13].

Recommendations

• On \([j, k]\)-sets in graphs
• Algorithmic aspects of the \(k\)-domination problem in graphs
• On the parameterized complexity of \([1,j]\)-domination problems
• Independent \([1,k]\)-sets in graphs
• \((1,2)\)-domination in graphs

Cites work

• scientific article; zbMATH DE number 436064 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 975419 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• (Meta) Kernelization
• A constructive proof of the general Lovász local lemma
• Dominating sets for split and bipartite graphs
• Fair domination in graphs
• Graphs on surfaces
• Nearly perfect sets in graphs
• On the concentration of the domination number of the random graph
• Quasiperfect domination in triangular lattices
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The weighted perfect domination problem
• Treewidth. Computations and approximations
• \([1,2]\)-domination in graphs
• \([1,2]\)-sets in graphs
• \(k\)-tuple domination in graphs

Cited in

(7)

• When an optimal dominating set with given constraints exists
• A note on bipartite graphs whose \([1,k]\)-domination number equal to their number of vertices
• \([1,k]\)-domination number of lexicographic products of graphs
• The Set Connector Problem in Graphs
• On the parameterized complexity of \([1,j]\)-domination problems
• On the Parameterized Complexity of [1,j]-Domination Problems
• On \([j, k]\)-sets in graphs

This page was built for publication: \((1, j)\)-set problem in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294556)