On the number of minimal separators in graphs
On the number of minimal separators in graphs
复制标题
关于图中最小分隔符的数量
DOI：
10.1002/jgt.22179
复制
发表时间：
2015
影响因子：
0.9
通讯作者：
Simon Mackenzie
中科院分区：
文献类型：
--
作者：
Serge Gaspers;Simon Mackenzie
我们考虑了一个n阶图所能具有的最大极小分离子数。- 给出了这个数在O 1 + 52 n·n中的一个新的证明。证明了该数在ω（1.4457n）中，改进了Ω（3 n/3）<$ω（1.4422n）的最佳下界，并给出了图中潜在极大团数的一个改进下界.我们要强调的是，我们的证明是简短、简单和基本的。
Weconsider the largest number of minimal separators a graph on n vertices can have. –We give a new proof that this number is in O1+52n·n . –We prove that this number is in ω(1.4457n) , improving on the previous best lower bound of Ω(3n/3)⊆ω(1.4422n) .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.