论文部分内容阅读
本文主要研究了一些特殊图类的最小填充数问题，通过已知的分解约化定理，将一些特殊图类分解为一些可求得最小填充数的图，从而求得其最小填充数。对G1(.×)G2，Sk(G)，R(G)，双圈图，哈林图等几类图的最小填充数进行了讨论，得到如下结果(未知符号定义具体见文中)：
1.F(Pm(.×)Pn)≤(m-2)(n-2)，其中m≥2，n≥2。
2.F(P2(.×)Cn)={2n-3，当n=2k+1时；2n-6，当n=2k时.k∈N+，n≥3。
3.F(P3(.×)Cn)={2n-3，当n=2k+1时；2n-6，当n=2k时.k∈N+，n≥3。
4.若G是有m条边的n阶2-连通图，则F(S(G))=m+F(G)。
5.对于边数m较少时连通图的填充数，有以下结果：
(1)当m=n-1时，图G为树，则F(G)=0。
(2)当m=n时，图G为单圈图，则F(G)=g-3，其中g为围长。
(3)当m=n+1时，图G为双圈图.设两个诱导圈的圈长分别为p和q，t为这两个圈公共部分的这条路上的顶点个数(不包括这条路的端点)。则F(G)=p+q-t-6。
6.设G为n阶哈林图，内点数为a，则G的填充数为f(G)=n-5+a。