沒有任意非零4-流的圖邊數的新極值

劉彥芬 秦健 楊星星

（1.永城職業學院，河南 永城 476600；2.徐州建筑職業技術學院，江蘇 徐州 221116；3.中國礦業大學，江蘇 徐州 221008）

沒有任意非零4-流的圖邊數的新極值

劉彥芬1秦健2楊星星3

（1.永城職業學院，河南 永城 476600；2.徐州建筑職業技術學院，江蘇 徐州 221116；3.中國礦業大學，江蘇 徐州 221008）

在文獻[7]中Tutte介紹了任意非零流，后來被廣泛的研究。為了得到較好的界值，論文運用圖收縮的方法，給出了圖沒有任意非零4-流時邊數的新極值。上述的極值改進了[5]中的結論。

邊數；任意非零4-流；2邊連通

0 引言

本文研究的是有限的、無環但可能含有平行邊的圖。未定義的術語和記號參見文獻[1]，n表示n階循環群，其中n為某個n≥ 2的整數。設D( G )表示無向圖G的一個定向。為了方便，用D表示D( G)。設 EG(v)表示在圖中與v點關聯的邊的集合。對于一點v∈V( D )，

Tutte在文獻[7]中介紹了任意非零流，并且非零流被廣泛的研究，參見文獻[8]。 一個圖有ANZF?的必要條件是2-邊連通的。對于整數k≥2，用 Fk表示有任意非零 Zk-流的全部圖的集合，由定義得

眾所周知，Petersen圖P10沒有4?NZF，并且當n為一奇數， n+1個頂點的輪圖Wn沒有3?NZF。于是自然的就考慮：對于k∈{3 ,4}，使得2-邊連通的n階簡單圖至少具有f( n, k)條邊，就有k?NZF的函數的存在性。本文就是考慮k=4時，使得2-邊連通的n階簡單圖至少具有f( n, k)條邊，就有4?NZF的函數的存在性。

1 主要引理

引理1[4]設G為階數為n (n≤17)且2-邊連通的圖，則G∈F4或者G能被收縮到petersen圖。

引理 2[5]設G′是G的簡約圖，則G′∈F4當且僅當G∈F4。

引理 3[6]設G是2-邊連通的非平凡的簡約圖，則G為簡單圖且

引理 4[5]設G是2-邊連通且階數為n的簡單圖，取p為滿足p≥2的整數，如果

那么G的約簡至多有p?1個頂點。

那么G有一個4-NZF，或者G可以收縮成Petersen圖。

2 主要結論及證明

那么，G的約簡圖至多有p?1個頂點。

因為G為2-邊連通圖，c≥p≥2，G'是非平凡的，由引理3，

于是有，

化簡得

若c=p，上式顯然不成立。故c＞p;。

所以

所以假設不成立，即c＜p。也就是，c≤p?1。

故G的約簡至多有 p?1個頂點。

基于上述的引理2.1，有下面的定理2.2成立。

那么G有一個4-NZF，或者G可以收縮成Petersen圖。

證明：取p=18，由引理2.1，G的約簡 G'至多有17個頂點。再由引理1可知，G的約簡 G'∈F4，或者G'可以收縮成Petersen圖。

若G'∈F4，由引理3知，G∈F4。

若G'可以收縮成Petersen圖，則G可以收縮成Petersen圖。

所以定理2.2成立。

上述的定理2.2的結論與文獻[5]中的定理1.3(見上述的引理5)的結論相同，但條件有了減弱。盡管只是將邊數減少了1，

這樣的圖存在無數多個。

[1] J.A.邦迪, U.S.R.默蒂(吳望名,李念祖,吳蘭芳等譯).圖論及其應用[M].北京:科學出版社,1984.

[2]鄭藝容.乘積圖的非零整數流和完美匹配單圈圖的特征值[M].福州:福州大學碩士學位論文,2005.

[3]尚華輝,苗連英,苗正科.沒有任意非零3-流圖的一個新下界[J].山西大學學報(自然科學版) ,2009, (3): 341-344.

[4]J.J.Watkins and R.J.Wilson.A survey of snarks[J].Graph theory, Combinatorics，and Applications, Wiley New York, 1991, 2,1129-1144.

[5]H.J.Lai.,The size of graphs without a nowhere zero 4-flow[J].J.Graph Theory.1995,19, 385-395.

[6]P.A.Catlin,A reduction method to find spanning Eulerian subgraphs[J].J.Graph Theory.1988,12,29– 45.

[7]W.T.Tutte, A contribution to the theory of chromatic polynomials[J].Canad.J.Math, 1954, 6: 80-91.

[8]F.Jaeger, N.Linial, C.Payan, and N.Tarsi, Group connectivity of graphs – a nonhomogeneous analogue of nowhere zero flow properties[J].J.Combinatorial Theory, Ser.B, 1992, 56: 165-182.

[9]F.Jaeger, Flows and generalized coloring theorem in graphs[J].J Combin Theory Ser B, 1979, 26:205-216.

[10]C.Thomassen, Gr¨otzsch’s 3-color theorem and its counterparts for the torus and the projective plane[J].J Combin Theory Ser B,1994, 62:268-279.

[11]C.Thomassen, 5-coloring graphs on the torus[J].J Combin Theory Ser B, 1994, 62: 11-33.

[12]W.T.Tutte, On the imbedding of linear graph into surfaces[J].Proc London Math Soc Ser 2, 1949, 51: 464-483.

[13]P.A.Catlin, The reduction of graph family closed under contraction[J].Discrete Math ,1996, 160: 67-80.

[14]C.Q.Zhang, Integer flows and cycle covers of graphs[M].Marcel Dekker, New York, 1997.

[15]J.J.Chen, E.Eschen, H.J.Lai, Group connectivity of certain graphs[J].Ars Combinatoria, 2008,89:141-158

[16]Y.X.Yao, X.W.Li, H.J.Lai，Degree conditions for group connectivity[J].Discrete Math, 2010,310:1050-1058.

O157.5

A

1673-2219（2011）04-0009-04

2011－01－05

劉彥芬（1981－），女，河南南陽人，永城職業學院教師，主要從事圖論及其應用方面的研究。

（責任編校：京華）