Computing the hull number in P3 and P3* convexities

• J. Araújo UFC
• M. Campêlo UFC
• G. H. de Sousa UFC

DOI: https://doi.org/10.5753/etc.2018.3176

Abstract

A subset of vertices S in a graph G = (V,E) is convex in the P3 (resp. P₃*) convexity if every vertex in V (G) \ S does not have two neighbors (resp. that are not adjacent to each other) in S. The convex hull of S is the minimum convex set containing it. A hull set is a set whose convex hull is V (G). The hull number is the cardinality of a minimum hull set. In this work, we propose and study two integer-linear programming formulations to determine the hull number of a graph in the P3 and P₃* convexities, which we believe to be the first ones presented in the literature. We carry out some computational experiments to evaluate their performances.

References

Convexity properties of graphs on sagemath. [link]. Accessed: 2018-03-27.

Araújo, R., Sampaio, R., and Szwarcfiter, J. (2013). The convexity of induced paths of order three. Electronic Notes in Discrete Mathematics, 44:109 – 114.

Draque Penso, L., Protti, F., Rautenbach, D., and Souza, U. S. (2014). On p3-convexity of graphs with bounded degree. In Gu, Q., Hell, P., and Yang, B., editors, Algorithmic Aspects in Information and Management, pages 263–274, Cham. Springer International Publishing.

Duchet, P. (1988). Convex sets in graphs, ii. minimal path convexity. Journal of Combinatorial Theory, Series B, 44(3):307 – 316.

Farber, M. and Jamison, R. E. (1986). Convexity in graphs and hypergraphs. SIAM J. Algebraic Discrete Methods, 7:433–444.