? 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 ,
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 ,
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
Cycle convexity and the tunnel number of links, 2018. ,
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
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.45, issue.2, 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. ,
DOI : 10.2172/10145949
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
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. ,
Inapproximability Results for Graph Convexity Parameters, pp.97-107 ,
DOI : 10.1016/j.tcs.2015.06.059
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. ,
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
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
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 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
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
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, Theor. Comput. Sci, vol.510, pp.127-135, 2013. ,
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
Convex sets in graphs, ii. minimal path convexity, Journal of Combinatorial Theory, Series B, vol.44, issue.3, pp.307-316, 1988. ,
The hull number of a graph, Discrete Mathematics, vol.57, issue.3, pp.217-223, 1985. ,
DOI : 10.1016/0012-365X(85)90174-8
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 : https://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. ,
A perspective on abstract convexity: Classifying alignments by varieties, Convexity and Related CombinatorialGeometry, 1982. ,
Algorithmic meta-theorems for restrictions of treewidth, Algorithmica, vol.64, pp.19-37, 2012. ,
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
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
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
Local majorities, coalitions and monopolies in graphs: a review, Theoretical Computer Science, vol.282, issue.2, pp.231-257, 2002. ,
Geodesic Convexity in Graphs, SpringerBriefs in Mathematics, 2013. ,
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
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