
arXiv: 1511.09262
An independent $[1,k]$-set $S$ in a graph $G$ is a dominating set which is independent and such that every vertex not in $S$ has at most $k$ neighbors in it. The existence of such sets is not guaranteed in every graph and trees having an independent $[1,k]$-set have been characterized. In this paper we solve some problems previously posed by other authors about independent $[1,2]$-sets. We provide a necessary condition for a graph to have an independent $[1,2]$-set, in terms of spanning trees and we prove that this condition is also sufficient for cactus graphs. We follow the concept of excellent tree and characterize the family of trees such that any vertex belong to some independent $[1,2]$-set. Finally we describe a linear algorithm to decide whether a tree has an independent $[1,2]$-set. Such algorithm can be easily modified to obtain the cardinality of the smallest independent $[1,2]$-set of a tree.
13 pages, 6 figures
independence, spanning trees, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), 05C69, 05c69, excellent trees, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics, domination
independence, spanning trees, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), 05C69, 05c69, excellent trees, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics, domination
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
