PC Seminar: The minimum number of maximal independent sets in twin-free graphs
- Date: 12 October 2023, 10:15–11:15
- Location: Ångström Laboratory, , Å64119
- Type: Seminar
- Lecturer: Stephan Wagner, Uppsala University
- Organiser: Matematiska institutionen
- Contact person: Tiffany Lo
Stephan Wagner holds a seminar with the title "The minimum number of maximal independent sets in twin-free graphs". Welcome to join!
Abstract: The problem of determining the maximum number of maximal independent sets in different graph classes dates back to a paper of Miller and Muller and a question of Erdős and Moser from the 1960s. The analogous problem for the minimum is trivial, but becomes significantly more interesting when restricted to twin-free graphs, where no two vertices have the same open neighbourhood. With this restriction, the minimum number of maximal independent sets turns out to be logarithmic in the number of vertices for arbitrary graphs, linear for bipartite graphs and exponential for trees.
Joint work with Stijn Cambie (Kortrijk).
This is a seminar in our seminar series on Probability and Combinatorics (PC).