A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and analysis of Computer Algorithms, 1974.

D. Bauer, F. Harary, J. Nieminen, and C. Suffel, Domination alteration sets in graphs, Discrete Mathematics, vol.47, pp.153-161, 1983.
DOI : 10.1016/0012-365X(83)90085-7

A. Beacham, The complexity of problems without backbones, 2000.

A. Beacham and J. Culberson, On the complexity of unfrozen problems, Discrete Applied Mathematics, vol.153, issue.1-3, 2004.
DOI : 10.1016/j.dam.2005.05.003

C. Berge, Graphs and Hypergraphs, 1973.

B. Bollobás, Graph Theory, 1979.
DOI : 10.1007/978-1-4612-9967-7

B. Bollobás, C. Borgs, J. T. Chayes, J. H. Kim, and D. B. Wilson, The scaling window of the 2-SAT transition, Random Structures & Algorithms, vol.4, issue.97, 1999.
DOI : 10.1002/rsa.1006

J. A. Bondy and U. S. Murty, Graph Theory with Applications, 1976.
DOI : 10.1007/978-1-349-03521-2

E. Boros, M. C. Golumbic, and V. E. Levit, On the number of vertices belonging to all maximum stable sets of a graph, Discrete Applied Mathematics, vol.124, issue.1-3, pp.17-25, 2002.
DOI : 10.1016/S0166-218X(01)00327-4

P. Cheeseman, B. Kanefsky, and W. M. Taylor, Where the really hard problems are, International Joint Conference on Artificial Intelligence, pp.331-337, 1991.

J. Culberson and I. Gent, Frozen development in graph coloring, Theoretical Computer Science, vol.265, issue.1-2, pp.227-264, 2001.
DOI : 10.1016/S0304-3975(01)00164-5

J. Culberson and B. Vandergriend, The G n,m phase transition is not hard for the hamiltonian cycle problem, Journal of Artificial Intelligence Research, vol.9, pp.219-245, 1998.

R. D. Dutton and R. C. Brigham, An extremal problem for edge domination insensitive graphs, Discrete Applied Mathematics, vol.20, issue.2, pp.113-125, 1988.
DOI : 10.1016/0166-218X(88)90058-3
URL : http://doi.org/10.1016/0166-218x(88)90058-3

E. Friedgut, Sharp thresholds of graph properties, and the k-sat problem, Journal of the American Mathematical Society, vol.12, issue.04, pp.1017-1054, 1999.
DOI : 10.1090/S0894-0347-99-00305-7

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPcompleteness, 1979.

I. Gent, E. Macintyre, P. Prosser, and T. Walsh, The constrainedness of search, Proceedings of AAAI-96, pp.246-252, 1996.

G. Gunther, B. Hartnell, and D. F. , Graphs whose vertex independence number is unaffected by single edge addition or deletion, Discrete Applied Mathematics, vol.46, issue.2, pp.167-172, 1993.
DOI : 10.1016/0166-218X(93)90026-K
URL : http://doi.org/10.1016/0166-218x(93)90026-k

P. L. Hammer, P. Hansen, and B. Simeone, Vertices Belonging to All or to No Maximum Stable Sets of a Graph, SIAM Journal on Algebraic Discrete Methods, vol.3, issue.4, pp.511-522, 1982.
DOI : 10.1137/0603052

F. Harary, Graph Theory, 1970.

F. Harary, Changing and unchanging invariants for graphs, Bull. Malaysian Math. Soc, vol.5, pp.73-78, 1982.

T. W. Haynes, L. M. Lawson, R. C. Brigham, and R. D. Dutton, Changing and unchanging of the graphical invariants: minimum and maximum degree, maximum clique size, node independence number and edge independence number, Congressus Numerantium, vol.72, pp.239-252, 1990.

G. Hopkins and W. Staton, Graphs with unique maximum independent sets, Discrete Mathematics, vol.57, issue.3, pp.245-251, 1985.
DOI : 10.1016/0012-365X(85)90177-3

V. E. Levit and E. Mandrescu, Combinatorial properties of the family of maximum stable sets of a graph, Discrete Applied Mathematics, vol.117, issue.1-3, pp.149-161, 2002.
DOI : 10.1016/S0166-218X(01)00183-4

D. L. Mammen and T. Hogg, A new look at the easy-hard-easy pattern of combinatorial search difficulty, Journal of Artificial Intelligence Research, vol.7, pp.47-66, 1997.

C. H. Papadimitriou, Computational Complexity, 1994.

A. Parkes, Clustering at the phase transition, Proceedings of AAAI-97, pp.340-345, 1997.

B. Selman, H. Levesque, and D. Mitchell, A new method for solving hard satisfiability problems, Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), pp.440-446, 1992.

J. Singer, I. P. Gent, and A. Smaill, Backbone fragility and the local search cost peak, Journal of Artificial Intelligence, vol.12, pp.235-270, 2000.

D. P. Sumner and P. Blitch, Domination critical graphs, Journal of Combinatorial Theory, Series B, vol.34, issue.1, pp.65-76, 1983.
DOI : 10.1016/0095-8956(83)90007-2
URL : http://doi.org/10.1016/0095-8956(83)90007-2

J. Zito, The structure and maximum number of maximum independent sets in trees, Journal of Graph Theory, vol.7, issue.2, pp.207-221, 1991.
DOI : 10.1002/jgt.3190150208