J. Barré, M. Lelarge, and D. , Mitsche: On rigidity, orientability and cores of random graphs with sliders. Preprint available at http://math

B. Bollobás, D. Mitsche, and P. , Praa lat: Metric dimension for random graphs, Electronic Journal of Combinatorics, vol.20, issue.4, p.1, 2013.

A. Bonato, M. Lozier, D. Mitsche, X. Pérez-giménez, and P. , Praa lat: The domination number of on-line social networks and random geometric graphs, TAMC, vol.2015, pp.150-163

A. Bonato, D. Mitsche, and P. , Vertex-Pursuit in Random Directed Acyclic Graphs, SIAM Journal on Discrete Mathematics, vol.27, issue.2, pp.732-756, 2013.
DOI : 10.1137/120866932

URL : https://hal.archives-ouvertes.fr/hal-00923080

J. Díaz, D. Mitsche, G. Perarnau, and X. , Pérez-Giménez: On the relation between graph distance and Euclidean distance in random geometric graphs, Advances in Applied Probability, vol.483, 2016.

J. Díaz, D. Mitsche, and X. , Large Connectivity for Dynamic Random Geometric Graphs, IEEE Transactions on Mobile Computing, vol.8, issue.6, pp.821-835, 2009.
DOI : 10.1109/TMC.2009.42

J. Díaz, D. Mitsche, and X. Pérez-giménez, On the probability of the existence of fixed-size components in random geometric graphs, Advances in Applied Probability, vol.412, pp.344-357, 2009.

J. Díaz, D. Mitsche, and X. , Pérez-Giménez: Sharp Threshold for Hamiltonicity of Random Geometric Graphs, SIAM Journal on Discrete Mathematics, vol.21, issue.1, pp.1157-1165, 2007.

A. Frieze, D. Mitsche, X. Pérez-giménez, and P. , Praa lat: On-line list colouring of random graphs, Electronic Journal of Combinatorics, vol.22, issue.2, pp.2-41, 2015.

O. Giménez, D. Mitsche, and M. Noy, Maximum degree in minor-closed classes of graphs, European Journal of Combinatorics, vol.55, pp.41-61, 2016.
DOI : 10.1016/j.ejc.2016.02.001

W. Kinnersley, D. Mitsche, and P. , Praa lat: A note on the acquaintance time of random graphs, Electronic Journal of Combinatorics, vol.20, issue.3, p.52, 2013.

M. Kiwi and D. , Mitsche: A bound for the diameter of random hyperbolic graphs, ANALCO, vol.2015, pp.26-39

D. Mitsche and G. , Perarnau: On the treewidth and related parameters of Random Geometric Graphs, STACS Also: SIAM Journal on Discrete Mathematics, vol.2012, pp.408-419

D. Mitsche and P. , Praa lat: On the hyperbolicity of random graphs, Electronic Journal of Combinatorics, vol.21, issue.2, pp.2-39, 2014.

D. Mitsche and P. , Revolutionaries and Spies on Random Graphs, Combinatorics, Probability and Computing, vol.43, issue.03, pp.417-432, 2013.
DOI : 10.1016/j.tcs.2008.02.040

URL : https://hal.archives-ouvertes.fr/hal-00923090

D. Mitsche and J. , On the limiting distribution of the metric dimension for random forests, European Journal of Combinatorics, vol.49, pp.68-89, 2015.
DOI : 10.1016/j.ejc.2015.02.029

URL : https://hal.archives-ouvertes.fr/hal-01143653

J. Alder and E. Lev, Bootstrap percolation: visualizations and applications, Braz, J. Phys, vol.33, pp.641-644, 2003.

N. Alon, Choice Numbers of Graphs: a Probabilistic Approach, Combinatorics, Probability and Computing, vol.XXVI, issue.02, pp.107-114, 1992.
DOI : 10.1007/BF02122551

N. Alon, Restricted colorings of graphs, Surveys of Combinatorics, pp.1-33, 1993.
DOI : 10.1017/CBO9780511662089.002

N. Alon, F. R. Chung, and R. L. Graham, Routing Permutations on Graphs via Matchings, SIAM Journal on Discrete Mathematics, vol.7, issue.3, pp.513-530, 1994.
DOI : 10.1137/S0895480192236628

N. Alon, M. Krivelevich, and B. Sudakov, List Coloring of Random and Pseudo-Random Graphs, Combinatorica, vol.19, issue.4, pp.453-472, 1999.
DOI : 10.1007/s004939970001

J. Alonso, T. Brady, D. Cooper, T. Delzant, V. Ferlini et al., Notes on word hyperbolic groups, Group Theory from a Geometrical Viewpoint, 1992.

H. Amini, Bootstrap percolation and diffusion in random graphs with given vertex degrees, Electronic Journal of Combinatorics, vol.17, p.25, 2010.

H. Amini, N. Fountoulakis, and K. Panagiotou, Bootstrap percolation in inhomogeneous random graphs

L. Babai, P. Erd?-os, and S. M. Selkow, Random Graph Isomorphism, SIAM Journal on Computing, vol.9, issue.3, pp.628-635, 1980.
DOI : 10.1137/0209047

J. Balogh and B. Bollobás, Bootstrap percolation on the hypercube, Probability Theory and Related Fields, pp.624-648, 2006.

J. Balogh, B. Bollobás, H. Duminil-copin, and R. Morris, The sharp threshold for bootstrap percolation in all dimensions, Transactions of the American Mathematical Society, vol.364, issue.5, pp.2667-2701, 2012.
DOI : 10.1090/S0002-9947-2011-05552-2

J. Balogh, B. Bollobás, M. Krivelevich, T. Müller, and M. Walters, Hamilton cycles in random geometric graphs, The Annals of Applied Probability, vol.21, issue.3, pp.1053-1072, 2011.
DOI : 10.1214/10-AAP718

J. Balogh, B. Bollobás, and R. Morris, Majority Bootstrap Percolation on the Hypercube, Combinatorics, Probability and Computing, vol.198, issue.1-2, pp.17-51, 2009.
DOI : 10.1016/0898-1221(81)90137-1

J. Balogh, Y. Peres, and G. Pete, Bootstrap Percolation on Infinite Trees and Non-Amenable Groups, Combinatorics, Probability and Computing, vol.15, issue.05, pp.715-730, 2006.
DOI : 10.1017/S0963548306007619

J. Balogh and B. , Bootstrap percolation on the random regular graph, Random Structures and Algorithms, vol.31, issue.1-2, pp.257-286, 2007.
DOI : 10.1002/rsa.20158

A. Barabási and R. Albert, Emergence of scaling in random networks, Science, vol.286, issue.5439, pp.509-512, 1999.

A. Barbour, M. Karo´nskikaro´nski, and A. Ruci´nskiruci´nski, A central limit theorem for decomposable random variables with applications to random graphs, Journal of Combinatorial Theory, Series B, vol.47, issue.2, pp.125-145, 1989.
DOI : 10.1016/0095-8956(89)90014-2

J. Barré, M. Lelarge, and D. Mitsche, On rigidity, orientability and cores of random graphs with sliders, Preprint available at http://math

I. Benjamini, C. Hoppen, E. Ofek, P. Praa-lat, and N. Wormald, Geodesics and almost geodesic cycles in random regular graphs, Journal of Graph Theory, vol.28, issue.2, pp.115-136, 2011.
DOI : 10.1002/jgt.20496

I. Benjamini, I. Shinkar, and G. Tsur, Acquaintance Time of a Graph, SIAM Journal on Discrete Mathematics, vol.28, issue.2
DOI : 10.1137/130930078

N. Bernasconi, K. Panagiotou, and A. Steger, The Degree Sequence of Random Graphs from Subcritical Classes, Combinatorics, Probability and Computing, vol.9, issue.05, pp.647-681, 2009.
DOI : 10.1307/mmj/1029000098

M. Bode, N. Fountoulakis, and T. Müller, On the giant component of random hyperbolic graphs, pp.425-429, 2013.
DOI : 10.1007/978-88-7642-475-5_68

M. Bode, N. Fountoulakis, and T. Müller, On the largest component of a hyperbolic model of complex networks, Electronic Journal of Combinatorics, vol.22, issue.3, pp.3-24, 2015.

M. Bode, N. Fountoulakis, and T. Müller, The probability of connectivity in a hyperbolic model of complex networks, Random Structures & Algorithms, to appear

M. Boguñá, F. Papadopoulos, and D. Krioukov, Sustaining the internet with hyperbolic mapping, Nature Communications, issue.1, p.62, 2010.

B. Bollobás, The chromatic number of random graphs, Combinatorica, vol.5, issue.1, pp.49-55, 1988.
DOI : 10.1007/BF02122551

B. Bollobás, S. Janson, and O. Riordan, The phase transition in inhomogeneous random graphs, Random Structures and Algorithms, vol.123, issue.1, pp.3-122, 2007.
DOI : 10.1002/rsa.20168

B. Bollobás, D. Mitsche, and P. , Praa lat, Metric dimension for random graphs, Electronic Journal of Combinatorics, vol.20, issue.4, p.1, 2013.

A. Bonato, M. Lozier, D. Mitsche, X. Pérez-giménez, and P. Praa-lat, The Domination Number of On-line Social Networks and Random Geometric Graphs, pp.150-163, 2015.
DOI : 10.1007/978-3-319-17142-5_14

URL : https://hal.archives-ouvertes.fr/hal-01291967

A. Bonato, D. Mitsche, and P. , Vertex-Pursuit in Random Directed Acyclic Graphs, SIAM Journal on Discrete Mathematics, vol.27, issue.2, pp.732-756, 2013.
DOI : 10.1137/120866932

URL : https://hal.archives-ouvertes.fr/hal-00923080

A. Bonato and R. J. Nowakowski, The Game of Cops and Robbers on Graphs, 2011.
DOI : 10.1090/stml/061

A. Boukerche and L. Bononi, Simulation and Modeling of Wireless, Mobile, and AD HOC Networks, pp.373-410, 2004.
DOI : 10.1002/0471656895.ch14

M. Bradonjic, R. Elsässer, T. Friedrich, T. Sauerwald, and A. Stauffer, Efficient Broadcast on Random Geometric Graphs, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1412-1421, 2010.
DOI : 10.1137/1.9781611973075.114

W. Bresser, P. Boolchand, and P. Suranyi, Rigidity Percolation and Molecular Clustering in Network Glasses, Physical Review Letters, vol.56, issue.23, p.2493, 1986.
DOI : 10.1103/PhysRevLett.56.2493

J. V. Butterfield, D. W. Cranston, G. Puleo, D. B. West, and R. Zamani, Revolutionaries and spies: Spy-good and spy-bad graphs, Theoretical Computer Science, vol.463, pp.35-53, 2012.
DOI : 10.1016/j.tcs.2012.05.041

URL : http://arxiv.org/abs/1202.2910

E. Candellero and N. Fountoulakis, Clustering and the hyperbolic geometry of complex networks, WAW 2014, pp.1-12

R. Carr, W. M. Goh, and E. Schmutz, The maximum degree in a random tree and related problems, Random Structures and Algorithms, vol.1, issue.1, pp.13-24, 1994.
DOI : 10.1002/rsa.3240050104

J. Chalupa, P. L. Leath, and G. R. Reich, Bootstrap percolation on a Bethe lattice, Journal of Physics C: Solid State Physics, vol.12, issue.1, pp.31-35, 1979.
DOI : 10.1088/0022-3719/12/1/008

G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Applied Mathematics, vol.105, issue.1-3, pp.1-3, 2000.
DOI : 10.1016/S0166-218X(00)00198-0

J. Chayes, B. Bollobás, C. Borgs, and O. Riordan, Directed scale-free graphs, Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2003, pp.132-139

N. Chen, On the Approximability of Influence in Social Networks, SIAM Journal on Discrete Mathematics, vol.23, issue.3, pp.1400-1415, 2009.
DOI : 10.1137/08073617X

W. Chen, W. Fang, G. Hu, and M. W. Mahoney, On the Hyperbolicity of Small-World and Treelike Random Graphs, Internet Mathematics, vol.9, issue.4, pp.434-491, 2013.
DOI : 10.1080/15427951.2013.828336

F. R. Chung and L. Lu, Complex graphs and networks, 2006.
DOI : 10.1090/cbms/107

N. E. Clarke, S. Finbow, S. L. Fitzpatrick, M. E. Messinger, and R. J. Nowakowski, Seepage in directed acyclic graphs, Australasian Journal of Combinatorics, vol.43, pp.91-102, 2009.

B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Information and Computation, vol.85, issue.1, pp.12-75, 1990.
DOI : 10.1016/0890-5401(90)90043-H

URL : https://hal.archives-ouvertes.fr/hal-00353765

N. J. Cowan, E. J. Chastain, D. A. Vilhena, J. S. Freudenberg, and C. T. Bergstrom, Nodal Dynamics, Not Degree Distributions, Determine the Structural Controllability of Complex Networks, Nodal dynamics, not degree distributions, determine the structural controllability of complex networks, p.38398, 2012.
DOI : 10.1371/journal.pone.0038398.g001

D. W. Cranston, C. D. Smyth, and D. B. West, Revolutionaries and spies on trees and unicyclic graphs, Journal of Combinatorics, vol.3, issue.2, pp.195-206, 2012.
DOI : 10.4310/JOC.2012.v3.n2.a4

A. Denise, M. Vasconcellos, and D. J. Welsh, The random planar graph, Congressus Numerantium, pp.61-79, 1996.

J. S. Deogun, T. Kloks, D. Kratsch, and H. Müller, On vertex ranking for permutation and other graphs, STACS Lecture Notes in Comput. Sci, vol.94, issue.775, pp.747-758, 1994.
DOI : 10.1007/3-540-57785-8_187

J. Díaz, D. Mitsche, G. Perarnau, and X. Pérez-giménez, Abstract, Advances in Applied Probability, vol.48, issue.03, 2016.
DOI : 10.1137/1.9781611973075.114

J. Díaz, D. Mitsche, and X. Pérez-giménez, Large Connectivity for Dynamic Random Geometric Graphs, IEEE Transactions on Mobile Computing, vol.8, issue.6, pp.821-835, 2009.
DOI : 10.1109/TMC.2009.42

J. Díaz, D. Mitsche, and X. Pérez-giménez, On the probability of the existence of fixed-size components in random geometric graphs, Advances in Applied Probability, vol.412, pp.344-357, 2009.

J. Díaz, D. Mitsche, and X. Pérez-giménez, Sharp Threshold for Hamiltonicity of Random Geometric Graphs, SIAM Journal on Discrete Mathematics, vol.21, issue.1, pp.1157-1165, 2007.
DOI : 10.1137/060665300

M. Drmota, A Bivariate Asymptotic Expansion of Coefficients of Powers of Generating Functions, European Journal of Combinatorics, vol.15, issue.2, pp.139-152, 1994.
DOI : 10.1006/eujc.1994.1016

M. Drmota, Asymptotic distributions and a multivariate darboux method in enumeration problems, Journal of Combinatorial Theory, Series A, vol.67, issue.2, pp.169-184, 1994.
DOI : 10.1016/0097-3165(94)90011-6

M. Drmota, Random Trees: An Interplay between Combinatorics and Probability, 2009.
DOI : 10.1007/978-3-211-75357-6

M. Drmota, Systems of functional equations, Random Structures & Algorithms, vol.51, issue.1-2, pp.103-124, 1997.
DOI : 10.1002/(SICI)1098-2418(199701/03)10:1/2<103::AID-RSA5>3.0.CO;2-Z

URL : https://hal.archives-ouvertes.fr/hal-01197227

M. Drmota, O. Giménez, and M. Noy, The Maximum Degree of Series-Parallel Graphs, Combinatorics, Probability and Computing, vol.36, issue.04, pp.529-570, 2011.
DOI : 10.1006/eujc.1994.1016

M. Drmota, O. Giménez, M. Noy, K. Panagiotou, and A. Steger, The maximum degree of planar graphs, Proc. of the London Math, pp.892-920, 2014.

P. M. Duxbury, D. J. Jacobs, M. F. Thorpe, and C. , Floppy modes and the free energy: Rigidity and connectivity percolation on Bethe lattices, Physical Review E, vol.59, issue.2, p.2084, 1999.
DOI : 10.1103/PhysRevE.59.2084

R. B. Ellis, J. L. Martin, and C. Yan, Random Geometric Graph Diameter in the Unit Ball, Algorithmica, vol.47, issue.4, pp.421-438, 2007.
DOI : 10.1007/s00453-006-0172-y

L. R. Fontes, R. H. Schonmann, and V. Sidoravicius, Stretched Exponential Fixation in Stochastic Ising Models at Zero Temperature, Communications in Mathematical Physics, vol.228, issue.3, pp.495-518, 2002.
DOI : 10.1007/s002200200658

F. Foucaud and G. Perarnau, Bounds for identifying codes in terms of degree parameters, Electronic Journal of Combinatorics, vol.19, p.32, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00578230

N. Fountoulakis, On the evolution of random graphs on spaces with negative curvature

T. Friedrich and A. Krohmer, On the Diameter of Hyperbolic Random Graphs, pp.614-625, 2015.
DOI : 10.1007/978-3-662-47666-6_49

T. Friedrich, T. Sauerwald, and A. Stauffer, Diameter and broadcast time of random geometric graphs in arbitrary dimensions, Algorithms and Computation, pp.190-199, 2011.

A. Frieze, R. Martin, J. Moncel, M. Ruszinkó, and C. Smyth, Codes identifying sets of vertices in random networks, Discrete Mathematics, vol.307, issue.9-10, pp.9-10, 2007.
DOI : 10.1016/j.disc.2006.07.041

URL : https://hal.archives-ouvertes.fr/hal-00182312

A. Frieze, D. Mitsche, X. Pérez-giménez, and P. , Praa lat, On-line list coloring of random graphs, Electronic Journal of Combinatorics, vol.22, issue.2, pp.2-41, 2015.

Z. Gao and N. C. Wormald, The Distribution of the Maximum Vertex Degree in Random Planar Maps, Journal of Combinatorial Theory, Series A, vol.89, issue.2, pp.201-230, 2000.
DOI : 10.1006/jcta.1999.3006

E. N. Gilbert and R. Graphs, Random Graphs, The Annals of Mathematical Statistics, vol.30, issue.4, pp.1141-1144, 1959.
DOI : 10.1214/aoms/1177706098

E. N. Gilbert, Random Plane Networks, Random Plane Networks, pp.533-543, 1961.
DOI : 10.1137/0109045

O. Giménez, D. Mitsche, and M. Noy, Maximum degree in minor-closed classes of graphs, European Journal of Combinatorics, vol.55, pp.41-61, 2016.
DOI : 10.1016/j.ejc.2016.02.001

A. Goel, S. Rai, and B. Krishnamachari, Sharp thresholds For monotone properties in random geometric graphs, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing , STOC '04, pp.580-586, 2004.
DOI : 10.1145/1007352.1007441

M. Gromov, Hyperbolic groups Essays in group theory, pp.75-263, 1987.

R. A. Guerin, Channel occupancy time distribution in a cellular radio system, IEEE Transactions on Vehicular Technology, vol.36, issue.3, pp.89-99, 1987.
DOI : 10.1109/T-VT.1987.24106

L. Gugelmann, K. Panagiotou, and U. Peter, Random Hyperbolic Graphs: Degree Sequence and Clustering, ICALP, vol.2012, pp.573-585
DOI : 10.1007/978-3-642-31585-5_51

P. Gupta and P. R. Kumar, Critical Power for Asymptotic Connectivity in Wireless Networks, pp.547-566, 1999.
DOI : 10.1007/978-1-4612-1784-8_33

R. Halin, S-functions for graphs, Journal of Geometry, vol.147, issue.1-2, pp.171-186, 1976.
DOI : 10.1007/BF01917434

F. Harary and R. A. Melter, The metric dimension of a graph, Ars Combinatoria, vol.2, pp.191-195, 1976.

T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs, 1998.

S. T. Hedetniemi, S. M. Hedetniemi, and A. Liestman, A survey of gossiping and broadcasting in communication networks, Networks, vol.3, issue.4, pp.319-349, 1998.
DOI : 10.1002/net.3230180406

C. Hernando, M. Mora, I. Pelayo, C. Seara, and D. Wood, Extremal Graph Theory for Metric Dimension and Diameter, Electronic Notes in Discrete Mathematics, vol.29, issue.1, p.30, 2010.
DOI : 10.1016/j.endm.2007.07.058

A. Holroyd, Sharp metastability threshold for two-dimensional bootstrap percolation, Probab. Theory Relat, pp.195-224, 2003.

D. Howard and C. D. Smyth, Revolutionaries and Spies, Discrete Mathematics, vol.312, issue.22, pp.312-3384, 2012.
DOI : 10.1016/j.disc.2012.08.001

H. K. Hwang, On Convergence Rates in the Central Limit Theorems for Combinatorial Structures, European Journal of Combinatorics, vol.19, issue.3, pp.329-343, 1998.
DOI : 10.1006/eujc.1997.0179

S. Janson, On percolation in random graphs with given vertex degrees, Electronic Journal of Probability, vol.14, issue.0, pp.86-118, 2009.
DOI : 10.1214/EJP.v14-603

S. Janson, Simply generated trees, conditioned Galton???Watson trees, random allocations and condensation, Probability Surveys, vol.9, issue.0, pp.103-252, 2012.
DOI : 10.1214/11-PS188

URL : https://hal.archives-ouvertes.fr/hal-01197228

S. Janson and M. Luczak, A simple solution to thek-core problem, Random Structures and Algorithms, vol.67, issue.1-2, pp.50-62, 2007.
DOI : 10.1002/rsa.20147

]. S. Janson, T. Luczak, T. Turova, and T. Vallier, Bootstrap percolation on the random graph $G_{n,p}$, The Annals of Applied Probability, vol.22, issue.5, pp.1989-2047, 2012.
DOI : 10.1214/11-AAP822

A. Jardosh, E. Belding-royer, K. Almeroth, and S. Suri, Towards realistic mobility models for mobile ad hoc networks, Proceedings of the 9th annual international conference on Mobile computing and networking , MobiCom '03, 2003.
DOI : 10.1145/938985.939008

S. P. Kasiviswanathan, C. Moore, and L. Theran, The Rigidity Transition in Random Graphs, Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms (SODA) 2011, pp.1237-1252
DOI : 10.1137/1.9781611973082.94

D. Kempe, J. Kleinberg, and E. Tardos, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining , KDD '03, pp.137-146, 2003.
DOI : 10.1145/956750.956769

R. Kershner, The Number of Circles Covering a Set, American Journal of Mathematics, vol.61, issue.3, pp.665-671, 1939.
DOI : 10.2307/2371320

S. Khuller, B. Raghavachari, and A. Rosenfeld, Landmarks in graphs, Discrete Applied Mathematics, vol.70, issue.3, pp.217-229, 1996.
DOI : 10.1016/0166-218X(95)00106-2

H. A. Kierstead and D. Yang, Orderings on Graphs and Game Coloring Number, Order, vol.20, issue.3, pp.255-264, 2003.
DOI : 10.1023/B:ORDE.0000026489.93166.cb

W. Kinnersley, D. Mitsche, and P. , Praa lat, A note on the acquaintance time of random graphs, Electronic Journal of Combinatorics, vol.20, issue.3, p.52, 2013.

M. Kiwi and D. Mitsche, A Bound for the Diameter of Random Hyperbolic Graphs, pp.26-39, 2015.
DOI : 10.1137/1.9781611973761.3

URL : https://hal.archives-ouvertes.fr/hal-01143658

M. Kiwi, P. Moisset, I. Rapaport, S. Rica, and G. Theyssier, Strict Majority Bootstrap Percolation in the r-wheel, Information Processing Letters, vol.114, issue.6, pp.277-281, 2014.
DOI : 10.1016/j.ipl.2014.01.005

J. Komlós and E. Szemerédi, Limits distribution for the existence of Hamilton cycles in random graphs, pp.43-55, 1983.

D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, and M. Boguñá, Hyperbolic geometry of complex networks, Physical Review E, vol.82, issue.3, p.36106, 2010.
DOI : 10.1103/PhysRevE.82.036106

M. Krivelevich, The Choice Number of Dense Random Graphs, Combinatorics, Probability and Computing, vol.9, issue.1, pp.19-26, 2000.
DOI : 10.1017/S0963548399004101

M. Krivelevich, B. Sudakov, V. H. Vu, and N. C. Wormald, On the probability of independent sets in random graphs, Random Structures and Algorithms, vol.31, issue.1, pp.1-14, 2003.
DOI : 10.1002/rsa.10063

M. Krivelevich and V. H. Vu, Choosability in Random Hypergraphs, Journal of Combinatorial Theory, Series B, vol.83, issue.2, pp.241-257, 2001.
DOI : 10.1006/jctb.2001.2053

G. Laman, On graphs and rigidity of plane skeletal structures, Journal of Engineering Mathematics, vol.4, issue.4, pp.331-340, 1970.
DOI : 10.1007/BF01534980

C. Lee, J. Lee, and S. Oum, Rank-width of random graphs, Journal of Graph Theory, vol.36, issue.1, pp.339-347, 2012.
DOI : 10.1002/jgt.20620

M. Lelarge, A New Approach to the Orientation of Random Hypergraphs, Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms (SODA) 2012, pp.251-264
DOI : 10.1137/1.9781611973099.23

URL : https://hal.archives-ouvertes.fr/hal-01270322

A. Li and T. Müller, On the treewidth of random geometric graphs and percolated grids The chromatic number of random graphs, Combinatorica, vol.11, pp.45-54, 1991.

C. Mcdiarmid, On the chromatic number of random graphs, Random Structures and Algorithms, vol.7, issue.4, pp.435-442, 1990.
DOI : 10.1002/rsa.3240010404

C. Mcdiarmid and B. Reed, On the Maximum Degree of a Random Planar Graph, Combinatorics, Probability and Computing, vol.9, issue.04, pp.591-601, 2008.
DOI : 10.1016/j.jctb.2004.09.007

C. Mcdiarmid, A. Steger, and D. Welsh, Random planar graphs, Journal of Combinatorial Theory, Series B, vol.93, issue.2, pp.187-205, 2005.
DOI : 10.1016/j.jctb.2004.09.007

A. Mehrabian and N. Wormald, On the Stretch Factor of Randomly Embedded Random Graphs, Discrete & Computational Geometry, vol.49, issue.3, pp.647-658, 2013.
DOI : 10.1007/s00454-012-9482-9

T. Milenkovi´cmilenkovi´c, V. Memi?evi´memi?evi´c, A. Bonato, and N. Pr?ulj, Dominating Biological Networks, Dominating biological networks, p.23016, 2013.
DOI : 10.1371/journal.pone.0023016.g009

D. Mitsche and G. Perarnau, On the treewidth and related parameters of Random Geometric Graphs, STACS Also: SIAM Journal on Discrete Mathematics, vol.2012, pp.408-419
URL : https://hal.archives-ouvertes.fr/hal-00923118

D. Mitsche, X. Pérez-giménez, and P. , Praa lat, Strong-majority bootstrap percolation on regular graphs with low dissemination threshold

D. Mitsche and P. , Praa lat, On the hyperbolicity of random graphs, Electronic Journal of Combinatorics, vol.21, issue.2, pp.2-39, 2014.

D. Mitsche and P. , Revolutionaries and Spies on Random Graphs, Combinatorics, Probability and Computing, vol.43, issue.03, pp.417-432, 2013.
DOI : 10.1016/j.tcs.2008.02.040

URL : https://hal.archives-ouvertes.fr/hal-00923090

D. Mitsche and J. Rué, On the limiting distribution of the metric dimension for random forests, European Journal of Combinatorics, vol.49, pp.68-89, 2015.
DOI : 10.1016/j.ejc.2015.02.029

URL : https://hal.archives-ouvertes.fr/hal-01143653

P. Moisset and I. Rapaport, Strict majority bootstrap percolation on augmented tori and random regular graphs: experimental results, Proceedings of the 20th International Workshop on Cellular Automata and Discrete Complex Systems, p.2014, 2014.

J. W. Moon, On the maximum degree in a random tree, Michigan Math, J, vol.15, issue.4, pp.429-432, 1968.

C. Moukarzel, P. M. Duxbury, and P. L. Leath, First-order rigidity on Cayley trees, Physical Review E, vol.55, issue.5, p.5800, 1997.
DOI : 10.1103/PhysRevE.55.5800

T. Müller, X. Pérez-giménez, and N. Wormald, Disjoint Hamilton cycles in the random geometric graph, Journal of Graph Theory, vol.15, issue.2, pp.299-322, 2011.
DOI : 10.1002/jgt.20560

T. Müller and J. Sereni, Identifying and Locating???Dominating Codes in (Random) Geometric Networks, Combinatorics, Probability and Computing, vol.22, issue.06, pp.925-952, 2009.
DOI : 10.1016/S0304-3975(02)00536-4

S. Muthukrishnan and G. Pandurangan, The bin-covering technique for thresholding random geometric graph properties, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms 2005, pp.989-998

O. Narayan, I. Saniee, and G. Tucci, Lack of spectral gap and hyperbolicity in asymptotic Erd? os- Rényi random graphs, Proceedings of the 5th International Symposium on Communications Control and Signal Processing (ISCCSP) 2012, pp.1-4

J. Ne?et?il, P. Ossona, and . Mendez, Tree-depth, subgraph coloring and homomorphism bounds, European Journal of Combinatorics, vol.27, issue.6, pp.1022-1041, 2006.
DOI : 10.1016/j.ejc.2005.01.010

J. Ne?et?il and S. Shelah, On the order of countable graphs, European Journal of Combinatorics, vol.24, issue.6, pp.649-663, 2003.
DOI : 10.1016/S0195-6698(03)00064-7

F. Papadopoulos, D. Krioukov, M. Boguñá, and A. Vahdat, Greedy forwarding in dynamic scalefree networks embedded in hyperbolic metric spaces, Proceedings of the 29th Conference on Information Communications, INFOCOM 2010, pp.2973-2981

M. Penrose, Connectivity of soft random geometric graphs, The Annals of Applied Probability, vol.26, issue.2
DOI : 10.1214/15-AAP1110

M. Penrose, Onk-connectivity for a geometric random graph, Random Structures and Algorithms, vol.45, issue.2, pp.145-164, 1999.
DOI : 10.1002/(SICI)1098-2418(199909)15:2<145::AID-RSA2>3.0.CO;2-G

M. Penrose, Random Geometric Graphs, Oxford Studies in Probability. Oxford U.P, 2003.
DOI : 10.1093/acprof:oso/9780198506263.001.0001

M. Penrose, The longest edge of the random minimal spanning tree, The Annals of, Applied Probability, vol.7, issue.2, pp.340-361, 1997.

G. Perarnau and O. Serra, On the tree-depth of random graphs, Discrete Applied Mathematics, vol.168, pp.119-126, 2014.
DOI : 10.1016/j.dam.2012.10.031

J. Petit, Layout Problems, 2001.

J. C. Phillips and M. F. Thorpe, Constraint theory, vector percolation and glass formation', Solid State Comm, pp.699-702, 1985.

A. Pothen and S. Toledo, Handbook on data structures and applications, ch. 59, Elimination structures in scientific computing, 2004.

A. J. Rader, B. M. Hespenheide, L. A. Kuhn, and M. F. Thorpe, Protein unfolding: Rigidity lost, Proc. Nat. Acad. Sc. 99, pp.3540-3545, 2002.
DOI : 10.1073/pnas.062492699

I. Rapaport, K. Suchan, I. Todinca, and J. Verstraëte, On Dissemination Thresholds in Regular and Irregular Graph Classes, Algorithmica, vol.31, issue.2, pp.16-34, 2011.
DOI : 10.1007/s00453-009-9309-0

URL : https://hal.archives-ouvertes.fr/hal-00462308

D. Reichman, New bounds for contagious sets, Discrete Mathematics, vol.312, issue.10, pp.1812-1814, 2012.
DOI : 10.1016/j.disc.2012.01.016

N. Robertson and P. D. Seymour, Graph minors. I. Excluding a forest, Journal of Combinatorial Theory, Series B, vol.35, issue.1, pp.39-61, 1983.
DOI : 10.1016/0095-8956(83)90079-5

N. Robertson and P. D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, Journal of Algorithms, vol.7, issue.3, pp.309-322, 1986.
DOI : 10.1016/0196-6774(86)90023-4

M. W. Robinson and N. Wormald, Almost all regular graphs are hamiltonian, Random Structures & Algorithms, vol.31, issue.2, pp.363-374, 1994.
DOI : 10.1002/rsa.3240050209

S. Sabhapandit, D. Dhar, and P. Shukla, Hysteresis in the Random-Field Ising Model and Bootstrap Percolation, Physical Review Letters, vol.88, issue.19, p.197202, 2002.
DOI : 10.1103/PhysRevLett.88.197202

P. Santi and D. M. Blough, An evaluation of connectivity in mobile wireless ad hoc networks, Proceedings International Conference on Dependable Systems and Networks, pp.89-98, 2002.
DOI : 10.1109/DSN.2002.1028890

R. Sasak, Comparing 17 graph parameters, 2010.

F. Sausset, C. Toninelli, G. Biroli, and G. Tarjus, Bootstrap Percolation and Kinetically Constrained Models on Hyperbolic Lattices, Journal of Statistical Physics, vol.100, issue.11, pp.411-430, 2010.
DOI : 10.1007/s10955-009-9903-1

URL : https://hal.archives-ouvertes.fr/hal-00497013

P. Slater, Leaves of trees, Congressus Numerantium, vol.14, pp.549-559, 1975.

S. ¨. Stefánsson and T. Vallier, Majority bootstrap percolation on the random graph G n,p , Preprint available at http

I. Stojmenovic, M. Seddigh, and J. Zunic, Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks, IEEE Transactions on Parallel and Distributed Systems, vol.13, issue.1, pp.14-25, 2002.
DOI : 10.1109/71.980024

I. Streinu and L. Theran, Slider-Pinning Rigidity: a Maxwell???Laman-Type Theorem, Discrete & Computational Geometry, vol.4, issue.2, pp.812-837, 2010.
DOI : 10.1007/s00454-010-9283-y

M. F. Thorpe, Continuous deformations in random networks, Journal of Non-Crystalline Solids, vol.57, issue.3, pp.355-370, 1983.
DOI : 10.1016/0022-3093(83)90424-6

T. Tlusty and J. P. Eckmann, Remarks on bootstrap percolation in metric networks, Journal of Physics A: Mathematical and Theoretical, vol.42, issue.20, p.205004, 2009.
DOI : 10.1088/1751-8113/42/20/205004

C. Toninelli, G. Biroli, and D. S. Fisher, Jamming Percolation and Glass Transitions in Lattice Models, Physical Review Letters, vol.96, issue.3, p.35702, 2006.
DOI : 10.1103/PhysRevLett.96.035702

V. H. Vu, On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs, Journal of Graph Theory, vol.16, issue.3, pp.201-226, 1999.
DOI : 10.1002/(SICI)1097-0118(199907)31:3<201::AID-JGT5>3.0.CO;2-T

M. Walters, Random geometric graphs, Surveys in Combinatorics, pp.365-401, 2011.

N. C. Wormald, Models of random regular graphs, Surveys in Combinatorics, pp.239-298, 1999.

X. Zhu, On-line list colouring of graphs, Electr. J. Combin, vol.16, p.127, 2009.