Let be the number of vertex covers of a graph of size . Then the vertex cover polynomial is defined by(1)where is the vertex count of (Dong et al. 2002).It is related to the independence polynomial by(2)(Akban and Oboudi 2013).Precomputed vertex cover polynomials for many named graphs in terms of a variable can be obtained in the Wolfram Language using GraphData[graph, "VertexCoverPolynomial"][x].The following table summarizes closed forms for the vertex cover polynomials of somecommon classes of graphs (cf. Dong et al. 2002).graphAndrásfai graph barbell graphbook graph cocktail party graphcomplete bipartite graph complete bipartite graph complete graph complete tripartite graph crown graphcycle graph empty graph gear graphhelm graphladder rung graph Möbius ladder path graph prism graphstar graph sun graphsunlet graph wheel graph Equivalent forms for the cycle graph include(3)(4)graphorderrecurrenceAndrásfai..
The vertex cover number is the size of a minimum vertex cover in a graph is known as the vertex cover number of , denoted .The König-Egeváry theorem states that the matching number (i.e., size of a maximum independent edge set) and vertex cover number are equal for a bipartite graph.The independence number of a graph and vertex cover number are related bywhere is the vertex count (West 2000).
Let be a collection of subsets of a finite set . A subset of that meets every member of is called the vertex cover, or hitting set.A vertex cover of a graph can also more simply be thought of as a set of vertices of such that every edge of has at least one of member of as an endpoint. The vertex set of a graph is therefore always a vertex cover. The smallest possible vertex cover for a given graph is known as a minimum vertex cover (Skiena 1990, p. 218), and its size is called the vertex cover number, denoted . Vertex covers, indicated with red coloring, are shown above for a number of graphs. In a complete k-partite graph, and vertex cover contains vertices from at least stages.A set of vertices is a vertex cover iff its complement forms an independent vertex set (Skiena 1990, p. 218). The counts of vertex covers and independent vertex sets in a graph are therefore the same.A vertex cover having the smallest possible number of vertices for a given graph..