✦ LIBER ✦

Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices

✍ Scribed by Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Leonid Khachiyan

Publisher: Springer-Verlag
Year: 2003
Tongue: English
Weight: 191 KB
Volume: 98
Category: Article
ISSN: 0025-5610
DOI: 10.1007/s10107-003-0408-4

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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 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,

On independence numbers of distance grap

On independence numbers of distance graphs with vertices in {-1,0,1}n: estimates, conjectures, and applications to the Nelson–Erdős–Hadwiger problem and the Borsuk problem

✍ A. E. Guterman; V. K. Lyubimov; A. M. Raigorodskii; S. A. Usachev 📂 Article 📅 2010 🏛 Springer US 🌐 English ⚖ 274 KB