Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
11021706 | Journal of Combinatorial Theory, Series B | 2018 | 32 Pages |
Abstract
We conjecture that in fact all Moore graphs are extremal for the scaled number of independent sets in regular graphs of a given minimum girth, maximizing this quantity if their girth is even and minimizing if odd. The Heawood and Petersen graphs are instances of this conjecture, along with complete graphs, complete bipartite graphs, and cycles.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Guillem Perarnau, Will Perkins,