On the Number of Minimal Separators in Graphs

Abstract

We consider the largest number of minimal separators a graph on n vertices can have at most. We give a new proof that this number is in $O(((1+\sqrt{5})/2{)}^{n}n)$. We prove that this number is in $\ddot{I}‰(1.4521^n)$, improving on the previous best lower bound of $\hat{I}\text{c◯}(3^{n/3})\subseteq \ddot{I}‰(1.4422^n)$. This gives also an improved lower bound on the number of potential maximal cliques in a graph. We would like to emphasize that our proofs are short, simple, and elementary.

arXiv admin note: text overlap with arXiv:0909.5278 by other authors