On the number of minimal separators in graphs
Serge Gaspers, Simon Mackenzie · Journal of Graph Theory · 2017
Abstract Weconsider the largest number of minimal separators a graph on n vertices can have. We give a new proof that this number is in . We prove that this number is in , improving on the previous best lower bound of . 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.