Since G is simple and v does not have two distinct neighbors, then v must belong to any generator for G ,
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 ,
|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 ,
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) ,
= 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 ,
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 ,
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 ,
On the hull number of some graph classes, Theor. Comput. Sci, vol.475, pp.1-12, 2013. ,
Cycle convexity and the tunnel number of links, 2016. ,
A c k n 5-approximation algorithm for treewidth, SIAM J. Comput, vol.16, issue.452, pp.317-378, 2016. ,
Graph Theory, Graduate Texts in Mathematics, vol.244, 2008. ,
DOI : 10.1007/978-1-84628-970-5
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
A partial k -arboretum of graphs with bounded treewidth, Theor. Comput. Sci, vol.209, issue.12, pp.1-45, 1998. ,
An introduction to chordal graphs and clique trees, The IMA Volumes in Mathematics and its Applications, pp.1-29, 1993. ,
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
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
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
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
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. ,
An upper bound on the p 3 -radon number, Discrete Mathematics, issue.16, pp.3122433-2437, 2012. ,
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
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
Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, 2006. ,
Convexity in Graphs and Hypergraphs, SIAM Journal on Algebraic Discrete Methods, vol.7, issue.3, pp.433-444, 1986. ,
DOI : 10.1137/0607049
Using neighborhood diversity to solve hard problems. CoRR, abs, 1201. ,
Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979. ,
A perspective on abstract convexity: Classifying alignments by varieties, Convexity and Related CombinatorialGeometry, 1982. ,
Algorithmic Meta-theorems for Restrictions of Treewidth, Algorithmica, vol.4, issue.3, pp.19-37, 2012. ,
DOI : 10.1007/s00453-011-9554-x
Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae, vol.51, issue.1, pp.45-64, 1962. ,
Convex analysis. Princeton Mathematical Series, 1970. ,
Convexity in tournaments, Bull. Soc. R. Sci.Lì ege, vol.45, pp.570-586, 1976. ,
Social network analysis: Methods and applications, 1994. ,
DOI : 10.1017/CBO9780511815478