Jinyoung Park, Rutgers University

Abstract

For a given graph G, a subset A of V(G) is independent if no two vertices in A are adjacent. Some time ago, Erdos and Moser asked: what’s the maximum possible number of maximal independent sets in a graph G with n vertices. In this talk we will investigate the answer to this question, and some other related questions.