𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximal independent sets in caterpillar graphs

✍ Scribed by Carmen Ortiz; Mónica Villanueva

Book ID
113564715
Publisher
Elsevier Science
Year
2012
Tongue
English
Weight
520 KB
Volume
160
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Maximal independent sets in bipartite gr
Maximal independent sets in bipartite graphs
✍ Jiuqiang Liu 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 458 KB 👁 1 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.__ In this paper, we determine the maximum number of maximal independent sets among all bipartite graphs of order __n__ and the extremal graphs as well as

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

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

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