, 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, 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
, 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
, 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
, 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
, 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
, 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
, 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, 2017.
, 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-00799868
, 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
, Sharp thresholds in bootstrap percolation. Physica A: Statistical Mechanics and its Applications, pp.305-312, 2003.
DOI : 10.1016/s0378-4371(03)00364-9
, Random majority percolation, Random Structures and Algorithms, vol.6, issue.3, pp.315-340, 2010.
DOI : 10.1214/EJP.v11-326
, A c k n 5-approximation algorithm for treewidth, SIAM J. Comput, vol.16, issue.452, pp.317-378, 2016.
, -domination number, Discrete Applied Mathematics, 2017.
DOI : 10.1016/j.dam.2017.05.014
, Efficient algorithms for graphs with few p 4 's, Discrete Mathematics, vol.235, issue.1, pp.29-51, 2001.
, 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.
, 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
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.95.52
, 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
, 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
, Inapproximability Results for Graph Convexity Parameters, pp.97-107
, 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
, 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.
DOI : 10.1155/S0161171280000440
, 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://doi.org/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
URL : http://doi.org/10.1016/s0012-365x(98)00394-x
, 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
, The Convexity Number of a Graph, Graphs and Combinatorics, vol.18, issue.2, pp.209-217, 2002.
DOI : 10.1007/s003730200014
, 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.
, 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.
, 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
, 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://arxiv.org/abs/1305.1979
, 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
, The hull number of a graph, Discrete Mathematics, vol.57, issue.3, pp.217-223, 1985.
, Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, 2006.
, 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 : http://doi.org/10.1016/j.jctb.2011.02.008
, 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.
, On the Steiner, geodetic and hull numbers of graphs, British Combinatorial Conference19th British Combinatorial Conference, pp.139-154, 2005.
DOI : 10.1016/j.disc.2004.08.039
, 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.1287/moor.8.4.538
, Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae, vol.51, issue.1, pp.45-64, 1962.
, 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
, Local majorities, coalitions and monopolies in graphs: a review, Theoretical Computer Science, vol.282, issue.2, pp.231-257, 2002.
DOI : 10.1016/S0304-3975(01)00055-X
URL : http://doi.org/10.1016/s0304-3975(01)00055-x
, Monophonic numbers of the join and composition of connected graphs, Discrete Mathematics, vol.307, issue.9, pp.1146-1154, 2007.
, Complexity aspects of the computation of the rank of a graph, Discrete Mathematics & Theoretical Computer Science, vol.16, issue.2, pp.73-86, 2014.
, Convex analysis, Princeton Mathematical Series, issue.28, 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