𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Graphs Having Maximal Independent Sets of ExactlytDistinct Cardinalities

✍ Scribed by Bert L. Hartnell, Douglas F. Rall

Book ID
120788683
Publisher
Springer Japan
Year
2012
Tongue
English
Weight
164 KB
Volume
29
Category
Article
ISSN
0911-0119

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,

Maximal independent sets in graphs with
Maximal independent sets in graphs with at most one cycle
✍ Min-Jen Jou; Gerard J. Chang πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 356 KB

In this paper, we determine the largest number of maximal independent sets among all connected graphs of order n, which contain at most one cycle. We also characterize those extremal graphs achieving this maximum value. As a consequence, the corresponding results for graphs with at most one cycle bu