A polynomial time algorithm for geodetic hull number for complementary prisms

Coelho, Erika M. M.; Coelho, Hebert; Nascimento, Julliano R.; Szwarcfiter, Jayme L.

RAIRO. Theoretical Informatics and Applications, Tome 56 (2022), article no. 1

Let $G$ be a finite, simple, and undirected graph and let $S\subseteq V\left(G\right)$. In the geodetic convexity, ($S\mathrm{is}convex$ if all vertices belonging to any shortest path between two vertices of $S$ lie in $S$ . The $\mathrm{𝑐𝑜𝑛𝑣𝑒𝑥}\mathrm{ℎ𝑢𝑙𝑙}H\left(S\right)\mathrm{of}S$ is the smallest convex set containing $S$ . The $\mathrm{ℎ𝑢𝑙𝑙}\mathrm{𝑛𝑢𝑚𝑏𝑒𝑟}h\left(G\right)$ is the minimum cardinality of a set . The $S\subseteq V\left(G\right)$ such that ($H\left(S\right)=V\left(G\right)$. The ($\mathrm{𝑐𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡𝑎𝑟𝑦}\mathrm{𝑝𝑟𝑖𝑠𝑚}\left(G\overline{G}\right)$ of a graph $G$ arises from the disjoint union of the graph $G\mathrm{and}\overline{G}$ by adding the edges of a perfect matching between the corresponding vertices of $G\mathrm{and}\overline{G}$. Previous works have determined $h\left(G\overline{G}\right)$ when both $G\mathrm{and}\overline{G}$ are connected and partially when $G$ is disconnected. In this paper, we characterize convex sets in $\left(G\overline{G}\right)$ and we present equalities and tight lower and upper bounds for $h\left(G\overline{G}\right)$. This fills a gap in the literature and allows us to show that $h\left(G\overline{G}\right)$ can be determined in polynomial time, for any graph $G$.

Classification : 05C69, 05C76, 05C85
Keywords: Complementary prisms, geodetic convexity, hull number

[1] J. Akiyama and F. Harary, A graph and its complement with specified properties I: Connectivity. Int. J. Math. Math. Sci. 2 (1979) 223–228. | MR | Zbl | DOI

[2] M. Albenque and K. Knauer, Convexity in partial cubes: the hull number, in LATIN 2014: Theoretical Informatics. Springer (2014) 421–432. | MR | Zbl

[3] J. Araujo, V. Campos, F. Giroire, N. Nisse, L. Sampaio and R. Soares, On the hull number of some graph classes. Theor. Comput. Sci. 475 (2013) 1–12. | MR | Zbl | DOI

[4] J. Araujo, G. Morel, L. Sampaio, R. Soares and V. Weber, Hull number: P₅-free graphs and reduction rules. Discr. Appl. Math. 210 (2016) 171–175. | MR | Zbl | DOI

[5] S. Bessy, M. C. Dourado, L. D. Penso and D. Rautenbach, The geodetic hull number is hard for chordal graphs. SIAM J. Discr. Math. 32 (2018) 543–547. | MR | Zbl | DOI

[6] B. Bollobás, The Art of Mathematics: Coffee Time in Memphis. Cambridge University Press (2006). | MR | Zbl | DOI

[7] P. P. Camargo, U. S. Souza and J. R. Nascimento, Remarks on k-clique, k-independent set and 2-contamination in complementary prisms. Int. J. Found. Comput. Sci. (2021) 1–16. | MR | Zbl

[8] M. R. Cappelle, L. Penso and D. Rautenbach, Recognizing some complementary products. Theor. Comput. Sci. 521 (2014) 1–7. | MR | Zbl | DOI

[9] D. Castonguay, E. M. M. Coelho, H. Coelho and J. R. Nascimento, On the geodetic hull number for complementary prisms II. RAIRO-Oper. Res. 55 (2021) S2403–S2415. | MR | Zbl | DOI

[10] V. Chvátal, C. T. Hoàng, N. V. R. Mahadev and D. De Werra, Four classes of perfectly orderable graphs. J. Graph Theory 11 (1987) 481–495. | MR | Zbl | DOI

[11] E. M. M. Coelho, H. Coelho, J. R. Nascimento and J. L. Szwarcfiter, On the geodetic hull number of complementary prisms. Preprint (2018). | arXiv

[12] E. M. M. Coelho, H. Coelho, J. R. Nascimento and J. L. Szwarcfiter, On the P₃-hull number of some products of graphs. Discr. Appl. Math. 253 (2019) 2–13. | MR | Zbl | DOI

[13] D. Corneil, H. Lerchs and L. Burlingham, Complement reducible graphs. Discr. Appl. Math. 3 (1981) 163–174. | MR | Zbl | DOI

[14] P. Domingos and M. Richardson, Mining the network value of customers. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’01. ACM, New York, NY, USA (2001) 57–66. | DOI

[15] M. C. Dourado, J. G. Gimbel, J. Kratochvíl, F. Protti and J. L. Szwarcfiter, On the computation of the hull number of a graph. Discr. Math. 309 (2009) 5668–5674. | MR | Zbl | DOI

[16] M. C. Dourado, L. D. Penso and D. Rautenbach, On the geodetic hull number of $P_{\kappa }$-free graphs.Theor. Comp. Sci. 640 (2016) 52–60. | MR | Zbl | DOI

[17] P. A. Dreyer and F. S. Roberts, Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion. Discr. Appl. Math. 157 (2009) 1615–1627. | MR | Zbl | DOI

[18] M. A. Duarte, L. Penso, D. Rautenbach and U. Dos Santos Souza, Complexity properties of complementary prisms. J. Combinat. Optim. (2015) 1–8. | MR | Zbl

[19] M. G. Everett and S. B. Seidman, The hull number of a graph. Discr. Math. 57 (1985) 217–223. | MR | Zbl | DOI

[20] A. Farrugia, Self-complementary graphs and generalisations: a comprehensive reference manual. University of Malta (1999).

[21] S. Foldes and P. L. Hammer, Split graphs, in Proceedings 8th Southeastern Conference on Combinatorics, Graph Theory and Computing, Louisiana State University, Baton Rouge, LA (1977) 311–315. | MR | Zbl

[22] P. L. Hammer and B. Simeone, The splittance of a graph. Combinatorica 1 (1981) 275–284. | MR | Zbl | DOI

[23] T. W. Haynes, M. A. Henning, P. J. Slater and L. C. Van Der Merwe, The complementary product of two graphs. Bull. Inst. Combinator. Appl. 51 (2007) 21–30. | MR | Zbl

[24] M. M. Kanté and L. Nourine, Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs. SIAM J. Discr. Math. 30 (2016) 311–326. | MR | Zbl | DOI

[25] H. Karami, S. M. Sheikholeslami, A. Khodkar and D. B. West, Connected domination number of a graph and its complement. Graphs Combinator. 28 (2012) 123–131. | MR | Zbl | DOI

[26] D. Peleg, Local majorities, coalitions and monopolies in graphs: a review. Theor. Comput. Sci. 282 (2002) 231–257. | MR | Zbl | DOI

[27] S.-J. Xu, Some parameters of graph and its complement. Discr. Math. 65 (1987) 197–207. | MR | Zbl | DOI