沈传锦

（闽西职业技术学院 计算机系，福建 龙岩 364021）

路与路的字典乘积图的消圈数

沈传锦

（闽西职业技术学院 计算机系，福建 龙岩 364021）

探讨了路与路的字典乘积图的消圈问题。对一般的路与路，推导出它们的字典乘积图的消圈数的一个紧的下界；对一些特殊的路与路，推导出它们的字典乘积图的消圈数的准确值。

消圈数；字典乘积；路；圈

设G= (V(G),E(G))是一个有限简单无向图，若S⊆ V(G)，且G-S是无圈图，则称S为G的一个消圈集。阶数最小的消圈集称为最小消圈集。图G的消圈数就是图G最小消圈集的阶数，并记为φ(G)。由消圈数的定义可知，图G中至少要删去φ(G)个顶点，才能使余下顶点的导出子图不含圈。若用I(G)记图G最大阶导出森林的阶数，则找到了图的最大阶的导出森林就等价于确定了图的消圈数，且

这一消圈问题至少要追溯到1847年Kirchhoff研究的成果。当在考虑电子电流电路时，他在文[1]中考虑过如何找到图的最大阶导出树。当时许多类似的论文考虑如何在图中找到最大阶导出森林，如[2]。文[3]研究了笛卡尔乘积图的消圈数问题，由此笔者提出路与路的字典乘积图消圈问题。

1 预备知识

定义1[5]设 G1= (V1, E1)与 G2= (V2,E2)是两个图，G1与G2的字典乘积图定义为：G1oG2＝(V,E)，其中

且

以下用Pm表示阶为m的路。依定义可画出2P与3P的字典乘积图，如图1。

图1 2Po3P

为方便讨论，在作PmoPn的图时只画一个简图（有n(n - 1)(m-1)条边未画出来），如图2（还有48条边未画出来的 P5oP4的简图）。设则PmoPn中的点(ui,vj)简记为vi,j。在PmoPn的消圈集中的点，用较大的的黑点“·”来表示。

图2 5Po4P的简图

2 主要结论

定……