. Proof, Since G is simple and v does not have two distinct neighbors, then v must belong to any generator for G

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

?. Suppose, |. *. , R. , and I. E. , Indeed, if it not the case then assume w.l.o.g. that X 0 ? K 1 = ?, and let u 1 ? K 1 ? X 0 and let r 0 , r 1 ? X * ? R. Let u 2 ? K 2 , it can be shown similarly as for the previous claim that X = X 0 ? {u 2 , r 0 } is a generator for G. Since |X| ? |X * | and |X ? R| = 1, the latter proves the claim, and so, from now on let us assume that X 0 ? K = ?. In this subcase, since K is a SR-separator, the two vertices in X, By Theorem, vol.4, issue.2

?. Else, X. *. , and }. , By Claim 2, every vertex of R \ r 0 has two neighbors in X * (in order to be generated) So, R = {r 0 }, or |X 0 ? K| ? 2, or r 0 is a universal vertex of G[R]. Note that if |X 0 ? K| = 2 then X 0 ? {r} is a generator for G for any choice of r ? R, furthermore for any choice of a universal vertex r 0 of G

. 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, C. Girão, . Linhares, J. Sales et al., Cycle convexity and the tunnel number of links, 2016.

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.

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

[. Babel and S. 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

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.

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.
URL : https://hal.archives-ouvertes.fr/hal-00990463

[. Courcelle and M. 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

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

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.
DOI : 10.1016/j.disc.2008.04.020

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.

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.
DOI : 10.1016/j.tcs.2013.09.004

P. Duchet, Convex sets in graphs, II. Minimal path convexity, Journal of Combinatorial Theory, Series B, vol.44, issue.3, pp.307-316, 1988.
DOI : 10.1016/0095-8956(88)90039-1

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

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.

]. 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.1007/s00453-011-9554-x

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.

R. T. Rockafellar, Convex analysis. Princeton Mathematical Series, 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