The structure and maximum number of maximum independent sets in trees

✍ Scribed by Jennifer Zito

• Publisher: John Wiley and Sons
• Year: 1991
• Tongue: English
• Weight: 732 KB
• Volume: 15
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190150208

✦ Synopsis

A subset of vertices is a maximum independent set if no two of the vertices are joined by an edge and the subset has maximum cardinality. In this paper we answer a question posed by Herb Wilf. We show that the greatest number of maximum independent sets for a tree of n vertices is 2(n-3* for odd n > 1 and 1 + 2'"-** for. even n .

We give the families of trees on which these maxima are achieved.

Proving which trees are extremal depends upon the structure of maximum independent sets in trees. This structure is described in terms of adjacency rules between three types of vertices, those which are in all, no, or some maximum independent sets. We show that vertices that are in some but not all maximum independent sets of the tree are joined in pairs by the a-critical edges (edges whose removal increases the size of a maximum independent set). The number of maximum independent sets is shown to depend on the structure within the tree of the a-critical edges.

1. Introduction

All graphs we consider are undirected labeled graphs without loops or multiple edges. An independent set of vertices is a set of vertices no two of *This paper is based on a section of the author's Ph.D. dissertation completed under the supervision of H. S. Wilf at the University of Pennsylvania.