没有任意非零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－），女，河南南阳人，永城职业学院教师，主要从事图论及其应用方面的研究。

（责任编校：京华）