不含 K3的（p，p）圖和（p，p-2）圖的包裝

（桂林師范高等?？茖W(xué)校 數(shù)學(xué)與計算機(jī)技術(shù)系，廣西桂林541199）

S·M·Hedetniemi等在文獻(xiàn)[1]中得到了n階樹和任意一個 n階（p，p-1）圖可包裝的條件。P·J·Slater等在文獻(xiàn)[2]中提出對任意兩個不含三角形的n（＞6）階（p，p-1）圖是否可包裝的問題，文獻(xiàn)[3]解決了此問題。文獻(xiàn)[4]獲得n階樹和同階（p，p+1）圖可包裝的充分必要條件。本文給出不含三角形的（p，p）圖與同階的（p，p-2）圖可包裝的充分必要條件。

文中所涉之圖都為簡單無向圖，V（G），E（G）分別是圖G的結(jié)點(diǎn)集和邊集，記G的補(bǔ)圖。若（k為整數(shù)），稱 G 是（p，p-k）圖。若，則稱 G1，G2同階.Sn＝K1，n-1，Ok表示 k 個孤立結(jié)點(diǎn)，Cn表示 n 階圈。設(shè) G1，G2，是同階圖 σ，是 V（G1）到 V（G2）的雙射，，用u1，u2表示在中的原像互換，即表示 σ（v2）＝u1，σ（v1）＝u2；（u1u2）（u3u4）σ 表示在 σ 中同時將 u1，u2的原像互換和 u3，u4的原像互換。

其余未說明的符號。概念及術(shù)語參考文獻(xiàn)[6]。

定義 設(shè)G1，G2是同階圖，如果G1與的某個子圖同構(gòu)，稱G1可嵌入，記為，如果其同構(gòu)映射為時，記作，這時稱G1與G2可包裝。

引理 1[3]設(shè)｛G1，G2｝是兩個同階圖，H1，H2分別是它們的支撐子圖，若

引理2[7]設(shè)n階圖G1，G2分別有1度結(jié)點(diǎn)，v1，u1且，

引理 3 設(shè)｛G1，G2｝是同階圖對，其中 G1是（p，p-2）圖，G2是不含 K3的（p，p）圖，G1，G2，分別有 1 度結(jié)點(diǎn)v1，u1，且分別是G1，G2中與其鄰接結(jié)點(diǎn)度數(shù)最小的1度結(jié)點(diǎn)，若

圖1

圖2

定理 設(shè)G1，G2都是n階簡單圖（n≥3），其中G1是不含 K3的（p，p）圖，G2是（p，p-2）圖，則圖 G1與 G2可包裝的充分必要條件是圖對｛G1，G2｝不為禁用圖對