𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The number of maximal independent sets in a connected graph

✍ Scribed by Jerrold R. Griggs; Charles M. Grinstead; David R. Guichard

Publisher
Elsevier Science
Year
1988
Tongue
English
Weight
1021 KB
Volume
68
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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-8406451 ar:d by a Eugene Fellowship.

** We feel compelled to point out that we are continuing the alliterative tradition started b_v and Moser in this subject, and also that the authors are all graduates of Pomona College, classes of 1973, 1974 and 1975 respectively.

πŸ“œ 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

Independent sets of maximal size in tens
Independent sets of maximal size in tensor powers of vertex-transitive graphs
✍ Cheng Yeaw Ku; Benjamin B. McMillan πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 97 KB πŸ‘ 2 views

## Abstract Let __G__ be a connected, nonbipartite vertex‐transitive graph. We prove that if the only independent sets of maximal cardinality in the tensor product __G__ Γ— __G__ are the preimages of the independent sets of maximal cardinality in __G__ under projections, then the same holds for all