圖的鄰域并及度條件與Z3-連通性

顧粉霞, 蔣梓煒, 盧春霞, 梁 棟, 朱 佳, 楊 帆

(江蘇科技大學 數理學院， 江蘇 鎮(zhèn)江 212003)

圖的鄰域并及度條件與Z3-連通性

顧粉霞, 蔣梓煒, 盧春霞, 梁 棟, 朱 佳, 楊 帆

(江蘇科技大學 數理學院， 江蘇 鎮(zhèn)江 212003)

鄰域并條件;Z3-連通性;處處非零3-流

令G是一個圖,給定G的方向D.若一條邊e=uv∈D(G)是由點u指向點v,則稱u是邊e的尾,v是邊e的頭.對于一個點v∈V(G),定義E+(v)是以點v為尾的邊的集合,E-(v)是以點v為頭的邊的集合.令A是一個非平凡的阿貝爾群,A*=A-{0}.定義F(G,A)={f|f:E(G)→A},F*(G,A)={f|f:E(G)→A*}.

當?f=0時，f∈F(G,A)是一個A-流.當f∈F*(G,A)且?f=0時,f是一個處處非零的A-流.若f是一個處處非零的Z-流且對于所有e∈E(G),|f(e)|

文獻[2-3]中介紹了整數流問題.文獻[4]中推廣了處處非零流并引入群連通性概念.下面的猜想是由Jaeger等人提出的,到現在為止仍然沒有得到證明.

猜想1[4]任意5-邊連通圖是Z3-連通圖.

國內外學者圍繞著這個猜想做了很多的工作.最近度條件被用來證明圖中處處非零3-流及Z3-連通性的存在性.一些結果可以在參考文獻[5-11]中看到.令G是n階圖.若對于任意一對不相鄰的點u,v,d(u)+d(v)≥n，則稱圖G滿足Ore-條件.文獻[8]中列舉出了所有滿足Ore-條件的Z3-連通圖且得到了下面的定理.

定理1[8]若G(n≥3)是一個簡單圖,滿足Ore-條件,那么圖G要么是Z3-連通圖,要么是圖1的12個圖中的一個.

圖1 滿足Ore-條件的非Z3-連通圖Fig.1 Graphs satisfying Ore-condition but is not Z3-connected

圖的Z3-連通性與哈密爾頓性質有著密切的聯系.文獻[12] 在證明哈密爾頓圈的存在性時首次引入了鄰域并條件.受此啟發(fā),文獻[13]中考慮了圖的鄰域條件與Z3-連通性,并證明了如下結果.

在定理2的基礎上,降低鄰域并條件,得到了如下定理.

1 引理

為了證明結果,會用到參考文獻[4, 14-15]中的一些結論.

引理1令A是一個阿貝爾群,有以下結論:

1)K1是A-連通圖[15].

2)若e∈E(G),G是A-連通圖，則G/e是A-連通圖.

3)若H是G的子圖,且H和G/H都是A-連通圖,那么G也是A-連通圖[15].

5)當且僅當|A|≥n+1時,Cn是A-連通圖[4,15].

6)令G是一個簡單圖，H是G的非平凡子圖，若H是Z3-連通圖，則|V(H)|≥5.

7)令H是G的Z3-連通子圖,若對于v∈V(G-H),e(v,V(H))≥2,那么由V(H)∪{v}生成的子圖是Z3-連通圖[14].

對于u,v,w∈V(G),v,w∈N(u),定義G[uv,uw]由G去掉邊uv,uw,增加邊wv而得到,即G[uv,uw]=G∪{wv}-{uv,uw}.

引理2[15-16]令A是一個阿貝爾群且|A|≥3,G是一個圖,u,v,w是G中的3個點,d(u)≥4,v,w∈N(u),若G[uv,uw]是A-連通圖,那么G也是A-連通圖.

對于一個點u∈V(G),定義Gu:圖G中去掉N[u]中所有的點得到的新圖.

在上述引理的基礎上,我們可以得到如下結論.

2 定理3的證明

命題1δ(G)≤|V(G′-v′)|≤δ(G)+1

證明:因為Gu是H的子圖,V(G′-v′)?N[u],所以,只需證明|V(G′-v′)|≥δ(G).反證法,假設|V(G′-v′)|≤δ(G)-1.因為對于?v∈V(G′-v′),d(v)≥δ(G),所以e(v,H)≥2.通過引理1 5)可知,V(H)∪{v}生成的子圖是Z3-連通圖,與H是最大的Z3-連通圖相矛盾.

命題2G′-v′是完全圖

另一方面δ(G)+2≥|V(G′-v′)|+1≥|NG′-v′(vi)∪NG′-v′(vj)|+2≥δ(G)+4,與上述結果矛盾.

References)

[1] Bondy J A, Murty U S R.Graphs theory with applications[M].New York: Macmillan Press, 1976.

[2] Tutte W T.A contribution on the theory of chromatic polynomial[J].CanadJMath,1954, 6: 80-91.

[3] Tutte W T.On the algebraic theory of graph colorings[J].JCombinTheroy,1966,1:15-50.

[4] Jaeger F, Linial N, Payan C, et al.Group connectivity of graphs-a nonhomogeneous analogue of nowhere zero flow properties[J].JCombinTheory:SerB, 1992, 56: 165-182.

[5] Fan G, Zhou C.Ore condition and nowhere-zero Z3-flows[J].SIAMJonDiscreteMath, 2008, 22: 288-294.

[6] Fan G, Zhou C.Degree sum and nowhere-zero Z3-flows[J].DiscreteMath, 2008, 308: 6233-6240.

[7] Li X, Lai H J, Shao Y.Degree condition and Z3-connectivity[J].DiscreteMath, 2012, 312: 1658-1669.

[8] Luo R, Xu R, Yin J, et al.Ore condition and Z3-connectivity[J].EuropeanJournalofCombinatorics, 2008, 29: 1587-1595.

[9] Yao X, Li X, Lai H J.Degree conditions for group connectivity[J].DiscreteMath, 2010, 310: 1050-1058.

[10] Zhang X, Zhan M, Shao Y, et al.Degree sum condition for Z3-connectivity in graphs[J].DiscreteMath, 2010, 310: 3390-3397.

[11] Lai H J, Li X, Shao Y, et al.Group connectivity and group colorings of graphs-a survey[J].ActaMathSinica, 2011, 27: 405-434.

[12] Faudree R J, Could R J,Jacobson M S, et al.Neighborhood unions and hamiltonian properties in graphs[J].JCombinTheory:SerB, 1989, 47: 1-9.

[13] Li L, Li X.Neighborhood unions and Z3-connectivity in graphs[J].GraphsandCombin, 2013：1891-1898.

[14] DeVos M, Xu R, Yu G.Nowhere-zero Z3-flows through Z3-connectivity[J].DiscreteMath, 2006, 306: 26-30.

[15] Lai H J.Group connectivity of 3-edge-connected chordal graphs[J].GraphsCombin, 2000, 16: 165-176.

[16] Chen J, Eschen E, Lai H J.Group connectivity of certain graphs[J].ArsCombin, 2008, 89: 217-227.

(責任編輯：童天添)

NeighborhoodunionsanddegreeconditionandZ3-connectivityingraphs

Gu Fenxia, Jiang Ziwei, Lu Chunxia, Liang Dong, Zhu Jia, Yang Fan

(School of Mathematics and Physics, Jiangsu University of Science and Technolgy,Zhenjiang Jiangsu 212003,China)

neighborhood unions-condition;Z3-connectivity;nowhere-zero 3-flows

10.3969/j.issn.1673-4807.2014.06.018

2014-06-12

國家自然科學基金資助項目(11326215);江蘇科技大學博士啟動項目;2014年本科生創(chuàng)新計劃項目

顧粉霞(1992—)，女，研究方向為圖論.E-mail:gufenxia1016@163.com

楊帆(1984—),女,博士,講師,研究方向為圖論,E-mail:fanyang_just@163.com

O157.5

A

1673-4807(2014)06-0609-04