Complexity and Structural Results for the Hull and Convexity Numbers in Cycle Convexity for Graph Products

Bijo S. Anand, Ullas Chandran S. V, Julliano R. Nascimento, Revathy S. Nair · 2024

Read Complexity and Structural Results for the Hull and Convexity Numbers in Cycle Convexity for Graph Products by Bijo S. Anand, Ullas Chandran S. V, Julliano R. Nascimento, Revathy S. Nair (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-19258.txt.

Introduction

Cycle convexity in graph products is studied by Anand and co-authors in a 2024 paper. In this setting, a set of vertices is called cycle convex if adding any outside vertex creates no cycle through that vertex inside the set. Two numbers matter here: the hull number, the size of the smallest set whose hull is the whole graph, and the convexity number.

For strong and lexicographic products, the hull number is always two. For Cartesian products, the team gives tight bounds and a closed formula when the factors are trees, which extends a known result for grid graphs. They also prove that deciding whether the hull number is at most a given value stays NP-complete even for bipartite Cartesian products, settling an open question.

Catalog record

CREATORBijo S. Anand, Ullas Chandran S. V, Julliano R. Nascimento, Revathy S. Nair
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-19258

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Complexity and Structural Results for the Hull and Convexity Numbers in Cycle Convexity for Graph Products Bijo S. Anand, Ullas Chandran S. V, Julliano R. Nascimento, Revathy S. Nair Abstract Let G G be a graph and S ⊆ V ⁡ ( G ) S\subseteq V(G) . In the cycle convexity, we say that S S is cycle convex if for any u ∈ V ⁡ ( G ) ∖ S u\in V(G)\setminus S , the induced subgraph of S ∪ { u } S\cup\{u\} contains no cycle that includes u u . The cycle convex hull of S S is the smallest convex set containing S S . The cycle hull number of G G , denoted by h ​ n c ​ c ​ ( G ) hn_{cc}(G) , is the cardinality of the smallest set S S such that the convex hull of S S is V ⁡ ( G ) V(G) . The convexity number of G G , denoted by C c ​ c ​ ( G ) C_{cc}(G) , is the maximum cardinality of a proper convex set of V ⁡ ( G ) 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 G and an integer k k , we prove that h ​ n c ​ c ​ ( G ) ≤ k hn_{cc}(G)\leq k is NP-complete even if G 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 G and an integer k k , deciding whether C c ​ c ​ ( G ) ≥ k C_{cc}(G)\geq k , when G G is a Cartesian, strong or lexicographic product graph. Keywords: convexity; convexity number; hull number; cycle convexity number; cycle hull number; Cartesian product; strong product; lexicographic product. AMS Subj.Class: 05C69, 05C76, 05C85 1 Introduction A finite convexity space is defined as a pair (V,\mathcal{C}) , where V is a non-empty finite set and \mathcal{C} is a collection of subsets of V satisfying the following properties: \emptyset\in\mathcal{C} , V\in\mathcal{C} , and \mathcal{C} is closed under intersections. The elements of \mathcal{C} are referred to as convex sets ; see [ 23 ] . Various convexity structures associated with the vertex set of a graph are widely studied. The most natural convexities in graphs are path convexities, defined in terms of a family of paths \mathcal{P} , where a set S of vertices in G is \mathcal{P} - convex if S includes all vertices of every path in \mathcal{P} between any two vertices of S . An extensive overview of different types of path convexities are provided in [ 21 ] . The well-known geodesic convexity corresponds to the case where \mathcal{P} is the family of all shortest paths; see [ 15 , 16 , 17 ] . Other significant examples include monophonic convexity [ 8 , 13 , 14 ] and P_{3} - convexity [ 10 , 11 , 12 ] . These convexities are defined respectively over induced paths and paths with three vertices. There are also convexity definitions that do not rely on path systems; some significant examples include Steiner convexity [ 9 ] and \Delta - convexity [ 1 , 2 , 3 ] . In the case of Steiner convexity, a set S\subseteq V(G) is Steiner convex if, for any subset S^{\prime}\subseteq S , all vertices of any Steiner tree with terminal set S^{\prime} are contained within S . In the case of \Delta -convexity, a set S\subseteq V(G) is \Delta - convex if every vertex u\in V(G)\setminus S fails to form a triangle with any two vertices in S . Graph convexities have been studied in many contexts, including the determination of convexity invariants such as the hull number, the interval number, and the convexity number. A major reference work by Pelayo [ 21 ] provides an extensive survey of geodesic convexity. A newly introduced convexity, known as cycle convexity , was recently studied in [ 7 ] . In this convexity, for a set S of vertices in a graph G , the cycle interval of S , denoted by \langle S\rangle , is the set formed by the vertices of S and any w\in V(G) that form a cycle with the vertices of S . If \langle S\rangle=S , then S is cycle convex in G . The cycle convexity number of G , C_{cc}(G) , is the maximum cardinality of a proper cycle convex set of V(G) . The cycle convex hull of a set S , denoted by \langle S\rangle_{C} , is the smallest cycle convex set containing S . We say that a vertex w\in V(G) is generated by S if w\in\langle S\rangle_{C} . The hull number of G in the cycle convexity, or more briefly, the cycle hull number of G , hn_{cc}(G) , is the cardinality of the smallest set S such that \langle S\rangle_{C}=V(G) . The study of cycle convexity in graphs has gained attention due to its applications in both graph theory and related fields such as Knot Theory [ 4 ] . Concerning the cycle hull number, Araujo et al. [ 5 ] presented bounds for this parameter in 4 -regular planar graphs and proved that, given a planar graph G and an integer k , determining whether hn_{cc}(G)\leq k is NP-complete. They also showed that the parameter is computable in polynomial time for classes like chordal, P_{4} -sparse, and grid graphs. Regarding the cycle convexity number, Lima, Marcilon, and Medeiros [ 20 ] showed that, given a graph G and an integer k , determining whether C_{cc}(G)\geq k is both NP-complete and W[1]-hard when parameterized by the size of the solution. However, for certain graph classes such as extended P_{4} -laden graphs, they show an algorithm able to solve the problem in polynomial time. In addition, other results have been obtained for related parameters in cycle convexity, for instance, the interval number [ 7 ] and the percolation time [ 20 ] . In this work, we explore some properties of cycle convex sets in graph products, focusing on the hull number and the convexity number. For the strong and lexicographic products of nontrivial connected graphs, we show that the cycle hull number is always two. For the Cartesian product, we establish tight bounds on the cycle hull number and present a closed formula for this parameter for Cartesian products of trees, which generalizes a known result for grid graphs [ 5 ] . On the complexity side, we close a gap in the literature regarding the cycle hull number for bipartite graphs, left open by Araujo et al. [ 5 ] . Specifically, given a graph G and an integer k , we show that determining whether hn_{cc}(G)\leq k is NP-complete even if G is

Read the complete text