Some problems based on the relative sizes of the maximal independent sets in a graph

Dr. Rommel Barbosa

Instituto de Informatica--UFG
Goiania, Brazil

April 4, 2008
219 Shelby Center
3:00 PM (Refreshments at 2:30)

Abstract

A graph G is well-covered if every maximal independent set of vertices in G has the same cardinality. A graph G is a Z_m-well-covered graph if |I₁| ≡ |I₂| (mod m) for all maximal independent sets I₁ and I₂ in V(G). The recognition problem of Z_m-well-covered graphs is a co-NP-complete problem. A graph G belongs to class M(t) if G has exactly t different sizes of maximal independent sets. A graph belongs to class I(t) if Ghas exactly t different sizes of maximal independent sets with sizes r, r + 1, ..., r + (t − 1), for some r ∈ N. Here we present some properties and open problems for graphs in these classes.