vertex cover
- 2022/09 Tran2022
- page 19 : vertex cover $k$ upper bounds twin-cover number by $\mathcal O(k)$ – By definition
- page 19 : bounded complete does not imply bounded vertex cover – Note that a clique of size $n$ has … a vertex cover number of $n-1$
- 2012 GanianTwinCover2012
- page 263 : bounded twin-cover number does not imply bounded vertex cover – The vertex cover of graphs of bounded twin-cover may be arbitrarily large.
- https://en.wikipedia.org/wiki/Vertex_cover
- vertex cover – … set of vertices that includes at least one endpoint of every edge of the graph.
- unknown
- vertex cover $k$ upper bounds maximum matching by $\mathcal O(k)$
- vertex cover $k$ upper bounds neighborhood diversity by $2^{\mathcal O(k)}$
- vertex cover $k$ upper bounds twin-cover number by $\mathcal O(k)$ – By definition
- vertex cover is equal to distance to edgeless
- edgeless upper bounds vertex cover by a constant
- SchroderThesis
- page 15 : bounded vertex cover does not imply bounded domination number – Proposition 3.5
- page 24 : bounded vertex cover does not imply bounded genus – Proposition 3.18
- page 24 : bounded vertex cover does not imply bounded maximum degree – Proposition 3.19
- page 24 : bounded vertex cover does not imply bounded bisection bandwidth – Proposition 3.20