Weak Saturation Numbers Of Some Graphs

For a fixed graph F,a graph G of order n is F-saturated if there is no copy of F in G,but for any edge e ∈G,there is a copy of F in G+e.The collection of F-saturated graphs of order n is denoted by SAT(n,F).The saturation number,denoted as sat(n,F), is the minimum number of edges in a graph in SAT(n,F).A graph G of order n is weakly F-saturated if G contains no copy of F,and there is an ordering of all edges of G so that if they are added one at a time,they form a complete graph and each edge added creates a new copy of F.The minimum size of a weakly F-saturated graph G of order n is denoted by wsat(n,F).The set of graphs of order n that are weakly F-saturated will be denoted by wSAT(n,F).No general theory has been developed for weak saturation numbers wsat(n,G)for graphs comparable to the extensive theory that has been developed for the extremal number ex(n,G)for graphs.One approach to developing a comprehensive theory for weak saturation numbers is to develop many examples of the weak saturation number for classes of graphs,so that the critical graphical parameters related to the weak saturation mwnbcr can be identificd from these examples.In this paper,weak saturation numbers for some graphs are considered.This paper consists of four parts.In the first chapter,the coneepts and a short survey of saturatod graphs and weakly saturated graphs are given.Some notations,symbols and the main results are also given.In the second chapter,we determine wsat(n,Kt-K1,m)which completely answers the question 3 in paper[11].We also give wsat(n,Kt-K2)and wsat(n,Kt-2K2)which partially answer the question 4 in paper[11].Furthermore,we determine wsat(n,k(K5-K2)),wsat(n,k(Kt-k2))and wsat(n,k(Kt-K1,m))by the techniques in[12].That partially answers the question 1 in paper[12].Paper[11]gives question 3.Is wsat(n,Kt-K1,m)=n(t-m-2)-t2-(2m+3)t/2-(m+1)for 2≤m<t-1？ and question 4. Is wsat(n,Kt-sK2)=(t-1/2)-s+(n-t+1)(t-3)for 1≤s<t-1/2? Paper[12]gives 2n+k-3 ≤wsat(n,k(K5-K2))≤2n+2k-4 and question 1. For k≥2 and n sufficiently la.rge,for which connected graphs G,is wsat(n,kG)=wsat(n,G)+k-1?In the third chapter,we determined wsat(n,KpUKq)(p≤q),"wsat(n,K2,6)and wsat(n,K2,t).Wsat(n,KpUKq)(p≤q)generalises the conclusion wsat(n,kKt)[12].By modifying method in[11],wsat(n,K2,6) and wsat(n,K2,t) are given which partially answer the question 2 in paper[11].Question 2[11].What properties will insure that a graph F with p vertices and q edges and minimal degre σ will satisfy q-1+(σ-1)(n-p)≤ wsat(n,F)≤(p-1)2/2+(δ-1)(n-p+1)for any n≥p?In the fourth chapter,wsat(n,K3,4)and the upper bound of wsat(n,Kt,t+1)are given, which partially answers the question 2 in paper[11].We also give an open problem.