next | previous | forward | backward | up | top | index | toc | Macaulay2 website
EdgeIdeals :: vertexCoverNumber

vertexCoverNumber -- find the vertex covering number of a (hyper)graph

Synopsis

Description

This function returns the vertex covering number of a (hyper)graph. The vertex covering number is the size of smallest vertex cover of the (hyper)graph. This corresponds to the smallest degree of a generator of the cover ideal of the (hyper)graph.

i1 : S = QQ[a..d];
i2 : g = graph {a*b,b*c,c*d,d*a} -- the four cycle

o2 = Graph{edges => {{a, b}, {b, c}, {a, d}, {c, d}}}
           ring => S
           vertices => {a, b, c, d}

o2 : Graph
i3 : vertexCoverNumber g

o3 = 2
i4 : S = QQ[a..e];
i5 : g = graph {a*b,a*c,a*d,a*e,b*c,b*d,b*e,c*d,c*e,d*e} -- the complete graph K_5

o5 = Graph{edges => {{a, b}, {a, c}, {b, c}, {a, d}, {b, d}, {c, d}, {a, e}, {b, e}, {c, e}, {d, e}}}
           ring => S
           vertices => {a, b, c, d, e}

o5 : Graph
i6 : vertexCoverNumber g

o6 = 4
i7 : h = hyperGraph {a*b*c,a*d,c*e,b*d*e}

o7 = HyperGraph{edges => {{a, b, c}, {a, d}, {c, e}, {b, d, e}}}
                ring => S
                vertices => {a, b, c, d, e}

o7 : HyperGraph
i8 : vertexCoverNumber(h)

o8 = 2

See also

Ways to use vertexCoverNumber :

For the programmer

The object vertexCoverNumber is a method function.