J L Fouquet

H Thuillier

J M Vanherpe

A P Wojda

ON (K q , k) STABLE GRAPHS WITH SMALL k

Keywords: Mathematics Subject Classification, 05C35, Stable graphs

A graph G is (Kq, k) (vertex) stable if it contains a copy of Kq after deleting any subset of k vertices. We show that for q ≥ 6 and k ≤ q 2 + 1 the only (Kq, k) stable graph with minimum size is isomorphic to K q+k .

Introduction

For terms not defined here we refer to [START_REF] Bondy | Graph theory[END_REF]. As usually, the order of a graph G is the number of its vertices (it is denoted by |G|) and the size of G is the number of its edges (it is denoted by e(G)). The degree of a vertex v in a graph G is denoted by d G (v), or simply by d(v) if no confusion is possible. For any set S of vertices, we denote by G -S the subgraph induced by V (G) -S. If S = {v} we write G -v for G -{v}. When e is an edge of G we denote by G -e the spanning subgraph (V (G), E -{e}). The disjoint union of two graphs G 1 and G 2 is denoted by G 1 +G 2 . The union of p mutually disjoint copies of a graph G is denoted by pG. A complete subgraph of order q of G is called a q-clique of G. The complete graph of order q is denoted by K q . When a graph G contains a q-clique as subgraph, we say "G contains a K q ". The following notion was introduced by Dudek et al. in [START_REF] Dudek | H, k) stable graphs with minimum size[END_REF]. Definition 1.1. Let H be a graph and k be a natural number. A graph G of order at least k is said to be a (H, k) stable graph if for any set S of k vertices the subgraph G -S contains a graph isomorphic to H.

By Q(H, k) we denote the size of a minimum (H, k) stable graph. It is clear that if G is an (H, k) stable graph with minimum size then the graph obtained from G by addition or deletion of some isolated vertices is also minimum (H, k) stable. Hence we shall asume that all the graphs considered in the paper have no isolated vertices. A (H, k) stable graph with minimum size shall be called a minimum (H, k) stable graph.

Lemma 1.2. [START_REF] Dudek | H, k) stable graphs with minimum size[END_REF] Let q and k be integers,

q ≥ 2, k ≥ 1. If G is (H, k) stable then, for every vertex v of G, the graph G -v is (H, k -1) stable. Proposition 1.3. [2] If G is a (H, k) stable
graph with minimum size then every vertex as well as every edge is contained in a subgraph isomorphic to H.

Proof.

Let e be an edge of G which is not contained in any subgraph of G isomorphic to H, then G -e would be a (H, k) stable graph with less edges than G, a contradiction. Let x be a vertex of G and e be an edge of G incident with x, since e is an edge of some subgraph isomorphic to H, say H 0 , the vertex x is a vertex of H 0 .

Preliminary results

We are interested by minimum (K q , k) stable graphs (where q and k are integers such that q ≥ 2 and k ≥ 0). As a corollary to Proposition 1.3, every edge and every vertex of a minimum (K q , k) stable graph is contained in a K q (thus the minimum degree is at least q -1). Note that, for q ≥ 2 and k ≥ 0, the graph

K q+k is (K q , k) stable, hence Q(K q , k) ≤ ( q+k 2
) .

Definition 2.1. Let H be a non complete graph on q + t vertices (t ≥ 1). We shall say that H is a near complete graph when it has a vertex v such that

• H -v is complete. • d H (v) = q + r with -1 ≤ r ≤ t -2.
The previous definition generalizes Definition 1.5 in [START_REF] Fouquet | On (Kq, k) vertex stable graphs with minimum size[END_REF] initially given for r ∈ {-1, 0, 1} and the following lemma generalizes Proposition 2.1 in [START_REF] Fouquet | On (Kq, k) vertex stable graphs with minimum size[END_REF].

Lemma 2.2. Every minimum (K q , k) stable graph G, where q ≥ 3 and k ≥ 1, has no component H isomorphic to a near complete graph.

Proof. Suppose, contrary to our claim, that G has such a component H and let v be the vertex of

H such that H -v is a clique of G. Then, H has q + t vertices with q -1 ≤ d(v) ≤ q + t -2 and d(v) = q + r. Since G is minimum (K q , k) stable, G -v is (K q , k -1)
stable and is not (K q , k) stable. Then, G -v contains a set S with at most k vertices intersecting every subgraph of G -v isomorphic to a K q . The graph G -S contains some K q (at least one) and clearly every subgraph of G -S isomorphic to a K q contains v. Since N (v) is a K q+r and N (v) -S contains no K q , |N (v) -S| ≤ q -1. Since there exists a K q containing v in H -S,

|N (v) -S| = q -1 (and hence |S ∩ N (v)| = r + 1). Since H -v -S contains no K q , H -v -S = N (v) -S.
Let a be a vertex of H -v not adjacent to v and let b be a vertex in N (v) -S, and consider S = S -{a} + {b}. We have | S |≤ k and G -S contains no K q , a contradiction.

It is clear that Q(K q , 0) = ( q 2
) and the only minimum (K q , 0) stable graph is K q . It is an easy exercise to see that Q(K 2 , k) = k + 1 and that the matching (k + 1)K 2 is the unique minimum (K 2 , k) stable graph. Theorem 2.3. [START_REF] Fouquet | On (Kq, k) vertex stable graphs with minimum size[END_REF] Let G be a minimum (K 3 , k) stable graph, with k ≥ 0. Then G is isomorphic to sK 4 + tK 3 , for any choice of s and t such that 2s + t = k + 1.

In [START_REF] Fouquet | On (Kq, k) vertex stable graphs with minimum size[END_REF] it was proved that if q ≥ 4 and k ∈ {1, 2} then

Q(K q , k) = ( q+k 2 )
and the only minimum (K q , k) stable graph is K q+k . We have proved also that if q ≥ 5 then

Q(K q , 3) = ( q+3 2
) and the only minimum (K q , 3) stable graph is K q+3 . Dudek, Szymański and Zwonek proved the following result.

Theorem 2.4. [START_REF] Dudek | H, k) stable graphs with minimum size[END_REF] For every q ≥ 4, there exists an integer k(q) such that

Q(K q , k) ≤ (2q -3)(k + 1) for k ≥ k(q).
As a consequence of this last result, they have deduced that for every k ≥k(q) K q+k is not minimum (K q , k) stable.

Remark 2.5. From now on, throughout this section we assume that q and k are integers such that q ≥ 4, k ≥ 1 and for every r such that 0 ≤ r < k we have

Q(K q , r) = ( q+r 2 )
and the only minimum (K q , r) stable graph is K q+r .

In view of Theorem 2.4, k is bounded from above and we are interested to obtain the greatest possible value of k.

Lemma 2.6. Let G be a (K q , k) stable graph such that e(G) ≤ ( q+k 2
)

. Then either for every vertex v we have

d(v) ≤ q + k -2 or G is isomorphic to K q+k .
Proof. Suppose that some vertex v has degree at least

q + k -1. By Lemma 1.2 the graph G -v is (K q , k -1) stable, hence Q(K q , k -1) ≤ e(G -v) = e(G) -d(v). Since Q(K q , k -1) = ( q+k-1 2 )
, we have

( q+k-1 2 ) ≤ e(G) -d(v) ≤ ( q+k 2 ) -(q + k -1) = ( q+k-1 2 ) . It follows that e(G-v) = ( q+k-1 2 ) , G-v is isomorphic to K q+k-1 and d(v) = q+k-1. Hence, G is isomorphic to K q+k . Lemma 2.7. Let G be a minimum (K q , k) stable graph. Then one of the following statements is true • G has no component isomorphic to K q • Q(K q , k -1) + ( q 2 ) ≤ Q(K q , k) Proof. Suppose that some component H of G is isomorphic to a K q . If G -H is not (K q , k -1)
stable, then there is a set S with at most k -1 vertices intersecting each K q of G -H. Then, for any vertex a of H, S + a intersects each K q of G while S has at most k -1 vertices, a contradiction. Hence G -H is (K q , k -1) stable and we have

Q(K q , k -1) ≤ e(G -H) = Q(K q , k) - ( q 2
) .

Lemma 2.8. [START_REF] Fouquet | On (Kq, k) vertex stable graphs with minimum size[END_REF] Let G be a minimum (K q , k) stable graph and let u be a vertex of degree q -1. Then one of the following statements is true

• ∀v ∈ N (u) d(v) ≥ q + 1 • Q(K q , k -1) + 3(q -2) ≤ Q(K q , k) Proof.
By Proposition 1.3, since d(u) = q -1, {u} + N (u) induces a complete graph on q vertices. Assume that some vertex w ∈ N (u) has degree q + r where r = -1 or r = 0, and let v be a neighbour of u distinct from w. Since the degree of u in G -v is q -2, no edge incident with u can be contained in a

K q of G -v. Since G -v is (K q , k -1) stable, we can delete the q -2 edges incident with u in G -v and the resulting graph G is still (K q , k -1) stable. By deleting v, we have e(G -v) ≤ e(G) -(q -1) and hence e(G ) ≤ e(G) -(q -1) -(q -2) .
In G , the degree of w is now q + r -2. Hence, no edge incident with w in G can be contained in a K q . Deleting these q + r -2 edges from G leads to a graph G " which remains to be (K q , k -1) stable. We get thus

Q(K q , k -1) ≤ e(G ) ≤ e(G) -(q -1) -(q -2) -(q + r -2) .
Since e(G) ≤ Q(K q , k), the result follows.

Lemma 2.9. Let G be a minimum (K q , k) stable graph, where 1 ≤ k ≤ 2q -6, and let v be a vertex of degree q -1. Then for every vertex w ∈ N (v) we have d(w) ≥ q + 1.

Proof. Suppose, contrary to the assertion of the lemma, that d(w) ≤ q for some vertex w ∈ N (v). By Lemma 2.8, we have

Q(K q , k -1)+3(q -2) ≤ Q(K q , k). Since Q(K q , k -1) = ( q+k-1 2 ) and Q(K q , k) ≤ ( q+k 2 )
we have

( q+k-1 2 ) + 3q -6 ≤ ( q+k 2
) . Then we obtain k ≥ 2q -5, a contradiction. Lemma 2.10. Let G be a minimum (K q , k) stable graph, where q ≥ 5 and 1 ≤ k ≤ q -1. Then the minimum degree of G is at least q.

Proof. Suppose that there is a vertex v of degree q -1 and let w be a neighbour of v. Since q -1 ≤ 2q -6, by Lemma 2.9, w has degree at least q + 1. By Lemma 1.2 the graph G -w is (K q , k -1) stable. In that graph v is not contained in any K q since its degree is q -2. Hence G -{w, v} is still (K q , k -1) stable. We have

e(G-{w, v}) = e(G)-(d(v)+d(w)-1) ≤ e(G)-2q+1. Since Q(K q , k-1) = ( q+k-1 2 ) and Q(K q , k) ≤ ( q+k 2 )
we have

( q+k-1 2 ) ≤ e(G) -2q + 1 ≤ ( q+k 2 ) -2q + 1. It follows that k ≥ q, a contradiction.
Lemma 2.11. Let G be a minimum (K q , k) stable graph, where q ≥ 5 and 1 ≤ k ≤ q -1, and let v be a vertex of degree q. Then N (v) is complete.

Proof.

Assume, by contradiction, that v is a vertex of degree q and N (v) contains two non adjacent vertices a and b. Let w ∈ N (v) distinct from a and b (w must exist since q ≥ 4). By Lemma 1.2 the graph G -w is (K q , k -1) stable. In that graph v is not contained in a K q since its two neighbours a and b are not adjacent. Hence G -{w, v} is still (K q , k -1) stable. By Lemma 2.10, d(w) ≥ q and hence e(G -{w, v}) = e(G) -(d(v) + d(w) -1) ≤ e(G) -2q + 1. We have, as in the proof of Lemma 2.10,

( q+k-1 2 ) ≤ e(G) -2q + 1 ≤ ( q+k 2
) -2q + 1, and we obtain k ≥ q, a contradiction. Lemma 2.12. Let G be a minimum (K q , k) stable graph, where q ≥ 4 and 2 ≤ k ≤ q 2 + 1, and let v be a vertex of degree at least q + 1. Then either N (v) induces a complete graph or there exists an ordering v 1 , . . . , v d(v) of the vertices of N (v) such that {v 1 , . . . , v q-1 } induces a complete graph and

v d(v)-1 v d(v) is not in E(G). Moreover, there exists a vertex w in {v 1 , . . . , v q-1 } adjacent to v d(v)-1 and v d(v) .

Proof.

Suppose that the subgraph induced by N (v) is not complete and let a and b be two non adjacent neighbours of v. Assume that every complete graph on q -1 vertices contained in N (v) intersects {a, b}. The graph G -{a, b} is (K q , k -2) stable. In that graph, v is not contained in a K q , hence G -{a, b, v} is still (K q , k -2) stable. We have e(G -{a, b, v}

) = e(G) -(d(v) + d(a) + d(b) -2) ≤ e(G) -3q -1. Since Q(K q , k -2) = ( q+k-2 2 ) and Q(K q , k) ≤ ( q+k 2 )
, we have

( q+k-2 2 ) ≤ e(G -{a, b, v}) ≤ e(G) -3q -1 ≤ ( q+k 2 ) -3q -1 and hence q 2 + 2 ≤ k, a contradiction with k ≤ q 2 + 1.
Thus, N (v) -{a, b} contains a K q-1 and we can order the vertices of N (v) in such a way that the q -1 first ones v 1 , . . . , v q-1 induce a complete graph and the two last vertices v d(v)-1 and v d(v) are not adjacent, as claimed. Set d(v) = q + r with r ≥ 1. By Proposition 1.3, the edges vv q+r-1 and vv q+r are contained in two distinct q-cliques, say Q 1 and Q 2 . Since v q+r-1 and v q+r are not adjacent, each Q i contains at most r vertices in N (v) -{v 1 , . . . , v q-1 }. Hence, each

Q i must have at least q -r -1 vertices in {v 1 . . . v q-1 }. Since N (v) is not complete and e(G) ≤ ( q+k 2 )
, by Lemma 2.6 we have

r ≤ k -2. Since k ≤ q 2 + 1, Q 1 (as well as Q 2 ) has at least q -r -1 ≥ q -k + 1 ≥ q 2 vertices in {v 1 . . . v q-1 }.
Hence Q 1 and Q 2 have at least one common vertex w in N (v), and the lemma follows.

Lemma 2.13. Let G be a minimum (K q , k) stable graph, where q ≥ 5 and 2 ≤ k ≤ q 2 + 1, and let H be a component of G. Assume that v is a vertex of maximum degree in H. Then either H is complete or the subgraph induced by N (v) contains no complete subgraph on d(v) -1 vertices.

Proof.

Assume that H is not complete. First, we prove that the maximum degree in H is at least q + 1. If the minimum degree in H is at least q + 1, we are done. If there exists a vertex u of degree q -1 in H then, by Lemma 2.9, the degree of any vertex of N (u) is at least q + 1. If there exists a vertex u of degree q then, by Lemma 2.11, N (u) ∪ {u} induces a K q+1 , and hence, since H is connected, there exists a vertex in H -(N (u) ∪ {u}) having at least one neighbour w in N (u) and d(w) ≥ q + 1. Thus, the maximum degree in H is q + r with r ≥ 1. Since H is not complete and v is a vertex of maximum degree in H, the subgraph induced on N (v) is not complete. By Lemma 2.12, there exists an ordering {v 1 . . . v q+r } of the vertices of N (v) such that {v 1 . . . v q-1 } induces a complete graph and v q+r-1 v q+r is not an edge of G. If the subgraph induced by N (v) contains a complete subgraph on q + r -1 vertices then without loss of generality we may suppose that it contains the vertex v q+r-1 . Assume that {v 1 , . . . , v q+r-2 , v q+r-1 } induces a complete graph. Since G is a minimum (K q , k) stable graph, by Proposition 1.3, the edge vv q+r must be contained in a K q . Hence v q+r has at least q -2 neighbours in {v 1 , . . . , v q+r-2 }. Let us denote by A this set of neighbours. Since the subgraph induced by (N (v) -{v q+r }) is complete, every vertex in A has degree q + r in G (let us say that these vertices are saturated). Henceforth, every vertex in A has no neighbour outside N (v) ∪ {v}. By Lemma 2.2, the (q + r)-clique (N (v) -{v q+r }) ∪ {v} is a proper subgraph of H -{v q+r }. Since H is connected, there exists a vertex w outside N (v) ∪ {v} adjacent to a vertex u in N (v). Clearly, the vertex u has also degree q + r and it has no other neighbour outside N (v) ∪ {v} than w. The edge uw being contained in a K q by Proposition 1.3, w must have at least q -2 common neighbours with u in N (v). Let us denote by B the set of neighbours of w in N (v). It is easy to see that every vertex in B is saturated. Since A and B are disjoint, we have 2q -3 ≤ |A ∪ B| ≤ |N (v)| = q + r and hence q ≤ r + 3. Since r ≤ k -2 by Lemma 2.6, we have q ≤ k + 1. Thus, we obtain q ≤ q 2 + 2, which implies q ≤ 4, a contradiction. Hence the subgraph induced by the vertices {v 1 , . . . , v q+r-2 , v q+r-1 } is not complete, and the lemma follows.

Proposition 2.14. Let G be a minimum (K q , k) stable graph, where q ≥ 6 and 2 ≤ k ≤ q 2 + 1. Then every component of G is a complete graph. Proof. Let H be a component of G and v be a vertex of maximum degree in H. If the subgraph induced on N (v) is complete then H is obviously complete. We can thus suppose that N (v) is not a clique. By Lemmas 2.10 and 2.11, the minimum degree is at least q + 1, and hence d(v) = q + r with r ≥ 1.

Claim 2.14.1. The graph G -(N (v) ∪ {v}) is (K q , k -r) stable.
Proof By Lemma 2.12, we can consider an ordering v 1 , . . . , v q+r of N (v) such that the set {v 1 , . . . , v q-1 } induces a K q-1 , v q+r-1 v q+r ∈ E(G) and there is a vertex w ∈ {v 1 , . . . , v q-1 } adjacent to v q+r-1 and v q+r . By Lemma 2.13, we can find two non adjacent vertices a and b in N (v) -{v q+r } and two non adjacent vertices c and d in N (v) -{v q+r-1 }. Let us note that since the set {v 1 , . . . , v q-1 } induces a complete graph, it contains at most one vertex of the set {a, b} and at most one vertex of {c, d}. Then, |{v 1 , . . . , v q-1 } ∩ {w, a, b, c, d}| ≤ 3. Since H is not complete, the graph G is not complete and by Lemma 2.6 we have r ≤ k -2. Since k ≤ q 2 + 1 and q ≥ 6, there exists a subset A ⊆ {v 1 . .

. v q-1 } such that • |A| = r • w ∈ A • A ∩ {a, b, c, d} = ∅ By repeated applications of Lemma 1.2, the graph G 1 obtained from G by deleting A is (K q , k -r) stable. In G 1 , the degree of v is equal to q.
Without loss of generality, suppose that a is distinct from v q+r-1 and c is distinct from v q+r . If there exists a q-clique in G 1 containing the edge vv q+r-1 then {v 1 , . . . , v q+r-2 } -A is a (q -2)-clique containing a. Since ab is not an edge, we must have b = v q+r-1 , a contradiction to the fact that av q+r-1 is an edge. Thus, there is no q-clique in G 1 containing vv q+r-1 . Analogously, we prove that there is no q-clique in G 1 containing vv q+r . Hence, the graph G 2 obtained from G 1 by deletion of the edges vv q+r-1 and vv q+r is still (K q , k -r) stable. In G 2 , v has degree q -2, so it is not contained in any K q . We can thus delete v and we get a (K q , k -r) stable graph G 3 . Since the maximum degree in G is q + r, the degree of w in G 3 is at most q -1. Recall that w is adjacent to the two non adjacent vertices v q+r-1 and v q+r . Hence w is not contained in any K q of G 3 , which means that G 4 = G 3 -w is still (K q , k-r) stable. Since the degree of each vertex in {v 1 , . . . , v q-1 } -(A ∪ {w}) is at most q -2 in G 4 , none of these vertices can be contained in any K q of G 4 . Hence by deletion of these vertices we get again a (K q , k -r) stable graph G 5 . We shall prove that none of the r + 1 vertices v q , . . . , v q+r is contained in a K q of G 5 . Note that G 5 = G-{v, v 1 , ..., v q-1 }. For q ≤ j ≤ q+r, denote by d j the degree of the vertex v j in the subgraph induced by {v q , . . . , v q+r }. Clearly we have 0 ≤ d j ≤ r. In G, by Proposition 1.3, the edge vv j is contained in a K q . Hence v j is adjacent (in G) to at least q-2-d j vertices in {v 1 , . . . , v q-1 }. Since we have deleted the vertex v and the vertices v 1 , . . . , v q-1 , we have thus d G5 (v j ) ≤ q+r-(q-2-d j )-1 = r+1+d j . If d j ≤ r -1 then d G5 (v j ) ≤ 2r ≤ 2(k -2) ≤ q -2 and there is no K q in G 5 containing v j . The equality d G5 (v j ) = q -1 can only be obtained when d j = r, that is v j has r neighbours in v q . . . v q+r . Since v q+r-1 and v q+r are not adjacent, v j is not contained in any K q of G 5 .

The research of APW was partially sponsored by polish Ministry of Science and Higher Education.

Hence, the graph G 6 = G -(N (v) ∪ {v}) obtained from G 5 by deletion of all the vertices v q , v q+1 . . . , v q+r is still (K q , k -r) stable, and the claim follows.

Claim 2.14.2.

(2.1)

we add, at least

edges of the (q -1)-clique induced by the set {v 1 . . . v q-1 }, • the edges incident with v q , . . . , v q+r and not incident with v.

Let l be the number of edges incident with v q , . . . , v q+r and not incident with v. We have

In order to find a lower bound of the number of edges incident with the vertices v q , . . . , v q+r , for each i ∈ {q, . . . , q + r} let us denote by d i the degree of the vertex v i in the subgraph induced by the set {v q , . . . , v q+r }. Then,

Since by Lemma 2.10 the minimum degree in G is at least q, we have

Since for every i in {q, . . . , q + r -2} d i ≤ r, d q+r-1 ≤ r -1 and d q+r ≤ r -1, we obtain

and hence

By the assumption made at the beginning of the section (see Remark 2.5), a minimum (K q , k -r) stable graph has

, the inequality (2.1) follows from Claim 2.14.1 and the inequality (2.2).

A simple calculation shows that the inequality q 2 + q + 2 ≤ 2kr can be obtained by starting from the inequality (2.1). Since r ≤ k -2 and k ≤ q 2 + 1, we have q 2 + q + 2 ≤ 2k(k -2) ≤ (q + 2)( q 2 -1), hence q 2 2 + q + 4 ≤ 0, a contradiction. Thus, N (v) is a clique and the proposition follows.

Result

In [START_REF] Fouquet | On (Kq, k) vertex stable graphs with minimum size[END_REF], it is shown that if G is minimum (K q , k) stable and the numbers k and q verify one of the following conditions:

• k = 1 and q ≥ 4 • k = 2 and q ≥ 4 • k = 3 and q ≥ 5 then G is isomorphic to K q+k . Theorem 3.1. Let G be a minimum (K q , k) stable graph, where q ≥ 6 and k

and suppose that for every r with 0 ≤ r < k the only minimum (K q , r) stable graph is K q+r . By Proposition 2.14, the graph G is the disjoint union of p complete graphs

0 and that there exist two components H i and H j with i < j such that k i -k j ≥ 2. By substituting

, which is a contradiction. Thus, for any i and any j, 0

To conclude that G has a unique component, observe the following facts.

• The graphs 2K q+l and K q+2l+1 are both (K q , 2l + 1) stable, but if 2l + 1 ≤ q 2 + 1 then

• The graphs K q+l ∪ K q+l+1 and K q+2l+2 are both (K q , 2l + 2) stable but if 2l + 2 ≤ q 2 + 1 then


J-L Fouquet

H Thuillier

J-M Vanherpe

A P Wojda

Al Mickiewicza

On (K q , k) vertex stable graphs with minimum size

Keywords:

A graph G is a (K q , k) vertex stable graph if it contains a K q after deleting any subset of k vertices. We give a characterization of (K q , k) vertex stable graphs with minimum size for q = 3, 4, 5.

Introduction

For terms not defined here we refer to [START_REF] Bondy | Graph theory[END_REF]. As usually, the order of a graph G is the number of its vertices (it is denoted by |G|) and the size of G is the number of its edges (it is denoted by e(G)). A complete subgraph of order q of G is called a q-clique of G.

The complete graph of order q is denoted by K q . When a graph G contains a q-clique as subgraph, we say "G contains a K q ". The union of p mutually disjoint copies of K q is denoted by pK q . When A is a set of vertices we denote by G -A the subgraph induced by V (G) -A.

In [START_REF] Katona | Extremal stable graphs[END_REF] Horwárth and G.Y Katona consider the notion of (H, k) stable graph: given a simple graph H, an integer k and a graph G containing H as subgraph, G is a a (H, k) stable graph whenever the deletion of any set of k edges does not lead to a H-free graph. These authors consider (P n , k) stable graphs and prove a conjecture stated in [START_REF] Frankl | Extremal k-edge hamiltonian hypergraphs[END_REF] on the minimum size of a (P 4 , k) stable graph. In [START_REF] Dudek | H, k) stable graphs with minimum size[END_REF], Dudek, Szymański and Zwonek are interested in a vertex version of this notion and introduce the (H, k) vertex stable graphs. 1 The research of APW was partially sponsored by polish Ministry of Science and Higher Education.

Preprint submitted to Discrete Mathematics

November [START_REF] Bondy | Graph theory[END_REF]2010 since H is not complete we must have p ≥ 2 when d H (u) = q + 1 and p ≥ 1 when

d H (u) = q. u N R K q+p
Figure 1: A near complete graph (R,N,u) on q + p + 1 vertices

Preliminary results

Proposition 2.1. Let G = (V, E) be a (K q , k) stable graph with minimum size (q ≥ 3).

Then G has no component isomorphic to a near complete graph (R,N,u) on q + p + 1 vertices.

Proof Suppose, by contradiction, that there exists such a component H = (R, N, u) on q + p + 1 vertices with d H (u) = q + ( ∈ {-1, 0, 1}). Since G is a (K q , k)-stable graph with minimum size, G -{u} is not (K q , k)-stable. There exists a set S with at most k vertices such that S intersects every K q of G -{u}. There exists a K q in G -S and clearly such a K q contains u. Since N is a K q+ and N -S contains no K q , |S ∩N | ≥ +1

(trivial for = -1). If |S ∩ N | ≥ + 2 then |N -S| ≤ q -2, and hence S intersects every K q containing u, a contradiction. Thus, |S ∩ N | = + 1 and |N -S| = q -1. If there exists v in R -S then (N -S) + {v} is a K q in G -{u}, a contradiction. Thus, R ⊂ S.

Let a ∈ R and b ∈ N -S, and set S = S -{a} + {b}. We have | S |≤ k and G -S contains no K q , a contradiction.

Lemma 2.2. Let G = (V, E) be a minimum (K q , k) (q ≥ 3 and k ≥ 1) stable graph and let u be a vertex of degree q -1 then one of the following statements is true

• ∀v ∈ N (u) d(v) ≥ q + 1.
• Q(K q , k -1) + 3(q -2) ≤ Q(K q , k).

Proof Since d(u) = q -1, {u} + N (u) induces a complete graph on q vertices. Assume that some vertex w ∈ N (u) has degree q + a (a = -1 or a = 0) and let v ∈ N (u) distinct from w. Then G -v is a (K q , k -1) stable graph (Lemma 1.4). Since the degree of u in G -{v} is q -2, no edge incident with u can be contained in a K q . We can thus delete these q -2 edges and the resulting graph (say G ) is still a (K q , k -1) stable graph.

In G , the degree of w is now q + a -2. Hence, no edge incident with w in G can be contained in a K q . Deleting these q + a -2 edges from G leads to a graph G " which remains to be a (K q , k -1) stable graph.

By deleting v, we have e(G -{v}) ≤ e(G) -(q -1) and hence

e(G ) ≤ e(G) -(q -1) -(q -2).
We get thus

Q(K q , k -1) ≤ e(G ) ≤ e(G) -(q -1) -(q -2) -(q + a -2).
Since e(G) = Q(K q , k), the result follows.

Proposition 2.3. Let G = (V, E) be a minimum (K q , 1) stable graph (q ≥ 4) then G is isomorphic to K q+1 .
Proof Let G be a minimum (K q , 1) stable graph. Since K q+1 is (K q , 1) stable, clearly

e(G) ≤ ( q+1 2
)

. We can assume that G is connected. Otherwise, each component contains

a K q , but ( q+1 2 ) < 2 ( q 2 )
as soon as q ≥ 4, a contradiction. Let u be a vertex of G and Q be a subgraph of G -{u} isomorphic to K q . Assume that there exists a vertex v outside Q and distinct from u. Note that v can be a neighbour of u.

Since d(u) ≥ q -1 and d(v) ≥ q -1, e(G) ≥ e(Q) + 2(q -1) -1 = ( q 2 ) + 2q -3 = ( q+1 2 ) + q -3. Thus, e(G) > e(K q+1 ), a contradiction. Hence, V (G) = V (Q)∪{u} with d(u) ≥ q -1. Since for
any edge e K q+1 -{e} is not (K q , 1) stable, we see that

d(u) = q, that is G is isomorphic to K q+1 .
Remark 2.4. It is easy to see that the minimum (K 3 , 1) stable graphs are 2K 3 and K 4 .

Proposition 2.5. Let G = (V, E) be a minimum (K q , 2) stable graph (q ≥ 4) then G is isomorphic to K q+2 .
Proof Since K q+2 is a (K q , 2) stable graph, we can suppose that G has at most

( q+2 2 )
edges. We can suppose, moreover, that G is not complete, otherwise G is obviously reduced to K q+2 . Let u be a vertex of minimum degree (recall that the minimum degree is at least q -1) and let v be one of its neighbours.

Assume that d G (u) = q -1. G -{v} is a (K q , 1) stable graph, but it is not minimum, since none of the remaining edge incident with u can be contained in a complete graph on q vertices. By deleting the q -2 edges incident with u, we get thus a (K q , 1) stable graph.

If d(v) ≥ q + 1, this graph has at most (

) -(2q -1) edges. Since this number of edges must be greater than (

) by Proposition 2.3, we have (q + 2)(q + 1) -4q + 2 ≥ (q + 1)q That leads to q ≤ 2, a contradiction. If d(v) ≤ q, by Lemma 2.2, we have Q(K q , 1) + 3q -6 ≤ Q(K q , 2) and hence q(q + 1) + 6q -12 ≤ (q + 1)(q + 2)

Which gives q ≤ 3, a contradiction.

We can thus assume that the minimum degree of G is at least q. Let u and v be two non adjacent vertices of G. Since G -{u, v} contains a K q (say Q), let a and b be two distinct vertices of Q. Since G -{a, b} must contain also a K q , there is certainly a vertex w distinct from v and u, outside Q, inducing with q -1 other vertices of G -{a, b} a K q .

Hence G contains three vertices (u, v and w) at least in G -Q and we have:

( q + 2 2 ) ≥ e(G) ≥ ( q 2 ) + 3q -2
Which gives q < 3, a contradiction. Hence G is complete and the proposition follows.

Lemma 2.6. Let G be a minimum (K q , 3) stable graph, q ≥ 5. Let u be a vertex of minimum degree in G and suppose that d G (u) = q + l, where -1 ≤ l ≤ 1. Then for every

neighbour v of u we have d G (v) ≥ q + l + 2.
Proof Suppose, contrary to our claim, that d G (v) ≤ q + l + 1 for a neighbour v of u.

Since, by Proposition 1.2, the edge uv is contained in a clique of order q and q ≥ 5, there is a set A of vertices of G such that |A| = l + 2 and the vertices of the set A ∪ {u, v} are mutually adjacent. The graph G = G -A is (K q , 3 -(l + 2)) stable. We have

d G (u) = q + l -(l + 2) = q -2, hence also G = G -{u} is (K q , 1 -l) stable. But in G the degree of the vertex v is at most q -2 and therefore G = G -{v} is (K q , 1 -l)
stable. Since every vertex of the set A ∪ {u, v} has at least q -3 neighbours outside this set, we have

( q + 1 -l 2 ) ≤ e(G ) ≤ ( q + 3 2
) -(l + 4)(q -3) - ( l + 4 2
)

which contradicts q ≥ 5. Proposition 2.7. Let G = (V, E) be a minimum (K q , 3) stable graph (q ≥ 5) then G is isomorphic to K q+3 .
Proof Note first that to prove the proposition it is sufficient to prove that every vertex of G has the degree at least q + 2.

Let u be a vertex of the minimum degree in G and suppose, contrary to our claim, that

d G (u) ≤ q + l, where -1 ≤ l ≤ 1.
Let v 1 , v 2 , ..., v l+2 be such vertices of G that the set {u, v 1 , v 2 , ..., v l+2 } induce a clique in G (such vertices exist since u is contained in a clique of order q by Proposition 1.2 and q ≥ 5). By Lemma 2.6, we have

d G (v i ) ≥ q + l + 2 for i = 1, 2, ..., l + 2. Set G = G -{v 1 , v 2 , ..., v l+2 }. The graph G is clearly (K q , 1 -l) stable. Moreover, since d G (u) = q -2, the graph G = G -{u} is also (K q , 1 -l) stable and we have ( q + 1 -l 2 ) ≤ e(G ) ≤ ( q + 3 2
) -(l + 2)(q -1) -(q -2) - ( l + 3 2
) which contradicts q ≥ 5.

A characterization of (K 3 , k) stable graph with minimum size

Dudek, Szymański and Zwonek in [START_REF] Dudek | H, k) stable graphs with minimum size[END_REF] have shown that Q(K 3 , k) = 3k + 3 for every nonnegative integer k. In this section we characterize all that (K 3 , k) stable graphs with minimum size.

Clearly, K 3 is the unique minimum (K 3 , 0) stable graph, and by Remark 2.4, the minimum (K 3 , 1) stable graphs are 2K 3 and K 4 .

The following theorem characterize all graphs which are (K 3 , k) stable with minimum size.

Theorem 3.1. Let G = (V, E) be a (K 3 , k) stable graph with minimum size. Then G is isomorphic to pK 4 +qK 3 , where p and q are such nonnegative integers that 2p+q = k +1.

Proof

By Remark 2.4, K 3 is the unique minimum (K 3 , 0) stable graph, and the minimum (K 3 , 1) stable graphs are 2K 3 and K 4 . Clearly, the graph (k + 1)K 3 is a (K 3 , k) stable graph and has 3k + 3 edges. Let k 0 ≥ 1 and suppose that for every k < k 0 every minimum (K 3 , k) stable graph is a union of p copies of K 4 and q copies K 3 with

2p + q = k + 1.
Let G be a (K 3 , k 0 ) stable graph of minimum size. Since G -{v} is (K 3 , k 0 -1) stable for every vertex v, we have 3k

0 ≤ e(G -{v}) ≤ e(G) -d G (v) ≤ 3k 0 + 3 -d G (v), that is d G (v) ≤ 3.
If every vertex of G has degree equal to 2, then G is a union of k 0 + 1 copies of K 3 , and the theorem is proved. So we may suppose that there is a vertex v 0 of degree

3. But then G -{v 0 } is (K 3 , k 0 -1) stable and e(G -{v 0 }) = 3k o , that is G -{v 0 } is minimum (K 3 , k 0 -1) stable. By the induction hypothesis, G -{v 0 } is isomorphic to p K 4 + q K 3 , where 2p + q = k 0 .
It is clear that all the neighbours of v 0 are in the same component of G, (otherwise one of the edges incident with v 0 is not contained in any triangle, contrary to Proposition 1.2). Now it is easy to see that G is isomorphic to (p + 1)K 4 + (q -1)K 3 and 2(p + 1) + (q -1) = k 0 + 1 (otherwise there is a set A of cardinality k 0 which is transversal of all cliques of order 3 in G).

A characterization of (K 4 , k) stable graph with minimum size

In [START_REF] Dudek | H, k) stable graphs with minimum size[END_REF] the minimum number of edges of a (K 4 , k) stable graph is given. Suppose first that there is a vertex

Theorem 4.1. [2] Let G = (V, E) be a (K 4 , k) stable graph with minimum size (k ≥ 1) then • Q(K 4 , 0) = 6. • Q(K 4 , k) = 5k + 5 when k ≥ 1. Proposition 4.2. Let G = (V, E) be a (K 4 , k) stable graph with minimum size if k ≥ 1 then G as no component isomorphic to K 4 . Proof Let us consider k ≥ 2. Assume that some component H of G is isomorphic to a K 4 with the vertices of H being a, b, c, d. Then G -H has 5k -1 edges. Since G -H is not a (K 4 , k -1)
v in G such that d G (v) = 5. Then G -{v} is (K 4 , k 0 -1) stable and moreover, since e(G -v) = 5k 0 , G -{v} is minimum (K 4 , k 0 -1) stable. Hence every component of G -{v} is either isomorphic to K 5 or to K 6 . If v is connected in G to a K 6 ,
u 1 u 4 ∈ E(G). Then the component containing v is a K 5 . case 2: u 1 u 4 ∈ E(G).
Let w be a new vertex adjacent to u 1 (this new vertex must exist since the component of v is 4-regular). Then u 1 w cannot be contained in a K 4 , a contradiction.

A characterization of (K 5 , k) stable graph with minimum size

In this section we provide the value of Q(K 5 , k) for k ≥ 5, as well as a description of the corresponding minimum stable graphs. When we have a K 5 and a K 6 , we get the same kind of contradiction when replacing these two complete graphs with a K 7 as well as when we have two K 6 replaced by a K 8 .

Lemma We have thus to consider that G is the vertex disjoint union of complete graphs isomorphic to K 7 or K 8 and at most one K 5 or one K 6 . Replacing a K 5 and a K 7 by one K 8 leads to a (K 5 , k) stable graph with a number of edges less than the number of edges of G, a contradiction. Replacing a K 6 and a K 8 by two K 7 leads to a (K 5 , k) stable graph with a number of edges less than the number of edges of G, a contradiction.

It remains to consider the case where the components are all isomorphic to a K 7 with the exception of one K 6 or all isomorphic to a K 8 with the exception of one K 5 . When we have at least two K 7 and a K 6 , these three complete graphs can be replaced by two K 8 , the resulting graph is still a (K 5 , k) stable graph, but the number of edges is less than the number of edges of G, a contradiction. When we have at least two K 8 and a K 5 , these three complete graphs can be replaced by three K 7 , the resulting graph is still a (K 5 , k) stable graph, but the number of edges is less than the number of edges of G, a contradiction.

When G is reduced to a K 8 and a K 5 or to a K 7 and a K 6 , we must have k ≤ 4, which is impossible.

Lemma 5.4. Let G be a (K 5 , k) stable graph with minimum size and maximum degree 6. Assume that some component contains a K 6 . Then either the component is reduced to this K 6 or to K 7 .

Proof Let A = {v 1 . . . v 6 } be the set of vertices of the K 6 . If d(v i ) = 5 for each vertex in A the proof is complete. Assume that the vertex v 1 has degree 6 and let w be its neighbour outside V . Since v 1 w must be contained in a K 5 by Proposition 1.2, w must be adjacent to 3 other vertices in V (say v 2 , v 3 and v 4 ). In the same way, if v 5 or v 6 has a neighbour outside A, this vertex must be adjacent to 4 vertices of A, which is impossible if this vertex is distinct from w.

Let w ∈ A be a neighbour of w (if any). Since ww must be contained in a K Proof Let H be a component containing vertices of degree 5 or 6 only. By Proposition

1.2, every edge is contained in a K 5 . Let U = {u 1 , u 2 , u 3 , u 4 , u 5 } be a set of vertices inducing a K 5 in H. case 1 : ∃ i 1 ≤ i ≤ 5 d H (u i ) = 6.
Without loss of generality we may suppose that i = 1. Let w and w the two neighbours of u 1 outside U . Since u 1 w must be contained in a K 5 , w must be adjacent to at least two vertices in U -{u 1 }. Without loss of generality, assume that wu 2 ∈ E(G)

and wu 3 ∈ E(G). Note that w is not joined to the two vertices u 4 and u 5 , otherwise, H contains a K 6 and H is thus isomorphic to a complete graph by Lemma 5.4. For the same reason, w is not joined to all the vertices in U . there must be an edge incident with w (d H (w ) ≥ 5), but this edge cannot be contained in any K 5 , a contradiction. If u 4 w is not an edge, there must be an edge incident with u 4 and this edge cannot be contained in any K 5 , which is impossible. Thus, w and w are adjacent and there are 2 vertices in {u 2 , u 3 , u 5 } adjacent to w , say u 2 and u 3 . But now, there is an additionnal edge incident with u 4 and this edge is u 4 w otherwise it is not contained in any K 5 . It is a routine matter to check that there is no additionnal vertex nor edge in H. Hence H is isomorphic to the graph depicted in Figure 2, a contradiction with Lemma 5.5.

case 2 : ∀ i 1 ≤ i ≤ 5 d H (u i ) = 5.
Let w be the last neighbour of u 1 outside U . Since wu 1 must be contained in a K 5 , w must be adjacent to u 2 , u 3 and u 4 , without loss of generality. Hence, wu 5 ∈ E(G) or H is complete. Since d H (u 5 ) = 5, let w = w be the last neighbour of u 5 outside U . Then

u 5 w is not contained in a K 5 , which is impossible. Lemma 5.7. Q(K 5 , 4) = 36.
Proof Since K 9 and K 6 +K 7 are (K 5 , 4) stable graphs, we certainly have Q(K 5 , 4) ≤ 36.

Assume that some graph G with e(G) ≤ 35 is a (K 5 , 4) stable graph with minimum size. Let v be a vertex with maximum degree. If

d(v) ≥ 8 then G -v is a (K 5 , 3)
stable graph with at most 27 edges, a contradiction with Proposition 2.7. If

d(v) = 7
then G -{v} is a (K 5 , 3) stable graph with at most 28 edges. Hence we must have e(G -{v}) = 28 and G is a (K 5 , 3) stable graph with minimum size. By Proposition 2.7, G -{v} is a K 8 and G is a K 9 minus one edge, a contradiction with Proposition 2.1.

We can thus assume that the maximum degree of G is at most 6. If some vertex u has degree 4, let v be one of its neighbours. We know, by Lemma 2.6 that d(v) = 6.

By deleting v, we get a graph G -v which is a (K 5 , 3) stable graph. In that graph, the edges incident with u are not contained in a K 5 since the degree of u is now 3. We can thus delete these edges and we obtain a (K 5 , 3) stable graph with at most 27 edges, a contradiction with Proposition 2.7.

Hence every vertex must have a degree 5 or 6. By Lemma 5.6, the components of G are complete graphs. It can be easily checked that the only convenient graphs are K 9 and K 6 + K 7 , a contradiction with e(G) ≤ 35.

Lemma 5.8. K 6 + K 7 and K 9 are the only (K 5 , 4) stable graph with minimum size.

Proof By Lemma 5.7, let G be a (K 5 , 4) stable graph with 36 edges.

If G has a vertex of degree at least 8 then G -{v} is a (K 5 , 4) stable graph with at most 28 edges. Hence G -{v} must have exactly 28 edges and d(v) = 8. Since, by

Proposition 2.7 G -{v} is a K 8 , G itself is a K 9 .
We can thus assume that the maximum degree of G is at most 7. If some vertex u has degree 4, let v be one of its neighbours. We know, by Lemma 2.2 that d(v) ≥ 6. By deleting v, we get a graph G -{v} which is a (K 5 , 3) stable graph. In that graph, the edges incident with u are not contained in a K 5 of G 3 since the degree of u is now 3.

We can thus delete these edges and we obtain a (K 5 , 3) stable graph with 27 edges, a contradiction with Proposition 2.7.

Hence the degree of each vertex is 5, 6 or 7.

In the following Claims Q 1 and Q 2 denote any two induced K 5 of G. such that x ∈ V (Q 1 ) and y ∈ V (Q 2 ). Then we can find a vertex x ∈ V (Q 1 ) and a vertex y ∈ V (Q 2 ) such that {x, x , y, y } is contained in an induced K 5 of G. Moreover the 5 th vertex of this K 5 must be contained in

Claim 5.8.1. |V (Q 1 ) ∩ V (Q 2 )| = 1. Proof Assume that |V (Q 1 ) ∩ V (Q 2 )| =
Q 1 + Q 2 .

Proof

Since G is a minimum (K 5 , 4) stable graph, the edge xy must be contained in a K 5 (say Q). By Claim 5.8.1 Q contains at least one vertex more in Q 1 (say x ) and one vertex more in Q 2 (say y ). Let a be the 5 th vertex of Q and assume that a

∈ V (Q 1 ) ∪ V (Q 2 ).
G -{a} is a (K 5 , 3) stable graph but it is not minimum since the edges between {x, x } and {y, y } cannot be contained in a K 5 . By deleting these 4 edges in G -{a} we get a (K 5 , 3) stable G with at most 28 edges. By Proposition 2.7, G is isomorphic to K 8 , which is impossible.

Then G 1 = G-{x, y, z} is a (K 5 , 1) stable graph in which the vertices u 1 , u 2 , v 1 , v 2 are not contained in any K 5 by Claims 5.8.1 and 5.8.3. That means that

G 2 = G -(V (Q 1 ) ∪ V (Q 2 )) is a (K 5 , 1) stable graph. If w ∈ V (Q 1 ) ∪ V (Q 2
) is adjacent to some vertex w in G 2 then a K 5 using that edge forces 4 edges more between these two subgraphs, a contradiction since G would have at least 37 edges (by Proposition 2.3 G 2 has at least 15 edges).

If some edge is missing between {u 1 , u 2 } and {v 1 , v 2 } (say

u 1 v 1 ∈ E(G)), then G 3 = G -{u 2 , v 2 } is a (K 5 ,
2) stable graph where x, y, z, u 1 , v 1 are not contained in any K 5 .

The graph G 3 is still (K 5 , 2) stable. Hence, by Proposition 2.5 G must have at least 38 edges, a contradiction.

We can thus suppose that V (Q 1 ) ∪ V (Q 2 ) induces a K 7 . The remaining part of G is the (K 5 , 1) stable graph G 2 described above. This graph must have exactly 15 edges.

Hence, G 2 is isomorphic to K 6 by Proposition 2.3. That means that G is isomorphic to

K 7 + K 6 . Claim 5.8.5. Either |V (Q 1 ) ∩ V (Q 2 )| = 4 or G is isomorphic to K 7 + K 6 .
Proof Suppose contrary to the claim that V (Q 1 ) ∩ V (Q 2 ) = {x, y, z, t} and G is not isomorphic to K 7 + K 6 . Let u and v be the remaining vertices of Q 1 and Q 2 respectively.

Let r be a neighbour of u, if any, outside V (Q 1 ) ∪ V (Q 2 ). Let Q 3 be a K 5 containing the edge ur. Then V (Q 1 ) ∩ V (Q 3 ) contains 4 vertices (Claims 5.8.1 and 5.8.3) but

V (Q 2 ) ∩ V (Q 3 )
V (Q 1 ) ∪ V (Q 2 ).
Let s be a such neighbour of x,.

V (Q 1 ) ∪ V (Q 2 ). Hence, Q 1 + Q 2 is a component of G inducing a K 6 .
By deleting 2 vertices in this component, the resulting graph is (K 5 , 2) stable. Since the remaining vertices of Proof Let G be a (K 5 , 5) stable graph with minimum size. By Lemma 5.9, we have e(G) = 42.

V (Q 1 ) ∪ V (Q 2 )
If G has a vertex of degree at least 7 then G -v is a (K 5 , 4) stable graph with at most 35 edges, a contradiction with Lemma 5.7.

If G has a vertex u of degree 4, let v be one of its neighbours. By deleting v we get a (K 5 , 4) stable graph where the edges incident with the vertex u are not contained in any K 5 since the degree of u in that graph is 3. By deleting these edges we get a (K 5 , 4)

stable graph with at most 35 edges, a contradiction with Lemma 5.7.

Hence every vertex has degree 5 or 6. By Lemma 5.6, the components of G are complete. It is an easy task to see that the only convenient graph G is isomorphic to Proof By Lemma 5.9, the theorem holds for k = 5. Suppose that the property holds for any k (5 ≤ k < k 0 ) and let us consider a (K 5 , k 0 ) stable graph G with minimum size.

K 7 + K 7 ,
Assume that G has at most 7k 0 + 6 edges and let v be a vertex of maximum degree.

Since G -v is a (K 5 , k 0 -1) stable graph, it must have 7k 0 edges, which means that d(v) ≤ 6. Moreover, by Proposition 1.2, we certainly have d(v) ≥ 4.

Let z be a vertex of degree 4 in some component of G. If z has a neighbour v whose degree is 6 then G -v has exactly 7k 0 edges. Hence G -v is a (K 5 , k 0 -1) stable graph with minimum size. Since the degree of z is 3 in G -v, any edge incident with z in G -v is not contained in a K 5 , a contradiction.

If z has a neighbour v whose degree is 5 then G -v has at most 7k 0 + 1 edges. G -v is a (K 5 , k 0 -1) stable graph. This graph has not minimum size since the 3 remaining edges incident with z are not contained in a K 5 . If we delete these 3 edges, we still have a (K 5 , k 0 -1) stable graph, but the number of edges is at most 7k 0 -2, which is impossible by the induction hypothesis.

Hence the neighbours of z have also degree 4, that means that the component containing a vertex of degree 4 is a 4 regular graph containing a K 5 . That is, this component is reduced to a K 5 .

Since each component containing only vertices of degree 5 or 6 are complete by Lemma 5.6, we have thus that all the components of G are complete. By Lemma 5.3, each component has 7 vertices or 8 vertices (recall that k 0 ≥ 5). Assume that we have p components isomorphic to a K 7 and q isomorphic to a K 8 , then k 0 ≤ 3p + 4q -1 and G has 21p + 28q edges. If k 0 = 3p + 4q -1, we have 21p + 28q = 7k 0 + 7, a contradiction. If k 0 < 3p + 4q -1 then deleting one vertex in some component leaves the graph (K 5 , k 0 )

Lemma 5 . 1 .Lemma 5 . 2 .

 5152 Let G be a (K 5 , k) stable graph containing a component isomorphic to K p with p ≥ 9. Then the graph G obtained from G by deleting two vertices v and v in thisK p and adding a K 6 is a (K 5 , k) stable graph such that • if p ≥ 10, e(G ) < e(G),• if p = 9, e(G ) = e(G).Proof Let A be the set of vertices created by the adjunction of the new K 6 . Let S be a set of vertices with|S| ≤ k in G . If |S ∩ A| ≤ 1, G -S contains obviously a K 5 . If |S ∩ A| ≥ 2 then S = S -A + {v, v } is a subset of Gwith at most k vertices. Hence G -S contains a K 5 which still exists in G -S. If p ≥ 10, at least 17 edges are deleted and 15 edges are created, thus e(G ) < e(G) . If p = 9, 15 edges are deleted while 15 edges are created and e(G) = e(G ). Let G = (V, E) be a (K 5 , k) stable graph with minimum size. Then G does not contain two components isomorphic to a K p with p ≤ 6. Proof If we have two component (say K and L) isomorphic to a complete graph with 5 vertices then the graph G obtained from G by deleting these two components and adding a complete graph on 6 vertices is still a (K 5 , k) stable graph. Indeed, let S be any subset of V (G ) with |S | ≤ k. If G -S does not contain any K 5 then S contains at least 2 vertices v and w of the new K 6 . Let S = S -{v, w} + {a, b}, where a ∈ K and b ∈ L, then G -S does not contain any K 5 , a contradiction.

5 by Proposition 1 . 2 , 4 and v 5 ,Figure 2 :Lemma 5 . 5 .Lemma 5 . 6 .

 124525556 Figure 2: Forbidden component of a (K 5 , k) stable graph with minimum size.

subcase 1 . 1 :subcase 1 . 2 :

 1112 If w or w has no other neighbour in U , say w, we must have ww ∈ E(G), w u 2 ∈ E(G) and w u 5 ∈ E(G). One of u 4 or u 5 , say u 4 , is not adjacent to w , and there must be a vertex w adjacent to u 4 (d H (u 4 ) ≥ 5), but the edge u 4 w cannot be on any K 5 , which is impossible. If w has an other neighbour (say u 5 ) in U . When w is not adjacent to w, then w must be adjacent to precisely 3 vertices in {u 2 , u 3 , u 4 , u 5 }. If u 4 w is an edge,

case 1 :

 1 contains 3 vertices, a contradiction. Since d(u) ≥ 5, we must have uv ∈ E(G) (and, moreover, d(u) = d(v) = 5). There are neighbours of {x, y, z, t} outside

as claimed. Theorem 5 .

 5 11. Let G = (V, E) be a (K 5 , k) stable graph (k ≥ 5) with minimum size then |E(G)| = 7k + 7.

  Proof By Proposition 4.3 the vertices of G have degree 3 or 4. Assume to the contrary that H contains some vertex v with degree 3. Let N (v) = {u 1 , u 2 , u 3 } be its neighbourhood. By Proposition 1.2, N (v) is complete. Since H is not isomorphic to K 4 by Proposition 4.2, assume that, without loss of generality, u 1 is joined to some new vertex w. Since u 1 w must be contained in a K 4 by Proposition 1.2, w must be adjacent to u 2 and u 3 . By Proposition 2.1, H is not isomorphic to a K 5 minus one edge, hence there must exist some new vertex w adjacent to w. Since each vertex in {u 1 , u 2 , u 3 , w} has degree 4, we cannot find a K 4 using the edge ww , a contradiction with Proposition 1.2.

stable graph, there is a set S with at most k -1 vertices intersecting each K 4 of G -H. Then S + {a} intersects each K 4 of G while S has at most k -1 vertices, a contradiction. When k = 1, G must have 10 edges by Theorem 4.1. Since for each vertex v the graph G -v contains a K 4 , v is joined to this K 4 by 4 edges. Hence G is a K 5 and the result holds.

Proposition 4.3. Let G = (V, E) be a (K 4 , k) stable graph (k ≥ 1) with minimum size then every vertex of G has degree 3, 4 or 5.

Proof By Proposition 1.2 every vertex is contained in a K 4 , hence its degree is at least 3. Assume that G has a vertex v with d(v) ≥ 6. Then, by Lemma 1.4, G -v is a (K 4 , k -1) stable graph and therefore has at least 5k edges, which is impossible since G has exactly 5k + 5 edges, by Theorem 4.1.

Proposition 4.4. Let G = (V, E) be a (K 4 , k) stable graph (k ≥ 1) with minimum size.

Let H be a component without any vertex of degree 5, then each vertex of H has degree 4.

Theorem 4.5. Let G = (V, E) be a (K 4 , k) stable graph (k ≥ 1) with minimum size then G is isomorphic to pK 5 + qK 6 , where p and q are such nonnegative integers that

2p + 3q = k + 1.

Proof

The proof is by induction on k. By Proposition 2.3, the only minimum (K 4 , 1) stable graph with minimum size is K 5 . Let k 0 ≥ 2 and suppose that for every integer k, such that 1 ≤ k < k 0 every (K 4 , k) stable graph with minimum size is isomorphic to pK 5 + qK 6 , where p and q are nonnegative integers such that 2p + 3q = k + 1.

Let G be a (K 4 , k 0 ) stable graph with minimum size. By Theorem 4.1 we have e(G) = 5k 0 +5. Note that it is sufficient to prove that every component of G is isomorphic either to K 5 or to K 6 . By Proposition 4.3, we have 3 ≤ d G (v) ≤ 5 for every vertex v of G. Since by Proposition 1.2, every edge of G is contained in a K 4 , all the neighbours of a vertex v are in the same component of G -{v}.

  then the component of G which contains v is a near complete graph, contradicting Proposition 2.1. So v is connected to a K 5 and G is a union of graphs isomorphic to K 5 or K 6 , as desired.Assume now that no component has a vertex of degree 5. Then, by Proposition 4.4, each component is a 4-regular subgraph.Let v be any vertex and let N (v) = {u 1 , u 2 , u 3 , u 4 } be its neighbourhood. Since v is contained in a K 4 by Proposition 1.2, we can suppose, without restriction of generality, that u 1 u 2 , u 1 u 3 and u 2 u 3 are edges of G. Since vu 4 is contained in a K 4 by Proposition 1.2, u 4 is adjacent to at least 2 vertices of N (say, without loss of generality, u 2 and u 3 ).

	case 1:

  5.3.Let G = (V, E) be a (K 5 , k) stable graph with minimum size which is the vertex disjoint union of complete graphs and k ≥ 5. Then each component is a K 7 or a

	K 8 .

Proof By Lemma 5.1, we can consider that each component is a K p with 5 ≤ p ≤ 9. By Lemma 5.2, at most one component is a K 5 or a K 6 . If some component is isomorphic to a K 9 then let us replace this component by a K 6 and a K 7 . By Lemma 5.1 the resulting graph is still a (K 5 , k) stable graph with minimum size. It is clear that no component is isomorphic to a K 9 now. Indeed, applying once more the operation described above leads to a (K 5 , k) stable graph with minimum size having two K 6 , a contradiction with Lemma 5.2.

  1 then the vertex in the intersection must have degree at least 8, which is impossible. Assume that Q 1 and Q 2 are vertex disjoint and let xy ∈ E(G) (if any)

	Claim 5.8.2.

  The edge xs being contained in a K 5 , this K 5 must have 4 common vertices with Q 1 and 4 common vertices with Q 2 (Claims 5.8.1, 5.8.3 and 5.8.4). Hence, s must be adjacent to the 4 vertices of V (Q 1 ) ∩ V (Q 2 ) and {x, y, z, t, s} induces a K 5 with 4 common vertices with Q 1 and 4 common vertices with Q 2 . By the above remark, we have us ∈ E(G) as well as vs ∈ E(G) and V (Q 1 ) ∪ V (Q 2 ) induces a K 7 . By deleting 3 vertices of this component, the resulting graph is (K 5 , 1) stable with 15 edges, and hence is isomorphic to K 6 .

case 2 :There are no neighbours of {x, y, z, t} outside

  in this graph are not contained in any K 5 , we can delete them and the (K 5 , 2) stable graph so obtained must have 21 edges exactly. This component is a K 7 by Proposition 2.5, a contradiction.To end the proof of the lemma, it is sufficient to say that any two induced K 5 of G must be disjoint by Claims 5.8.1, 5.8.3, 5.8.4 and 5.8.5. That means that each component of G is a K 5 , which is impossible since G must have 36 edges.

	Lemma 5.9. Q(K 5 , 5) = 42.

Proof Since K 7 +K 7 is a (K 5 , 5) stable graphs, we certainly have Q(K 5 , 5) ≤ 42. Let G be a (K 5 , 5) stable graph with minimum size and assume that e(G) ≤ 41. Let us remark that the size of G is certainly greater than Q(K 5 , 4).

If G has a vertex of degree at least 6 then G-v is a (K 5 , 4) stable graph with at most 35 edges, a contradiction with Lemma 5.7. If G has a vertex of degree 4 then, since the degree of every neighbour is at most 5, we must have, by Lemma 2.2, Q(K 5 , 5) ≥ Q(K 5 , 4) + 9, a contradiction. Hence, every vertex must have degree 5 and by Lemma 5.6, the component of G are isomorphic to K 6 . It is easy to see that no such graph can exist. Lemma 5.10. K 7 + K 7 is the unique (K 5 , 5) stable graph with minimum size.

Claim 5.8.3.

Proof Assume that V (Q 1 ) ∩ V (Q 2 ) = {x, y}. Let us remark that these two vertices have degree 7. Let {u 1 , u 2 , u 3 } and {v 1 , v 2 , v 3 } be the sets of remaining vertices of Q 1 and Q 2 respectively.

Assume that some edge is missing between {u 1 , u 2 , u 3 } and {v 1 , v 2 , v 3 } (say

stable graph in which the vertices x and That means that u 1 and u 3 have 3 neighbours outside V (Q 1 ) ∪ V (Q 2 ). In the same way, we can consider that u 2 has also three such neighbours (take

as well as v 1 , v 2 and v 3 by symmetry. Hence G 3 contains the 19 edges of Q 1 + Q 2 and 18 edges connecting {u 1 , u 2 , u 3 } and {v 1 , v 2 , v 3 } to the vertices outside, a contradiction.

We can thus suppose that every vertex in {u 1 , u 2 , u 3 } is joined to every vertex in

and {v 1 , v 2 } be the sets of remaining vertices of Q 1 and Q 2 respectively. stable, which is impossible.

Dudek, Szymański and Zwonek propose the following conjecture. Conjecture 5.12. [START_REF] Dudek | H, k) stable graphs with minimum size[END_REF] For every integer q ≥ 5 there is an integer k(q) such that Q(K q , k) = (2q -3)(k + 1) for k ≥ k(q). Theorem 5.11 proves this conjecture for q = 5 with k(q) = 5. Theorem 5.13. Let G = (V, E) be a (K 5 , k) stable graph (k ≥ 5) with minimum size then

• each component is isomorphic to a complete graph with 7 or 8 vertices,

• there are p components isomorphic to K 7 and q components isomorphic to K 8 for any choice of p and q with 3p + 4q = k + 1.

Proof By Theorem 5.11, the first item is true. We can check that the property of the second item holds for k = 5 (G being the vertex disjoint union of two K 7 ). Assume that the property holds for any k (5 ≤ k < k 0 ) and let us consider a (K 5 , k 0 ) stable graph G with minimum size.

If G has a vertex v of degree at least 8, then G -v has at most 7k 0 -1 edges and cannot be a (K 5 , k 0 -1) stable graph, a contradiction. Thus the maximum degree of G is at most 7.

In that case, G -v is (K 5 , k 0 -1) stable graph with minimum size. By the induction hypothesis, each component of G -v is isomorphic to a complete graph with 7 or 8 vertices. Going back to G by adding the vertex v leads to join v to a whole component of G -v, otherwise, some edge incident with v cannot be contained in a K 5 , a contradiction with Proposition 1.2. The vertex v cannot be connected to 7 vertices of a K 8 , otherwise we would have a near complete graph, a contradiction. Hence v is joined to the 7 vertices of a K 7 and the component of G containing v is a K 8 . case 2 : If some component of G contains vertices of degree 5 or 6 only, then, by Lemma 5.6, this component is a complete graph on at least 7 or 8 vertices (Lemma 5.3), since k 0 > 5. case 3 : If some component of G contains a vertex v of degree 4 then, no neighbour w of v may have a degree at least 5. Otherwise, G -w is a (K 5 , k 0 -1) stable graph with at most 7k 0 + 2 edges. Since the degree of v is 3 in G -w, the 3 edges incident with v are not contained in any K 5 . We can thus delete these 3 edges from G -w, getting a (K 5 , k 0 -1) stable graph with at most 7k 0 -1 edges, which is impossible by Theorem 5.11. Hence this component is 4-regular. That is, this component is reduced to a K 5 , a contradiction with Lemma 5.3 since k 0 > 5.

It is now a routine matter to check that the third item holds.