Cobertura de vértices

Una cobertura de vértices para un grafo G es un conjunto de vértices V en los que cada arco de G incide al menos en un nodo de V. La cobertura de vértices mínima es la más pequeña de las coberturas de vértices. El número de cobertura de vértices ${\displaystyle \omega _{V}(G)\,}$ para un grafo G es el tamaño de la cobertura de vértices mínima.

• Para cualquier grafo, el conjunto de todos sus vértices es trivialmente una cobertura de vértices.
• Un grafo bipartito completo ${\displaystyle G_{m,n}\,}$ tiene ${\displaystyle \omega _{V}(G_{m,n})=\min \lbrace m,n\rbrace \,}$ y ${\displaystyle \omega _{E}(G_{m,n})=\max \lbrace m,n\rbrace \,}$.

• Para cualquier grafo ${\displaystyle G=(V,E)\,}$ : ${\displaystyle \omega _{V}(G)\,}$ + máximo conjunto de vértices independientes = ${\displaystyle {\Big |}V\ {\Big |}}$ (Tibor Gallai 1959)

• Cobertura de aristas
• Problema de la cobertura de vértices
• Problema de la clique

• Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.