Some Results About The Contractible Edge And The Domination Number Of Graphs

In first two chapters we study mainly some problems about the contractible edge of graphs. Let G be a k-connected non-complete graph (where k ≥ 2), an edge of G is called k-contractible if its contraction results still in a k-connected graph, simply say contractible edge. An edge that is not contractible is called a non-contractible edge. A noncomplete k-connectecd graph is called contraction critical k-connected if G has no contractible edge. In a k-connected graph, if e = uv is contained in a triangle uvw and d(w) = k, then e is called trivially non-contractible.In 1961, Tutte ([1]) proved that any 3-connected graph with order at least 5 has a contractible edge. On the other hand, Thomassen ([2]) showed that for k ≥4 there are infinitely many k-connected k-regular graphs which do not have a contractible edge. So it is nature to study the structure of contraction critical k-connected graphs. The contraction critical 4-connected graphs was characterized by Martinov ([3]) and M. Fontet([4]), which are two special classes of 4-regular graphs. For k ≥ 5, the characterization for the contraction critical k-connected graphs seems to be very hard. In general, Egawa ([5]) showed that every contraction critical k-connected graph has a vertex of degree at most [5k/4] - 1. By Egawa's result, the minimum degree of a contraction critical 5-connected graph is 5. As for the vertex of degree 5 in contraction critical 5-connected graphs, Yuan ([7]) and Ando et.al ([6]) independently obtained.Theorem A ([6], [7]) Let G be a contraction critical 5-connected graph. Then each vertex of G has a neighbor of degree 5, and thus G has at least |G|/5 vertices of degree 5.In 1997, Su ([8]) improved the results of Theorem A and obtained the following. Theorem B Let G be a contraction critical 5-connected graph. Then each vertex of G has at least two neighbors of degree 5, and thus G has at least 2|G|/5 vertices of degree 5.Qin ([9]) shown that the number ' two ' in Theorem B is best possible, and he improved the number of vertices of degree 5 to 4|G|/9.Thomassen ([2]) proved that any contraction critical k-connected graph contains one triangle. Mader ([10]) obtained that every contraction critical k-connected graph G contains at least 1/3|G| triangles. Recently, Kriesell ([11]) further improved Mader's result to that a contraction critical k-connected graph G contains at least 2|G|/3 triangles.