𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The number of maximal independent sets of (k+ 1)-valent trees

✍ Scribed by Junho Song; Heewon Han; Changwoo Lee

Publisher
Springer-Verlag
Year
2006
Tongue
English
Weight
191 KB
Volume
21
Category
Article
ISSN
1598-5865

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The number of maximal independent sets i
The number of maximal independent sets in connected graphs
✍ ZoltΓ‘n FΓΌredi πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 286 KB πŸ‘ 2 views

Generalizing a theorem of Moon and Moser. we determine the maximum number of maximal independent sets in a connected graph on n vertices for n sufficiently large, e.g., n > 50. = I .32. . .). Example 1.2. Let b, = i(C,), where C,z denotes the circuit of length n. Then b, = 3, 6, = 2, b, = 5, and b,

Constraints on the number of maximal ind
Constraints on the number of maximal independent sets in graphs
✍ Jiuqiang Liu πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 387 KB πŸ‘ 2 views

## Abstract A maximal independent set of a graph __G__ is an independent set that is not contained properly in any other independent set of __G__. Let __i(G)__ denote the number of maximal independent sets of __G__. Here, we prove two conjectures, suggested by P. ErdΓΆs, that the maximum number of m

The number of maximal independent sets i
The number of maximal independent sets in a connected graph
✍ Jerrold R. Griggs; Charles M. Grinstead; David R. Guichard πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 1021 KB

We determine the maximum on n vertices can have, and we a question of Wilf. number of maximal independent sets which a connected graph completely characterize the extremal graphs, thereby answering \* Partially supported by NSF grant number DIMS-8401281. t Partially supported by NSF grant number D S

The structure and maximum number of maxi
The structure and maximum number of maximum independent sets in trees
✍ Jennifer Zito πŸ“‚ Article πŸ“… 1991 πŸ› John Wiley and Sons 🌐 English βš– 732 KB

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

Maximizing the number of independent sub
Maximizing the number of independent subsets over trees with bounded degree
✍ Clemens Heuberger; Stephan G Wagner πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 208 KB πŸ‘ 1 views

## Abstract The number of independent vertex subsets is a graph parameter that is, apart from its purely mathematical importance, of interest in mathematical chemistry. In particular, the problem of maximizing or minimizing the number of independent vertex subsets within a given class of graphs has