Báo cáo toán hoc:" Saturation Numbers for Trees "

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài:Saturation Numbers for Trees . | Saturation Numbers for Trees Jill Faudree Ralph J. Faudree Department of Mathematics and Statistics Department of Mathematical Sciences University of Alaska Fairbanks University of Memphis Fairbanks AK 99775-6660 Memphis TN 38152 ffjrf@ rfaudree@ Ronald J. Gould Michael S. Jacobson Department of Mathematics and Computer Science Department of Mathematics Emory University University of Colorado Denver Atlanta GA 30322 Denver CO 80217 rg@ msj @ Submitted Jan 30 2009 Accepted Jul 17 2009 Published Jul 24 2009 Mathematics Subject Classifications 05C35 05C05 Abstract For a fixed graph H a graph G is H-saturated if there is no copy of H in G but for any edge e ị G there is a copy of H in G e. The collection of H-saturated graphs of order n is denoted by SAT n H and the saturation number sat n H is the minimum number of edges in a graph in SAT n H . Let Tk be a tree on k vertices. The saturation numbers sat n Tk for some families of trees will be determined precisely. Some classes of trees for which sat n Tk n will be identified and trees Tk in which graphs in SAT n Tk are forests will be presented. Also families of trees for which sat n Tk n will be presented. The maximum and minimum values of sat n Tk for the class of all trees will be given. Some properties of sat n Tk and SAT n Tk for trees will be discussed. 1 Introduction and Notation Only finite graphs without loops or multiple edges will be considered. Notation will be standard and generally follow the notation of CL05 . For a graph G we use G to represent the vertex set V G and the edge set E G when it is clear from the context. For a fixed graph H a graph G is H-saturated if there is no copy of H in G but for any edge e ị G there is a copy of H in G e. The collection of H-saturated graphs of order n is denoted by SAT n H and the saturation number denoted sat n H is the minimum number of edges in a graph in SAT n H . The maximum number of edges in a graph in SAT n