✦ LIBER ✦

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

✍ Scribed by Bruce E. Sagan; Vincent R. Vatter

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

No coin nor oath required. For personal study only.

✦ Synopsis

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 formula for c(n,r) when r is large relative to n, while a theorem of Goh, Koh, Sagan, and Vatter does the same when r is small relative to n. We complete the determination of c(n,r) for all n and r and characterize the extremal graphs. Problems for maximum independent sets are also completely resolved. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 283–314, 2006

📜 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 👁 1 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

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.

Very rapidly mixing Markov chains for 2Δ

Very rapidly mixing Markov chains for 2Δ-colorings and for independent sets in a graph with maximum degree 4

✍ Michael Molloy 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB 👁 1 views

We introduce a new technique for analyzing the mixing rate of Markov chains. We use it to prove that the Glauber dynamics on 2 -colorings of a graph with maximum degree mixes in O n log n time. We prove the same mixing rate for the Insert/Delete/Drag chain of Dyer and Greenhill (Random Structures A