𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximal independent sets in graphs with at most one cycle

✍ Scribed by Min-Jen Jou; Gerard J. Chang

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
356 KB
Volume
79
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

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 but not necessarily connected are also given.

πŸ“œ SIMILAR VOLUMES

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

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

Generating cycles in graphs with at most
Generating cycles in graphs with at most one end
✍ Henning Bruhn πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 81 KB πŸ‘ 1 views

## Abstract Answering a question of Halin, we prove that in a 3‐connected graph with at most one end the cycle space is generated by induced non‐separating cycles. Β© 2003 Wiley Periodicals, Inc. J Graph Theory 42: 342–349, 2003

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