论文标题
通过顶点覆盖参数参数的潜在最大集团的紧密界限
Tight Bounds for Potential Maximal Cliques Parameterized by Vertex Cover
论文作者
论文摘要
我们表明，$ n $顶点和尺寸$ k $的顶点盖的图最多具有$ 4^k + n $潜在的最大集团。我们还表明，对于每个正整数$ k $，都存在一个图形，上面有尺寸$ k $，$ o（k^2）$顶点的顶点盖，以及$ω（4^k）$潜在的最大集团。我们的结果扩展了Fomin，Liedloff，Montealegre和Todinca的结果[Algorithmica，80（4）：1146---1169，2018]，他们证明了$ poly（n）4^k $的上限，但在下部限制下是一个开放的问题。
We show that a graph with $n$ vertices and vertex cover of size $k$ has at most $4^k + n$ potential maximal cliques. We also show that for each positive integer $k$, there exists a graph with vertex cover of size $k$, $O(k^2)$ vertices, and $Ω(4^k)$ potential maximal cliques. Our results extend the results of Fomin, Liedloff, Montealegre, and Todinca [Algorithmica, 80(4):1146--1169, 2018], who proved an upper bound of $poly(n) 4^k$, but left the lower bound as an open problem.
