𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An Extension of the Chvátal–Erdős Theorem: Counting the Number of Maximum Independent Sets

✍ Scribed by Chen, Guantao; Li, Yinkui; Ma, Haicheng; Wu, Tingzeng; Xiong, Liming

Book ID
125345619
Publisher
Springer Japan
Year
2014
Tongue
English
Weight
264 KB
Volume
31
Category
Article
ISSN
0911-0119

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

An extension of the Erdős–Neveu–Rényi th
An extension of the Erdős–Neveu–Rényi theorem with applications to order statistics
✍ M. Kaluszka; A. Okolewski 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 90 KB

The necessary and su cient conditions are given for some stochastic process to be an empirical distribution function from some exchangeable random variables. The result is applied to establish sharp lower and upper bounds for order statistics based on possibly dependent random variables.

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