On the geodetic hull number for complementary prisms II
Diane Castonguay, Erika M. M. Coelho, Hebert Coelho, Julliano R. Nascimento · RAIRO - Operations Research · 2020
In the geodetic convexity, a set of vertices S of a graph G is convex if all vertices belonging to any shortest path between two vertices of S lie in S. The convex hull H(S) of S is the smallest convex set containing S. If H(S) = V (G), then S is a hull set. The cardinality h(G) of a minimum hull set of G is the hull number of G. The complementary prism GḠ of a graph G arises from the disjoint union of the graph G and Ḡ by adding the edges of a perfect matching between the corresponding vertices of G and Ḡ. A graph G is autoconnected if both G and Ḡ are connected. Motivated by previous work, we study the hull number for complementary prisms of autoconnected graphs. When G is a split graph, we present lower and upper bounds showing that the hull number is unlimited. In the other case, when G is a non-split graph, it is limited by 3.