On the geodetic hull number for complementary prisms II
RAIRO. Operations Research, Tome 55 (2021), pp. S2403-S2415

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.

DOI : 10.1051/ro/2020089
Classification : 05C12, 05C76
Keywords: Geodetic convexity, hull set, hull number, complementary prism 
@article{RO_2021__55_S1_S2403_0,
     author = {Castonguay, Diane and Coelho, Erika M. M. and Coelho, Hebert and Nascimento, Julliano R.},
     title = {On the geodetic hull number for complementary prisms {II}},
     journal = {RAIRO. Operations Research},
     pages = {S2403--S2415},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2020089},
     mrnumber = {4223198},
     zbl = {1469.05043},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2020089/}
}
TY  - JOUR
AU  - Castonguay, Diane
AU  - Coelho, Erika M. M.
AU  - Coelho, Hebert
AU  - Nascimento, Julliano R.
TI  - On the geodetic hull number for complementary prisms II
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S2403
EP  - S2415
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2020089/
DO  - 10.1051/ro/2020089
LA  - en
ID  - RO_2021__55_S1_S2403_0
ER  - 
%0 Journal Article
%A Castonguay, Diane
%A Coelho, Erika M. M.
%A Coelho, Hebert
%A Nascimento, Julliano R.
%T On the geodetic hull number for complementary prisms II
%J RAIRO. Operations Research
%D 2021
%P S2403-S2415
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2020089/
%R 10.1051/ro/2020089
%G en
%F RO_2021__55_S1_S2403_0
Castonguay, Diane; Coelho, Erika M. M.; Coelho, Hebert; Nascimento, Julliano R. On the geodetic hull number for complementary prisms II. RAIRO. Operations Research, Tome 55 (2021), pp. S2403-S2415. doi: 10.1051/ro/2020089

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

[2] B. S. Anand, M. Changat, S. Klavžar and I. Peterin, Convex sets in lexicographic products of graphs. Graphs Comb. 28 (2012) 77–84. | MR | Zbl | DOI

[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] S. R. Canoy, Jr. and I. Garces, Convex sets under some graph operations. Graphs Comb. 18 (2002) 787–793. | MR | Zbl | DOI

[5] C. C. Centeno, M. C. Dourado, L. D. Penso, D. Rautenbach and J. L. Szwarcfiter, Irreversible conversion of graphs. Theor. Comput. Sci. 412 (2011) 3693–3700. | MR | Zbl | DOI

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

[7] 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, (2001) 57–66. | DOI

[8] M. C. Dourado and R. M. Sampaio, Complexity aspects of the triangle path convexity. Discrete Appl. Math. 206 (2016) 39–47. | MR | Zbl | DOI

[9] 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. Discrete Math. 309 (2009) 5668–5674. | MR | Zbl | DOI

[10] M. C. Dourado, F. Protti, D. Rautenbach and J. L. Szwarcfiter, On the hull number of triangle-free graphs. SIAM J. Discrete Math. 23 (2010) 2163–2172. | MR | Zbl | DOI

[11] M. C. Dourado, F. Protti and J. L. Szwarcfiter, Complexity results related to monophonic convexity. Discrete Appl. Math. 158 (2010) 1268–1274. | MR | Zbl | DOI

[12] M. C. Dourado, L. D. Penso and D. Rautenbach, On the geodetic hull number of P k -free graphs. Theor. Comput. Sci. 640 (2016) 52–60. | MR | Zbl | DOI

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

[14] M. A. Duarte, L. Penso, D. Rautenbach and U. Dos Santos Souza, Complexity properties of complementary prisms. J. Comb. Optim. 33 (2017) 365–372. | MR | Zbl | DOI

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

[16] 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

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

[18] C. Hernando, T. Jiang, M. Mora, I. M. Pelayo and C. Seara, On the Steiner, geodetic and hull numbers of graphs. Discrete Math. 293 (2005) 139–154. | MR | Zbl | DOI

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

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

[21] I. Peterin, Intervals and convex sets in strong product of graphs. Graphs Comb. 29 (2013) 705–714. | MR | Zbl | DOI

Cité par Sources :