路與路的字典乘積圖的消圈數(shù)

沈傳錦

（閩西職業(yè)技術(shù)學(xué)院 計算機系，福建 龍巖 364021）

路與路的字典乘積圖的消圈數(shù)

沈傳錦

（閩西職業(yè)技術(shù)學(xué)院 計算機系，福建 龍巖 364021）

探討了路與路的字典乘積圖的消圈問題。對一般的路與路，推導(dǎo)出它們的字典乘積圖的消圈數(shù)的一個緊的下界；對一些特殊的路與路，推導(dǎo)出它們的字典乘積圖的消圈數(shù)的準確值。

消圈數(shù)；字典乘積；路；圈

設(shè)G= (V(G),E(G))是一個有限簡單無向圖，若S? V(G)，且G-S是無圈圖，則稱S為G的一個消圈集。階數(shù)最小的消圈集稱為最小消圈集。圖G的消圈數(shù)就是圖G最小消圈集的階數(shù)，并記為φ(G)。由消圈數(shù)的定義可知，圖G中至少要刪去φ(G)個頂點，才能使余下頂點的導(dǎo)出子圖不含圈。若用I(G)記圖G最大階導(dǎo)出森林的階數(shù)，則找到了圖的最大階的導(dǎo)出森林就等價于確定了圖的消圈數(shù)，且

這一消圈問題至少要追溯到1847年Kirchhoff研究的成果。當(dāng)在考慮電子電流電路時，他在文[1]中考慮過如何找到圖的最大階導(dǎo)出樹。當(dāng)時許多類似的論文考慮如何在圖中找到最大階導(dǎo)出森林，如[2]。文[3]研究了笛卡爾乘積圖的消圈數(shù)問題，由此筆者提出路與路的字典乘積圖消圈問題。

1 預(yù)備知識

定義1[5]設(shè) 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的簡圖）。設(shè)則PmoPn中的點(ui,vj)簡記為vi,j。在PmoPn的消圈集中的點，用較大的的黑點“·”來表示。

圖2 5Po4P的簡圖

2 主要結(jié)論

定理1 當(dāng)m≥3，n≥3時，

證明 記PmonP＝G(V,E)，其中

在PmoPn中，點v1,1，v1,n與 vm,1,vm,n的度數(shù)皆為n+1，點v1,2,… ,v1,n-1與 vm,2, … ,vm,n-1的度數(shù)皆為n+2，點v2,1,v3,1,…,vm-1,1與 v2,n,v3,n,… ,vm-1,n的度數(shù)皆為2n+1，其余點的度數(shù)皆為2n+2，則

可得

依推論1可得

依字典乘積圖的定義可得

定理2 當(dāng)n≥3時， (φ P3oPn)=n。

證明 如圖3所示。一方面，

另一方面，P3oPn中存在階為n的消圈集

圖3 P3oP6的簡圖

圖4 P5oP6的簡圖

定理3 當(dāng)n≥3時， (φ P5oPn)=2n。

證明 如圖4所示。一方面

另一方面，P5oPn中存在階為2n的消圈集

事實上此時的余點導(dǎo)出子圖為階數(shù)最大的森林，即階皆為n的3條路，假如在此消圈集中還可以再減少某一個頂點，且由于這個頂點的度2n，則使得增加一個點后的余點導(dǎo)出子圖的邊數(shù)不少于頂點數(shù)，于是余點導(dǎo)出子圖含有圈，矛盾。

定理4 當(dāng)n≥3時， (φ P7oPn)=3n。

證明從略。

定理5 當(dāng)m=2k (k ≥ 1, k∈ N)，n≥2(n＞k)時，φ( PmoPn)=kn。

證明 當(dāng)m=2k (k ＞ 1, k∈ N)，n≥2時， pm?pn中存在階為kn的消圈集

另一方面，此消圈集的階數(shù)為最小。事實上此時的余點導(dǎo)出子圖為階數(shù)最大的森林，假如在此消圈集中還可以再減少某一個頂點，且由于這個頂點的度至少為n，則使得增加一個點后的余點導(dǎo)出子圖的邊數(shù)不少于頂點數(shù)，即頂點數(shù)為kn +1、邊數(shù)為 kn+ (n - k)，于是余點導(dǎo)出子圖含有圈，矛盾。如圖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] 沈傳錦.完全圖與樹、圈、完全圖、完全二部圖的笛卡爾乘積圖的消圈數(shù)[J].海南大學(xué)學(xué)報,2009,(4)：320-324.

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

[5] 孔偉.乘積圖的pebbling覆蓋數(shù)[D].合肥：中國科學(xué)技術(shù)大學(xué),2007.

（責(zé)任編輯、校對：趙光峰）

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-），男，福建永定人，碩士，福建龍巖閩西職業(yè)技術(shù)學(xué)院講師，研究方向為圖論及其應(yīng)用。

O157.5

A

1009-9115(2011)05-0020-02