✦ LIBER ✦

The second largest number of maximal independent sets in connected graphs with at most one cycle

✍ Scribed by Min-Jen Jou

Book ID: 118801970
Publisher: Springer US
Year: 2011
Tongue: English
Weight: 420 KB
Volume: 24
Category: Article
ISSN: 1382-6905
DOI: 10.1007/s10878-011-9376-4

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

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 r cycles

✍ Goh Chee Ying; Koh Khee Meng; Bruce E. Sagan; Vincent R. Vatter 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 2 views

## Abstract We find the maximum number of maximal independent sets in two families of graphs. The first family consists of all graphs with __n__ vertices and at most __r__ cycles. The second family is all graphs of the first family which are connected and satisfy __n__ ≥ 3__r__. © 2006 Wiley Period

Trees with the second largest number of

Trees with the second largest number of maximal independent sets

✍ Min-Jen Jou; Jenq-Jong Lin 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 508 KB

Maximal and maximum independent sets in

Maximal and maximum independent sets in graphs with at most r cycles

✍ Bruce E. Sagan; Vincent R. Vatter 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 236 KB 👁 2 views

## Abstract Let __m__(__G__) denote the number of maximal independent sets of vertices in a graph __G__ and let __c__(__n__,__r__) be the maximum value of __m__(__G__) over all connected graphs with __n__ vertices and at most __r__ cycles. A theorem of Griggs, Grinstead, and Guichard gives a formul

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