On independent [1, 2]-sets in trees

DOI10.7151/DMGT.2029MaRDI QIDQ1649903zbMATH OpenOpenAlexFDO

Authors Sahar A. Aleid, M. L. Puertas, Jose Cáceres

Publication date 29 June 2018

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

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

zbMATH Keywords

dominationexcellent treesindependencespanning trees

Mathematics Subject Classification ID

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

Abstract: 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.

Recommendations

• Independent \([1,k]\)-sets in graphs
• Independent [1,2]-number versus independent domination number
• Independent (k + 1)-domination in k-trees
• \([1,2]\)-sets and \([1,2]\)-total sets in trees with algorithms
• Trees with two disjoint minimum independent dominating sets

Cites work

• R -Domination in Graphs
• \([1,2]\)-sets in graphs
• A characterization of \(i\)-excellent trees
• A linear algorithm for the domination number of a tree
• Edge Dominating Sets in Graphs
• Graphs \& digraphs
• scientific article; zbMATH DE number 3648727 (Why is no real title available?)
• scientific article; zbMATH DE number 3674114 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1744072 (Why is no real title available?)
• Independent \([1,k]\)-sets in graphs
• On the Algorithmic Complexity of Total Domination
• Optimum domination in weighted trees
• Restrained domination excellent trees.
• Total domination excellent trees

Cited in

(13)

• An independent dominating set in the complement of a minimum dominating set of a tree
• Irredundant and perfect neighbourhood sets in trees
• A characterization of \(i\)-excellent trees
• Invariant subsets of scattered trees and the tree alternative property of Bonato and Tardif
• A note on the number of matchings and independent sets in trees
• On the existence and the number of independent (1,2)-dominating sets in the \(G\)-join of graphs
• On S₀-free forests with man independent sets
• A Note on Independent Sets in Trees
• On generalized independent subsets of trees
• Independent [1,2]-number versus independent domination number
• Independent (k + 1)-domination in k-trees
• \([1,2]\)-sets and \([1,2]\)-total sets in trees with algorithms
• On the number of independent sets in a tree

This page was built for publication: On independent \([1, 2]\)-sets in trees

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