几类图的最优填充数  

Fill-in Numbers of Some Graphs

作　　者：汤洁泉[1] 束金龙[1] 

机构地区：[1]华东师范大学数学系,上海200062

出　　处：《华东师范大学学报（自然科学版）》2006年第5期76-82,共7页Journal of East China Normal University(Natural Science)

基　　金：国家自然科学基金(19971027);上海市科委基础研究重点项目(O4JC14031);上海市自然科学基金(05ZR14046);教育部地理信息科学重点实验室开放基金

摘　　要：运用图的最优填充分解定理和局部最优填充定理,将一些特殊图类G1×G2,S(G), R(G)和双圈图分解为一些可求得最小填充数的图,得到如下结果:(1)F(Pm×Pn)≤(m- 2)(n-2),其中m≥2,n≥2;(2)若G是有m条边的n阶2-连通图,则F(S(G))=m+F(G); (3)设图G为双圈图,两个诱导圈的圈长分别为p和q,t为这两个圈公共部分的路上的顶点个数(不包括两个端点),则F(G)=p+q-t-6．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）, R（G） and double cyclic graphs were studied. And the following results were obtained： （1） F（Pm×Pn）≤ （m - 2）（n - 2）, wtlere m ≥ 2, n≥ 2; （2） ifG 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.

关 键 词：填充数 分解约化 弦图 双圈图 

分 类 号：O157.5[理学—数学]