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

沈传锦

（闽西职业技术学院 计算机系，福建 龙岩 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 主要结论

定理1 当m≥3，n≥3时，

证明 记PmonP＝G(V,E)，其中

在PmoPn中，点v1,1，v1,n与 vm,1,vm,n的度数皆为n+1，点v1,2,… ,v1,n-1与 vm,2, … ,vm,n-1的度数皆为n+2，点v2,1,v3,1,…,vm-1,1与 v2,n,v3,n,… ,vm-1,n的度数皆为2n+1，其余点的度数皆为2n+2，则

可得

依推论1可得

依字典乘积图的定义可得

定理2 当n≥3时， (φ P3oPn)=n。

证明 如图3所示。一方面，

另一方面，P3oPn中存在阶为n的消圈集

图3 P3oP6的简图

图4 P5oP6的简图

定理3 当n≥3时， (φ P5oPn)=2n。

证明 如图4所示。一方面

另一方面，P5oPn中存在阶为2n的消圈集

事实上此时的余点导出子图为阶数最大的森林，即阶皆为n的3条路，假如在此消圈集中还可以再减少某一个顶点，且由于这个顶点的度2n，则使得增加一个点后的余点导出子图的边数不少于顶点数，于是余点导出子图含有圈，矛盾。

定理4 当n≥3时， (φ P7oPn)=3n。

证明从略。

定理5 当m=2k (k ≥ 1, k∈ N)，n≥2(n＞k)时，φ( PmoPn)=kn。

证明 当m=2k (k ＞ 1, k∈ N)，n≥2时， pm˚pn中存在阶为kn的消圈集

另一方面，此消圈集的阶数为最小。事实上此时的余点导出子图为阶数最大的森林，假如在此消圈集中还可以再减少某一个顶点，且由于这个顶点的度至少为n，则使得增加一个点后的余点导出子图的边数不少于顶点数，即顶点数为kn +1、边数为 kn+ (n - k)，于是余点导出子图含有圈，矛盾。如图5所示。

图5 P6˚7P的简图

[1] G. Kirchhoff, Über die AuflÖsung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer StrÖme geführt wird[J]. Ann. Phys. Chem., 1847, 72： 497-508.

[2] N. Alon, D. Mubayi and R. Thomas. Large induced forest in sparse graphs[J]. Graph Theory, 2001, 38： 113-123.

[3] 沈传锦.完全图与树、圈、完全图、完全二部图的笛卡尔乘积图的消圈数[J].海南大学学报,2009,(4)：320-324.

[4] L.W. Beineke and R.C.Vandell. Decycling graphs[J]. Graph Theory, 1997, 25： 59-77.

[5] 孔伟.乘积图的pebbling覆盖数[D].合肥：中国科学技术大学,2007.

（责任编辑、校对：赵光峰）

Decycling Number of Lexicographic Product between Two Paths

SHEN Chuan-jin

(Department of Computer, Minxi Vocational & Technical College, Longyan 364021, China)

This paper studies the decycling number of Lexicographic product between two paths. A sharp lower bound of the decycling number of Lexicographic product is given for two general paths. And for some special paths, the accurate decycling number of their Lexicographic product is determined.

decycling number; Lexicographic product; path; cycle

2011-05-24

沈传锦（1972-），男，福建永定人，硕士，福建龙岩闽西职业技术学院讲师，研究方向为图论及其应用。

O157.5

A

1009-9115(2011)05-0020-02