Complexity and structural results for the hull and convexity numbers in cycle convexity for graph products

Abstract

Let G be a graph and S ⊆ V ( G ). In the cycle convexity, we say that S is cycle convex if for any u ∈ V ( G ) ∖ S, the induced subgraph of S ∪ { u } contains no cycle that includes u. The cycle convex hull of S is the smallest convex set containing S. The cycle hull number of G, denoted by hncc ( G ), is the cardinality of the smallest set S such that the convex hull of S is V ( G ). The cycle convexity number of G, denoted by concc ( G ), is the maximum cardinality of a proper cycle convex set of V ( G ). This paper studies cycle convexity in graph products. We show that the cycle hull number is always two for strong and lexicographic products. For the Cartesian, we establish tight bounds for this product and provide a closed formula when the factors are trees, generalizing an existing result for grid graphs. In addition, given a graph G and an integer k, we prove that hncc ( G ) ≤ k is NP-complete even if G is a bipartite Cartesian product graph, addressing an open question in the literature. Furthermore, we present exact formulas for the cycle convexity number in those three graph products. That leads to the NP-completeness of, given a graph G and an integer k, deciding whether concc ( G ) ≥ k, when G is a Cartesian, strong or lexicographic product graph.