不含 K3的（p，p）图和（p，p-2）图的包装

（桂林师范高等专科学校 数学与计算机技术系，广西桂林541199）

S·M·Hedetniemi等在文献[1]中得到了n阶树和任意一个 n阶（p，p-1）图可包装的条件。P·J·Slater等在文献[2]中提出对任意两个不含三角形的n（＞6）阶（p，p-1）图是否可包装的问题，文献[3]解决了此问题。文献[4]获得n阶树和同阶（p，p+1）图可包装的充分必要条件。本文给出不含三角形的（p，p）图与同阶的（p，p-2）图可包装的充分必要条件。

文中所涉之图都为简单无向图，V（G），E（G）分别是图G的结点集和边集，记G的补图。若（k为整数），称 G 是（p，p-k）图。若，则称 G1，G2同阶.Sn＝K1，n-1，Ok表示 k 个孤立结点，Cn表示 n 阶圈。设 G1，G2，是同阶图 σ，是 V（G1）到 V（G2）的双射，，用u1，u2表示在中的原像互换，即表示 σ（v2）＝u1，σ（v1）＝u2；（u1u2）（u3u4）σ 表示在 σ 中同时将 u1，u2的原像互换和 u3，u4的原像互换。

其余未说明的符号。概念及术语参考文献[6]。

定义 设G1，G2是同阶图，如果G1与的某个子图同构，称G1可嵌入，记为，如果其同构映射为时，记作，这时称G1与G2可包装。

引理 1[3]设｛G1，G2｝是两个同阶图，H1，H2分别是它们的支撑子图，若

引理2[7]设n阶图G1，G2分别有1度结点，v1，u1且，

引理 3 设｛G1，G2｝是同阶图对，其中 G1是（p，p-2）图，G2是不含 K3的（p，p）图，G1，G2，分别有 1 度结点v1，u1，且分别是G1，G2中与其邻接结点度数最小的1度结点，若

图1

图2

定理 设G1，G2都是n阶简单图（n≥3），其中G1是不含 K3的（p，p）图，G2是（p，p-2）图，则图 G1与 G2可包装的充分必要条件是图对｛G1，G2｝不为禁用图对