Journal of East China Normal University(Natural Sc ›› 2006, Vol. 2006 ›› Issue (5): 76-82.

• Article • Previous Articles     Next Articles

Fill-in Numbers of Some Graphs

TANG Jie-quan, SHU Jin-long   

  1. Department of Mathematics, East China Normal University, Shanghai 200062, China
  • Received:2005-01-17 Revised:2005-04-20 Online:2006-09-25 Published:2012-11-27

Abstract: By using the decomposition theorem and the local reductive elimination for the fill-in of graphs, the fill-in numbers of some special graphs, such as G1×G2, S(G) and double cyclic graphs were studied. And the following results were obtained: (1)F(Pm×Pn)≦(m-2)(n-2), where m≧2, n≧2; ; (2) if G is a 2-connected graph with m edges and n vertices, then F(S(G))=m+F(G); (3) let G be a double cyclic graph, the length of the two cycles being p and q, respectively, and t the number of the vertices which are both in the two cycles (the end points are excluded), then F(G)=p+q-t-6.

Key words: fill-in, chordal, decomposition theorem, double cyclic graphs  ,

CLC Number: