RAIRO-Theor. Inf. Appl.
Volume 56, 2022
|Number of page(s)||11|
|Published online||07 February 2022|
A polynomial time algorithm for geodetic hull number for complementary prisms*
INF, Universidade Federal de Goiás,
2 IM, COPPE, and NCE, Universidade Federal do Rio de Janeiro, RJ, Brazil.
3 IME, Universidade do Estado do Rio de Janeiro, RJ, Brazil.
** Corresponding author: firstname.lastname@example.org
Accepted: 4 January 2022
Let G be a finite, simple, and undirected graph and let S ⊆ V (G). In the geodetic convexity, S 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. The hull number h(G) is the minimum cardinality of a set S ⊆ V (G) such that H(S) = V (G). The complementary prism GG̅ of a graph G arises from the disjoint union of the graph G and G̅ by adding the edges of a perfect matching between the corresponding vertices of G and G̅. Previous works have determined h(GG̅) when both G and G̅ are connected and partially when G is disconnected. In this paper, we characterize convex sets in GG̅ and we present equalities and tight lower and upper bounds for h(GG̅). This fills a gap in the literature and allows us to show that h(GG̅) can be determined in polynomial time, for any graph G.
Mathematics Subject Classification: 05C69 / 05C76 / 05C85
Key words: Complementary prisms / geodetic convexity / hull number
© The authors. Published by EDP Sciences, 2022
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.