Cycle convexity and the tunnel number of links

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\cup {v\in V(G)\mid $\text{there is a cycle }$C$\text{ in }$G\text{ such that } V©\setminus S={v}}$,forevery$S\subseteq V(G)$\mathrm{.}Wesaythat$S\subseteq V(G)$isconvexif$I_{cc}(S)=S$\mathrm{.}Theconvexhullof$S\subseteq V(G)$,denotedby$Hull(S)$,istheinclusion-wiseminimalconvexset$S’$ such that $S\subseteq S^{\mathrm{\prime }}$. A set $S\subseteq V(G)$ is called a hull set if $Hull(S)=V(G)$. The hull number of $G$ in the cycle convexity, denoted by $h{n}_{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.