Some New Results On The Fill-in Of Graphs

In this paper, we mainly study the fill-in of some special graphs, achieving some new results. Using the decomposition theorem and the local reductive elimination for the fill-in of graphs, the fill-in of some special graphs, such as G₁×G₂, S(G), R(G), Halin graph are studied. Some results will be given in this thesis:4 . If G is a 2-connected graph with m edges and n vertices, then F(S(G)) = m + F(G).5 . (1) If m = n - 1, G is a tree, then F(G) = 0.(2) If m = n, G is a single cyclic graph, then F(G) = g — 3, where g is the girth of G.(3) If m = n +1, G is a double cyclic graph. Let the length of the two cycles are p and q, t is the number of the vertices which are both in the two cycles (the end points are excluded). Then F(G) =p + q-t-6.7. Let G is a Halin graph with n vertices, the number of inter-vertices is a, then the fill-in of G is f(G) = n-5 + a.