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

沈傳錦

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

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

沈傳錦

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

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

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

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

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

1 預(yù)備知識(shí)

定義1[5]設(shè) G1= (V1, E1)與 G2= (V2,E2)是兩個(gè)圖，G1與G2的字典乘積圖定義為：G1oG2＝(V,E)，其中

且

以下用Pm表示階為m的路。依定義可畫出2P與3P的字典乘積圖，如圖1。

圖1 2Po3P

為方便討論，在作PmoPn的圖時(shí)只畫一個(gè)簡(jiǎn)圖（有n(n - 1)(m-1)條邊未畫出來），如圖2（還有48條邊未畫出來的 P5oP4的簡(jiǎn)圖）。設(shè)則PmoPn中的點(diǎn)(ui,vj)簡(jiǎn)記為vi,j。在PmoPn的消圈集中的點(diǎn)，用較大的的黑點(diǎn)“·”來表示。

圖2 5Po4P的簡(jiǎn)圖

2 主要結(jié)論

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

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

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

可得

依推論1可得

依字典乘積圖的定義可得

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

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

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

圖3 P3oP6的簡(jiǎn)圖

圖4 P5oP6的簡(jiǎn)圖

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

證明 如圖4所示。一方面

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

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

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

證明從略。

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

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

另一方面，此消圈集的階數(shù)為最小。事實(shí)上此時(shí)的余點(diǎn)導(dǎo)出子圖為階數(shù)最大的森林，假如在此消圈集中還可以再減少某一個(gè)頂點(diǎn)，且由于這個(gè)頂點(diǎn)的度至少為n，則使得增加一個(gè)點(diǎn)后的余點(diǎn)導(dǎo)出子圖的邊數(shù)不少于頂點(diǎn)數(shù)，即頂點(diǎn)數(shù)為kn +1、邊數(shù)為 kn+ (n - k)，于是余點(diǎn)導(dǎo)出子圖含有圈，矛盾。如圖5所示。

圖5 P6?7P的簡(jiǎn)圖

[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é)報(bào),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].合肥：中國(guó)科學(xué)技術(shù)大學(xué),2007.

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

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àn)閳D論及其應(yīng)用。

O157.5

A

1009-9115(2011)05-0020-02