圖的填充數(shù)的一些新進(jìn)展.pdf

1、本文主要研究了一些特殊圖類的最小填充數(shù)問題，通過已知的分解約化定理，將一些特殊圖類分解為一些可求得最小填充數(shù)的圖，從而求得其最小填充數(shù)。對(duì)G1(.×)G2，Sk(G)，R(G)，雙圈圖，哈林圖等幾類圖的最小填充數(shù)進(jìn)行了討論，得到如下結(jié)果(未知符號(hào)定義具體見文中)： 1.F(Pm(.×)Pn)≤(m-2)(n-2)，其中m≥2，n≥2。 2.F(P2(.×)Cn)={2n-3，當(dāng)n=2k+1時(shí)；2n-6，當(dāng)n=2k時(shí).k∈

2、N+，n≥3。 3.F(P3(.×)Cn)={2n-3，當(dāng)n=2k+1時(shí)；2n-6，當(dāng)n=2k時(shí).k∈N+，n≥3。 4.若G是有m條邊的n階2-連通圖，則F(S(G))=m+F(G)。 5.對(duì)于邊數(shù)m較少時(shí)連通圖的填充數(shù)，有以下結(jié)果： (1)當(dāng)m=n-1時(shí)，圖G為樹，則F(G)=0。 (2)當(dāng)m=n時(shí)，圖G為單圈圖，則F(G)=g-3，其中g(shù)為圍長。 (3)當(dāng)m=n+1時(shí)，圖G為雙圈圖.