✦ LIBER ✦

Maximal independent sets in graphs with at most r cycles

✍ Scribed by Goh Chee Ying; Koh Khee Meng; Bruce E. Sagan; Vincent R. Vatter

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 127 KB
Volume: 53
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20185

No coin nor oath required. For personal study only.

✦ Synopsis

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 Periodicals, Inc. J Graph Theory 53: 270–282, 2006

📜 SIMILAR VOLUMES

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

Maximal matchings in graphs with large n

Maximal matchings in graphs with large neighborhoods of independent vertices

✍ I. Rinsma; C. H. C. Little; D. R. Woodall 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB

## Abstract We obtain lower bounds on the size of a maximum matching in a graph satisfying the condition |__N(X)__| ≥ __s__ for every independent set __X__ of __m__ vertices, thus generalizing results of Faudree, Gould, Jacobson, and Schelp for the case __m__ = 2.