On the hull number on cycle convexity of graphs

In this work, we study the parameter hull number in a recently defined graph convexity called Cycle Convexity, whose definition is motivated by related notions in Knot Theory. For a graph G = (V, E), define the interval function in the Cycle Convexity as Icc(S) = S ? {v & ISIN; V (G) | there is a cycle C in G such that V(C) \ S = {v}}, for every S & SUBE; V (G). We say that S & SUBE; V (G) is convex if Icc(S) = S. The convex hull of S & SUBE; V (G), denoted by Hull(S), is the inclusion-wise minimal convex set S' such that S & SUBE; S'. A set S & SUBE; V (G) is called a hull set if Hull(S) = V (G). The hull number of G in the cycle convexity, denoted by hncc(G), is the cardinality of a smallest hull set of G. We first focus on the class of planar graphs, as the main motivation for the definition of hncc(G) stems from Knot Theory and occurs when G is a 4-regular planar graph. We prove that: the hull number of a 4-regular planar graph is at most half of its number of vertices and that such bound is tight; and that deciding whether hncc(G) & LE; k, provided a positive integer k and a planar graph G, is an NP-complete problem. On the positive side, we present polynomial-time algorithms to compute the hull number in the cycle convexity of chordal graphs, P4-sparse graphs, and grids.& COPY; 2023 Elsevier B.V. All rights reserved.

Automated summary

This paper studies the parameter hull number in a graph convexity called Cycle Convexity, which is motivated by related notions in Knot Theory. The authors define the interval function and investigate the properties and computational methods of the minimum convex set for a graph G.