Cycle convexity and the tunnel number of links
share
In this work, we introduce a new graph convexity, that we call Cycle Convexity, motivated by related notions in Knot Theory. For a graph G=(V,E), define the interval function in the Cycle Convexity as I_cc(S) = S∪{v∈ V(G)|there is a cycle C in G such that V(C)∖ S={v}}, for every S⊆ V(G). We say that S⊆ V(G) is convex if I_cc(S)=S. The convex hull of S⊆ V(G), denoted by Hull(S), is the inclusion-wise minimal convex set S' such that S⊆ S'. A set S⊆ V(G) is called a hull set if Hull(S)=V(G). The hull number of G in the cycle convexity, denoted by hn_cc(G), is the cardinality of a smallest hull set of G. We first present the motivation for introducing such convexity and the study of its related hull number. Then, we prove that: the hull number of a 4-regular planar graph is at most half of its vertices; computing the hull number of a planar graph is an NP-complete problem; computing the hull humber of chordal graphs, P_4-sparse graphs and grids can be done in polynomial time.
READ FULL TEXT