2020/12/10 by Júlio Aráujo, Víctor Campos, Araújo, Júlio +9
Computer Science · Materials Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Photochromic and Fluorescence Chemistry
paper · pdf · doi:10.48550/arxiv.2012.05656
openalex publication_date 2020/12/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Icc(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 Icc(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 hncc(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, P4-sparse graphs and grids can be done in polynomial time.