vertex cover

• Tran2022
  • page 18 : vertex cover upper bounds twin-cover number by a linear function – By definition
  • page 18 : graph class complete has unbounded vertex cover – Note that a clique of size $n$ has … a vertex cover number of $n-1$
  • page 23 : vertex cover upper bounds neighborhood diversity by an exponential function – Proposition 4.3. Vertex Cover Number strictly upper bounds Neighborhood Diversity.
  • page 23 : bounded neighborhood diversity does not imply bounded vertex cover – Proposition 4.3. Vertex Cover Number strictly upper bounds Neighborhood Diversity.
  • page 29 : bounded edge clique cover number does not imply bounded vertex cover – Proposition 4.13. Edge Clique Cover Number is incomparable to Vertex Cover Number.
  • page 29 : bounded vertex cover does not imply bounded edge clique cover number – Proposition 4.13. Edge Clique Cover Number is incomparable to Vertex Cover Number.
  • page 34 : bounded c-closure does not imply bounded vertex cover – Proposition 5.3. $c$-Closure is incomparable to Vertex Cover Number.
  • page 34 : bounded vertex cover does not imply bounded c-closure – Proposition 5.3. $c$-Closure is incomparable to Vertex Cover Number.
• 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
• unknown source
  • maximum matching on bipartite graphs upper and lower bounds vertex cover by a linear function – Kőnig’s theorem
  • vertex cover upper and lower bounds maximum matching by a linear function – Every edge of the matching needs to be covered by at least one vertex. Path shows lower bound.
  • vertex cover upper bounds neighborhood diversity by an exponential function
  • vertex cover is equal to distance to edgeless
  • graph class edgeless has constant vertex cover
  • graph class star has constant vertex cover – trivially
• assumed
  • vertex cover upper bounds twin-cover number by a linear function – By definition
• 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.