. Hence, ? hn cc (G) for any graph G. Note that hn P3 (G) ? hn P * 3 (G) and in P3 (G) ? in P * 3 (G) for any graph G. Hence, it only remains to prove the upper bounds for cycle-convexity

@. Suppose, G. , and ?. , is the complete join of the two (q, q ? 4)-graphs G 1 and G 2 Note that since G has no universal vertex, the graphs G 1 and G 2 have n 1 ? 2 and n 2 ? 2 vertices, respectively. In such case, since every vertex of G 1 , resp. of G 2 , is adjacent to every vertex of G 2 , resp. of G 1 , two vertices on each side are enough in order to generate G, cc (G) ? 4. Therefore, we are left to characterize when in cc (G) = 3. We will prove the following claim

G. Clearly, |S ? V (G i )| ? 2 for some i ? {1, 2}. W.l.o.g., let us assume that S has at least two vertices in G 1 . Furthermore, since S is a generator for G, every vertex of V (G) \ S has at least two neighbors in S

?. Case and |. , Since |S ? V (G 2 )| = 1, each vertex of G 1 \ S must have at least one neighbor in S ? V (G 1 ) to be generated (otherwise it would have a unique neighbor in S)

?. Case and |. ?v, = 3 and S is not connected. Since S must have at least one connected component with at least 2 vertices, let x and y be two adjacent vertices of S and let {z} = S \ {x, y}. Let w ? V (G 1 ) \ S. The only way that w is generated is that x and y are neighbors of w. Hence

V. Araujo, F. Campos, N. Giroire, L. Nisse, R. Sampaio et al., On the hull number of some graph classes, Theoretical Computer Science, vol.475, issue.1 2, pp.1-12, 2013.
DOI : 10.1016/j.tcs.2012.12.035

URL : https://hal.archives-ouvertes.fr/inria-00635032

V. J. Araujo, D. Campos, J. Girão, A. Nogueira, A. Salgueiro et al., Cycle convexity and the tunnel number of links, 2018.

G. J. Araujo, L. Morel, R. Sampaio, V. Soares, and . Weber, Hull number: -free graphs and reduction rules, LAGOS'13: Seventh Latin- American Algorithms, Graphs, and Optimization Symposium, pp.171-175, 2016.
DOI : 10.1016/j.endm.2013.10.011

URL : https://hal.archives-ouvertes.fr/hal-01568575

R. [. Araújo, J. L. Sampaio, and . Szwarcfiter, The convexity of induced paths of order three, Electronic Notes in Discrete Mathematics, vol.44, pp.109-114, 2013.
DOI : 10.1016/j.endm.2013.10.017

B. [. Balogh and . Bollobás, Sharp thresholds in bootstrap percolation. Physica A: Statistical Mechanics and its Applications, pp.305-312, 2003.
DOI : 10.1016/s0378-4371(03)00364-9

P. Balister, B. Bollobás, J. R. Johnson, and M. Walters, Random majority percolation, Random Structures and Algorithms, vol.6, issue.3, pp.315-340, 2010.
DOI : 10.1214/EJP.v11-326

. L. Bdd-+-16-]-h, P. G. Bodlaender, M. S. Drange, F. V. Dregi, D. Fomin et al., A c k n 5-approximation algorithm for treewidth, SIAM J. Comput, vol.45, issue.2, pp.317-378, 2016.

C. Bujtás and S. Jaskó, -domination number, Discrete Applied Mathematics, 2017.
DOI : 10.1016/j.dam.2017.05.014

. Bkk-+-01-]-l, T. Babel, J. Kloks, D. Kratochvil, H. Kratsch et al., Efficient algorithms for graphs with few p 4 's, Discrete Mathematics, vol.235, issue.1, pp.29-51, 2001.

U. [. Bondy and . Murty, Graph Theory, Graduate Texts in Mathematics, vol.244, 2008.
DOI : 10.1007/978-1-84628-970-5

S. [. Babel and . Olariu, On the structure of graphs with few P4s, Discrete Applied Mathematics, vol.84, issue.1-3, pp.1-13, 1998.
DOI : 10.1016/S0166-218X(97)90120-7

]. H. Bod98 and . Bodlaender, A partial k -arboretum of graphs with bounded treewidth, Theor. Comput. Sci, vol.209, issue.12, pp.1-45, 1998.

B. [. Blair and . Peyton, An introduction to chordal graphs and clique trees, The IMA Volumes in Mathematics and its Applications, pp.1-29, 1993.
DOI : 10.2172/10145949

G. [. Balogh and . Pete, Random disease on the square grid, Random Structures and Algorithms, vol.13, issue.3-4, pp.409-422, 1998.
DOI : 10.1002/(SICI)1098-2418(199810/12)13:3/4<409::AID-RSA11>3.0.CO;2-U

J. [. Chlebík and . Chlebíková, Approximation hardness of dominating set problems in bounded degree graphs, Information and Computation, vol.206, issue.11, pp.1264-1275, 2008.
DOI : 10.1016/j.ic.2008.07.003

. C. Cdd-+-10-]-c, S. Centeno, M. C. Dantas, D. Dourado, J. L. Rautenbach et al., Convex partitions of graphs induced by paths of order three, Discrete Mathematics & Theoretical Computer Science, vol.12, issue.5, pp.175-184, 2010.

M. [. Coelho, R. M. Dourado, and . Sampaio, Inapproximability Results for Graph Convexity Parameters, pp.97-107
DOI : 10.1016/j.tcs.2015.06.059

M. Chellali, O. Favaron, A. Hansberg, and L. Volkmann, k-Domination and k-Independence in Graphs: A Survey, Graphs and Combinatorics, vol.21, issue.125, pp.1-55, 2012.
DOI : 10.1016/j.aml.2007.10.016

]. B. Cla80 and . Clark, The heegaard genus of manifolds obtained by surgery on links and knots, International Journal of Mathematics and Mathematical Sciences, vol.3, issue.3, pp.583-589, 1980.

M. [. Courcelle and . Mosbah, Monadic second-order evaluations on tree-decomposable graphs, Theoretical Computer Science, vol.109, issue.1-2, pp.49-82, 1993.
DOI : 10.1016/0304-3975(93)90064-Z

URL : http://www.labri.fr/perso/courcell/Textes1/BC-Mosbah(1993).pdf

J. [. Changat and . Mathew, On triangle path convexity in graphs, Discrete Mathematics, vol.206, issue.1-3, pp.91-95, 1999.
DOI : 10.1016/S0012-365X(98)00394-X

V. Campos, R. M. Sampaio, A. Silva, and J. L. Szwarcfiter, Graphs with few <mml:math altimg="si1.gif" display="inline" overflow="scroll" xmlns:xocs="http://www.elsevier.com/xml/xocs/dtd" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.elsevier.com/xml/ja/dtd" xmlns:ja="http://www.elsevier.com/xml/ja/dtd" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:tb="http://www.elsevier.com/xml/common/table/dtd" xmlns:sb="http://www.elsevier.com/xml/common/struct-bib/dtd" xmlns:ce="http://www.elsevier.com/xml/common/dtd" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:cals="http://www.elsevier.com/xml/common/cals/dtd" xmlns:sa="http://www.elsevier.com/xml/common/struct-aff/dtd"><mml:msub><mml:mrow><mml:mi>P</mml:mi></mml:mrow><mml:mrow><mml:mn>4</mml:mn></mml:mrow></mml:msub></mml:math>???s under the convexity of paths of order three, 11th Cologne/Twente Workshop on Graphs and Combinatorial Optimization, pp.28-39, 2012.
DOI : 10.1016/j.dam.2014.05.005

C. [. Chartrand, P. Wall, and . Zhang, The Convexity Number of a Graph, Graphs and Combinatorics, vol.18, issue.2, pp.209-217, 2002.
DOI : 10.1007/s003730200014

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 Mathematics, vol.309, issue.18, pp.5668-5674, 2006.
DOI : 10.1016/j.disc.2008.04.020

F. [. Dourado, J. L. Protti, and . Szwarcfiter, Complexity results related to monophonic convexity, Traces from LAGOS'07 IV Latin American Algorithms, Graphs, and Optimization Symposium Puerto Varas -2007, pp.1268-1274, 2010.
DOI : 10.1016/j.dam.2009.11.016

URL : https://doi.org/10.1016/j.dam.2009.11.016

P. A. Dreyer and F. S. Roberts, Irreversible <mml:math altimg="si38.gif" display="inline" overflow="scroll" xmlns:xocs="http://www.elsevier.com/xml/xocs/dtd" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.elsevier.com/xml/ja/dtd" xmlns:ja="http://www.elsevier.com/xml/ja/dtd" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:tb="http://www.elsevier.com/xml/common/table/dtd" xmlns:sb="http://www.elsevier.com/xml/common/struct-bib/dtd" xmlns:ce="http://www.elsevier.com/xml/common/dtd" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:cals="http://www.elsevier.com/xml/common/cals/dtd"><mml:mi>k</mml:mi></mml:math>-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion, Discrete Applied Mathematics, vol.157, issue.7, pp.1615-1627, 2009.
DOI : 10.1016/j.dam.2008.09.012

+. Drds, ]. M. Dourado, D. Rautenbach, V. F. Santos, P. M. Schäfer et al., An upper bound on the p 3 -radon number, Discrete Mathematics, issue.16, pp.3122433-2437, 2012.

+. Drds, ]. M. Dourado, D. Rautenbach, V. F. Santos, P. M. Schäfer et al., On the carathéodory number of interval and graph convexities, Theor. Comput. Sci, vol.510, pp.127-135, 2013.

D. [. Dinur and . Steurer, Analytical approach to parallel repetition, Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC '14, pp.624-633, 2014.
DOI : 10.1007/978-3-642-15369-3_54

URL : http://www.cs.cornell.edu/~dsteurer/papers/productgames.pdf

]. P. Duc88 and . Duchet, Convex sets in graphs, ii. minimal path convexity, Journal of Combinatorial Theory, Series B, vol.44, issue.3, pp.307-316, 1988.

S. [. Everett and . Seidman, The hull number of a graph, Discrete Mathematics, vol.57, issue.3, pp.217-223, 1985.
DOI : 10.1016/0012-365X(85)90174-8

M. [. Flum and . Grohe, Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, 2006.

P. [. Fomin, D. M. Golovach, and . Thilikos, Contraction obstructions for treewidth, Journal of Combinatorial Theory, Series B, vol.101, issue.5, pp.302-314, 2011.
DOI : 10.1016/j.jctb.2011.02.008

URL : https://doi.org/10.1016/j.jctb.2011.02.008

R. [. Farber and . Jamison, Convexity in Graphs and Hypergraphs, SIAM Journal on Algebraic Discrete Methods, vol.7, issue.3, pp.433-444, 1986.
DOI : 10.1137/0607049

]. R. Gan12 and . Ganian, Using neighborhood diversity to solve hard problems. CoRR, abs, 1201.

D. [. Garey and . Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.

. Hjm-+-05-]-c, T. Hernando, M. Jiang, I. M. Mora, C. Pelayo et al., On the steiner, geodetic and hull numbers of graphs, British Combinatorial Conference19th British Combinatorial Conference, pp.139-154, 2005.

]. R. Jam82 and . Jamison, A perspective on abstract convexity: Classifying alignments by varieties, Convexity and Related CombinatorialGeometry, 1982.

]. M. Lam12 and . Lampis, Algorithmic meta-theorems for restrictions of treewidth, Algorithmica, vol.64, pp.19-37, 2012.

J. [. Lekkeikerker and . Boland, Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae, vol.51, issue.1, pp.45-64, 1962.
DOI : 10.4064/fm-51-1-45-64

J. [. Nayak, N. Ren, and . Santoro, An improved testing scheme for catastrophic fault patterns, Information Processing Letters, vol.73, issue.5-6, pp.5-6199, 2000.
DOI : 10.1016/S0020-0190(00)00012-0

S. [. Paluga and . Canoy-jr, Monophonic numbers of the join and composition of connected graphs, Discrete Mathematics, vol.307, issue.9-10, pp.1146-1154, 2007.
DOI : 10.1016/j.disc.2006.08.002

]. D. Pel02 and . Peleg, Local majorities, coalitions and monopolies in graphs: a review, Theoretical Computer Science, vol.282, issue.2, pp.231-257, 2002.

]. I. Pel13 and . Pelayo, Geodesic Convexity in Graphs, SpringerBriefs in Mathematics, 2013.

I. F. Ramos, V. F. Santos, and J. L. Szwarcfiter, Complexity aspects of the computation of the rank of a graph, Discrete Mathematics & Theoretical Computer Science, vol.16, issue.2, pp.73-86, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01185615

]. R. Roc70 and . Rockafellar, Convex analysis, Princeton Mathematical Series, issue.28, 1970.

]. J. Var76 and . Varlet, Convexity in tournaments, Bull. Soc. R. Sci.Lì ege, vol.45, pp.570-586, 1976.

K. [. Wasserman and . Faust, Social network analysis: Methods and applications, 1994.
DOI : 10.1017/CBO9780511815478