\((1, j)\)-set problem in graphs

DOI10.1016/j.disc.2016.04.008zbMath1339.05278arXiv1410.3091OpenAlexW1592312050MaRDI QIDQ294556

Arijit Ghosh, Arijit Bishnu, Subhabrata Paul, Kunal Dutta

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-completenesschordal graphprobabilistic methoddomination\((1, j)\)-set

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)

Related Items (6)

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] ⋮ On the parameterized complexity of \([1,j\)-domination problems] ⋮ On the Parameterized Complexity of [1,j-Domination Problems] ⋮ On \([j, k\)-sets in graphs]

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \([1,2\)-domination in graphs]
• Fair domination in graphs
• Dominating sets for split and bipartite graphs
• The weighted perfect domination problem
• \(k\)-tuple domination in graphs
• Treewidth. Computations and approximations
• Nearly perfect sets in graphs
• \([1,2\)-sets in graphs]
• A constructive proof of the general lovász local lemma
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• (Meta) Kernelization
• Quasiperfect domination in triangular lattices
• On the Concentration of the Domination Number of the Random Graph

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