(1, j)-set problem in graphs

DOI10.1016/J.DISC.2016.04.008zbMATH Open1339.05278arXiv1410.3091OpenAlexW1592312050MaRDI QIDQ294556FDOQ294556

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

Publication date: 16 June 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

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].

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

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

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)

Cites Work

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

Cited In (7)

• \([1,k]\)-domination number of lexicographic products of graphs
• On the parameterized complexity of \([1,j]\)-domination problems
• When an optimal dominating set with given constraints exists
• The Set Connector Problem in Graphs
• A note on bipartite graphs whose \([1,k]\)-domination number equal to their number of vertices
• 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)