[1,2]-sets and [1,2]-total sets in trees with algorithms

DOI10.1016/J.DAM.2015.06.014zbMATH Open1327.05258arXiv1706.05248OpenAlexW807791927MaRDI QIDQ897596FDOQ897596

Authors: Amir Kafshdar Goharshady, M. R. Hooshmandasl, Mohsen Alambardar Meybodi 

Publication date: 7 December 2015

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

Abstract: A set $SsubseteqV$ of the graph $G=(V,E)$ is called a $[1,2]$-set of $G$ if any vertex which is not in $S$ has at least one but no more than two neighbors in $S$. A set $SsubseteqV$ is called a $[1,2]$-total set of $G$ if any vertex of $G$, no matter in $S$ or not, is adjacent to at least one but not more than two vertices in $S$. In this paper we introduce a linear algorithm for finding the cardinality of the smallest $[1,2]$-sets and $[1,2]$-total sets of a tree and extend it to a more generalized version for $[i,j]$-sets, a generalization of $[1,2]$-sets. This answers one of the open problems proposed in [5]. Then since not all trees have $[1,2]$-total sets, we devise a recursive method for generating all the trees that do have such sets. This method also constructs every $[1,2]$-total set of each tree that it generates.

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

Recommendations

• On independent \([1, 2]\)-sets in trees
• On \([1,2]\)-domination in trees
• Set-sized \((1,3)\)-domination for trees
• Algorithm and complexity of the two disjoint connected dominating sets problem on trees
• Tree-representation of set families and applications to combinatorial decompositions
• On the number of dominating sets in some classes of trees
• Efficient sets in partial \(k\)-trees
• An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees
• An O\((n^{1.75})\) algorithm for \(L(2,1)\)-labeling of trees
• Trees with extremal numbers of \(k\)-dominating sets

zbMATH Keywords

dominating setstotal dominating sets\([1,2\)-sets]

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Total domination in graphs
• Total domination in graphs
• On approximating the minimum independent dominating set
• Rainbow domination in graphs
• On domination and independent domination numbers of a graph
• On the mixed domination problem in graphs
• \([1,2]\)-sets in graphs
• \([1,2]\)-domination in graphs
• The algorithmic complexity of mixed domination in graphs
• The domination number of Cartesian product of two directed paths
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hardness results and approximation algorithms for (weighted) paired-domination in graphs
• Independent \([1,k]\)-sets in graphs
• Minimum independent dominating sets of random cubic graphs
• Complexity of distance paired-domination problem in graphs

Cited In (8)

• \([1,k]\)-domination number of lexicographic products of graphs
• On the parameterized complexity of \([1,j]\)-domination problems
• An explicit construction of optimal dominating and [1, 2]–dominating sets in grid
• When an optimal dominating set with given constraints exists
• Efficient interprocedural data-flow analysis using treedepth and treewidth
• 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 independent \([1, 2]\)-sets in trees

This page was built for publication: \([1,2]\)-sets and \([1,2]\)-total sets in trees with algorithms

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