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

A set S⊆V 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 S′⊆V 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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2016-01, Vol.198, p.136-146
Main Authors: Goharshady, A.K., Hooshmandasl, M.R., Alambardar Meybodi, M.
Format: Article
Language:English
Subjects:
[formula omitted]-sets
Dominating sets
Mathematics
Total dominating sets
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A set S⊆V 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 S′⊆V 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 Chellali et al. (2013). 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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2015.06.014