@. 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

?. Else, Indeed, since G is a thick spider, |K| = |S| ? 3, and we pick any three vertices in K in order to form the subset X that we will prove to be a generator for G. In order to prove it, since X induces a triangle, it is sufficient to prove that every vertex of G \ X has at least two adjacent neighbors in X. First, since X ? K and K is a clique, the latter holds for every vertex of K \ X. Furthermore, since there is a complete join between K and R, it also holds for every vertex of R. Finally, since every vertex of S has |K| ? 1 neighbors in K, there is at most one vertex in X that is nonadjacent to a given vertex in S, and so, since |X| ? 3, every vertex of S has at least two neighbors in X. Consequently, X is a generator for G

?. {1, Neighborhood Diversity This section is devoted to the design of an FPT algorithm for computing in cc parameterized by the neighborhood diversity Two distinct vertices u and v are twins if N (u) \ v = N (v) \ u. The neighborhood diversity of a graph is k, if its vertex set can be partitioned into k sets P 1 , . . . , P k such that, for every , k}, any pair of vertices u, v ? P i are twins. This parameter was proposed in [Lam12], motivated by the fact that a graph of bounded vertex cover also has bounded neighborhood diversity, and therefore the later parameter can be used to obtain more general results

. Proof, P. Let, |. ?. Be-of-size-|p-|-=-min{2, . S|}, S. =. Let et al., First, we claim that S is a generator for If x ? S then we are done. Otherwise, recall that every vertex x / ? S is the unique vertex of a cycle C that is not in S. In particular, by taking the smallest such cycle we can assume w.l.o.g. C to be induced. In this situation, C contains no more than two vertices of P since they are pairwise twins. Furthermore, for any P ? P of size, )|, the subset V (C \ P ) ? P induces a cycle C (again

@. Suppose, G. Generator, |. By, |. |. |s|-by-construction, S. |s| et al., Moreover since the vertices of P are pairwise twins, for any P * ? P of size |P * | = |P | there is an automorphism of G mapping P to

@. Otherwise, G. Does-not-generate, |. ?. The-latter-implies, ?. Let, \. S. Since et al., Suppose for sake of contradiction that Furthermore, since V \ S is generated by S , there exists a cycle C such that v is the only vertex of C not in S . However, for every v ? (P ? S) \ S , since v and v are twins it implies that there is a cycle C with vertex-set V (C \ v) ? {v }, and so, v is also generated by

. Proof and P. Let, By Lemma 37, for every 1 ? i ? k there are at most four possibilities for |P i ?S|: either |P i ?S| ? 2 (three possibilities) or P i ? S.. Overall, there are 4 k possibilities for the sequence |S ? P 1 |, |S ? P 2 |, . . . , |S ? P k |, and since by Lemma 37 the p i = |P i ? S| vertices of P i ? S can be chosen arbitrarily, a minimum-size generator S for G can be computed by exhaustive search over 4 k subsets if a partition into P i , 1 ? i ? k is given

. J. References, V. Araujo, F. Campos, N. Giroire, L. Nisse et al., On the hull number of some graph classes, Theor. Comput. Sci, vol.475, pp.1-12, 2013.

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

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.

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.

J. Balogh and B. Bollobás, Sharp thresholds in bootstrap percolation. Physica A: Statistical Mechanics and its Applications, pp.305-312, 2003.

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. Hans, . Bodlaender, M. S. Drange, F. V. Dregi, D. Fomin et al., A c k n 5-approximation algorithm for treewidth, SIAM J. Comput, vol.16, issue.452, pp.317-378, 2016.

[. Bujtás and S. Jaskó, -domination number, Discrete Applied Mathematics, 2017.

. 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.

[. Babel and S. Olariu, On the structure of graphs with few P4s, Discrete Applied Mathematics, vol.84, issue.1-3, pp.1-13, 1998.

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

R. S. Jean, B. Blair, and . Peyton, An introduction to chordal graphs and clique trees, The IMA Volumes in Mathematics and its Applications, pp.1-29, 1993.

J. Balogh and G. Pete, Random disease on the square grid, Random Structures and Algorithms, vol.13, issue.3-4, pp.409-422, 1998.

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.

C. C. Centeno, S. Dantas, M. Costa-dourado, D. Rautenbach, and J. L. Szwarcfiter, Convex partitions of graphs induced by paths of order three, Discrete Mathematics & Theoretical Computer Science, vol.12, issue.5, pp.175-184, 2010.

M. M. Erika, M. C. Coelho, R. M. Dourado, and . Sampaio, Inapproximability Results for Graph Convexity Parameters, pp.97-107

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.

B. 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.

[. Courcelle and M. Mosbah, Monadic second-order evaluations on tree-decomposable graphs, Theoretical Computer Science, vol.109, issue.1-2, pp.49-82, 1993.

M. Changat and J. Mathew, On triangle path convexity in graphs, Discrete Mathematics, vol.206, issue.1-3, pp.91-95, 1999.

R. M. Victor-campos, A. Sampaio, J. L. Silva, and . 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.

G. Chartrand, C. E. Wall, and P. Zhang, The Convexity Number of a Graph, Graphs and Combinatorics, vol.18, issue.2, pp.209-217, 2002.

J. G. Dourado, F. Kratochvíl, J. L. Protti, and . Szwarcfiter, On the computation of the hull number of a graph, Discrete Mathematics, vol.309, issue.18, pp.5668-5674, 2006.

C. Mitre, F. Dourado, J. L. Protti, and . Szwarcfiter, Complexity results related to monophonic convexity Traces from LA- GOS'07 IV Latin American Algorithms, Graphs, and Optimization Symposium Puerto Varas, Discrete Applied Mathematics, vol.158, issue.12, pp.1268-1274, 2007.

A. Paul, F. S. Dreyer, and . Roberts, Irreversible k-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.

M. Costa-dourado, D. Rautenbach, V. Fernandes-dos-santos, P. M. Schäfer, J. L. Szwarcfiter et al., An upper bound on the p 3 -radon number, Discrete Mathematics, issue.16, pp.3122433-2437, 2012.

M. Costa-dourado, D. Rautenbach, V. Fernandes-dos-santos, P. M. Schäfer, and J. L. Szwarcfiter, On the Carath??odory number of interval and graph convexities, Theoretical Computer Science, vol.510, pp.127-135, 2013.

[. Dinur and D. Steurer, Analytical approach to parallel repetition, Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC '14, pp.624-633, 2014.

P. Duchet, Convex sets in graphs, II. Minimal path convexity, Journal of Combinatorial Theory, Series B, vol.44, issue.3, pp.307-316, 1988.

G. Martin, S. B. Everett, and . Seidman, The hull number of a graph, Discrete Mathematics, vol.57, issue.3, pp.217-223, 1985.

J. Flum and M. 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.

M. Farber, E. Robert, 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. Ganian, Using neighborhood diversity to solve hard problems. CoRR, abs, 1201.

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

C. Hernando, T. Jiang, M. Mora, I. M. Pelayo, and C. Seara, 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. Lampis, Algorithmic Meta-theorems for Restrictions of Treewidth, Algorithmica, vol.4, issue.3, pp.19-37, 2012.
DOI : 10.1287/moor.8.4.538

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.

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.

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

M. Esamel, J. Paluga, R. Sergio, and . Canoy, Monophonic numbers of the join and composition of connected graphs, Discrete Mathematics, vol.307, issue.9, pp.1146-1154, 2007.

I. Da-fonseca-ramos, F. Vinicius, J. L. Santos, and . 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.

]. 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.