Article ID Journal Published Year Pages File Type
4650251 Discrete Mathematics 2008 5 Pages PDF
Abstract

A subset S of vertices of a graph G is independent if no two vertices in S are adjacent. In this paper we study maximal (with respect to set inclusion) independent sets in trees including the set of leaves. In particular the smallest and the largest number of these sets among n-vertex trees are determined characterizing corresponding trees. We define a local augmentation of trees that preserves the number of maximal independent sets including the set of leaves.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,