亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

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

        2011-10-28 02:32:42劉彥芬秦健楊星星
        湖南科技學院學報 2011年4期
        關鍵詞:邊數(shù)永城約簡

        劉彥芬 秦健 楊星星

        (1.永城職業(yè)學院,河南 永城 476600;2.徐州建筑職業(yè)技術學院,江蘇 徐州 221116;3.中國礦業(yè)大學,江蘇 徐州 221008)

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

        劉彥芬1秦健2楊星星3

        (1.永城職業(yè)學院,河南 永城 476600;2.徐州建筑職業(yè)技術學院,江蘇 徐州 221116;3.中國礦業(yè)大學,江蘇 徐州 221008)

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

        邊數(shù);任意非零4-流;2邊連通

        0 引言

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

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

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

        1 主要引理

        引理1[4]設G為階數(shù)為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-邊連通且階數(shù)為n的簡單圖,取p為滿足p≥2的整數(shù),如果

        那么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)的結論相同,但條件有了減弱。盡管只是將邊數(shù)減少了1,

        這樣的圖存在無數(shù)多個。

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

        [2]鄭藝容.乘積圖的非零整數(shù)流和完美匹配單圈圖的特征值[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-),女,河南南陽人,永城職業(yè)學院教師,主要從事圖論及其應用方面的研究。

        (責任編校:京華)

        猜你喜歡
        邊數(shù)永城約簡
        多邊形內(nèi)角和、外角和定理專練
        河南永城:裹包玉米走俏 農(nóng)民省心增收
        基于二進制鏈表的粗糙集屬性約簡
        實值多變量維數(shù)約簡:綜述
        自動化學報(2018年2期)2018-04-12 05:46:01
        基于模糊貼近度的屬性約簡
        中糧集團百萬頭生豬產(chǎn)業(yè)鏈項目落戶永城
        西江邊數(shù)大船
        歌海(2016年3期)2016-08-25 09:07:22
        最大度為10的邊染色臨界圖邊數(shù)的新下界
        一種改進的分布約簡與最大分布約簡求法
        河南科技(2014年7期)2014-02-27 14:11:29
        由商丘入永城途中作
        国产办公室秘书无码精品99| 免费无遮挡毛片中文字幕| 女同国产日韩精品在线| 日本超级老熟女影音播放| 午夜理论片yy6080私人影院| 久热在线播放中文字幕| 亚洲AV永久无码精品表情包| 亚洲最大av在线精品国产| 草草地址线路①屁屁影院成人| 亚洲粉嫩高潮的18p| 中文字幕无码高清一区二区三区 | 国产在线视频一区二区三区| 国产精品一区二区三区专区| 午夜福利理论片高清在线观看| 另类免费视频在线视频二区| 亚洲AV无码日韩一区二区乱| 亚洲精品在线一区二区| 无码人妻丰满熟妇区bbbbxxxx | av 日韩 人妻 黑人 综合 无码| 天天做天天爱天天综合网| 白白色免费视频一区二区| 亚洲中文字幕诱惑第一页| 91精品国产一区国产二区久久| 日韩av无码中文无码电影| 抽搐一进一出试看60秒体验区| 久国产精品久久精品国产四虎 | 丝袜欧美视频首页在线| 日韩国产一区二区三区在线观看 | 国产精品久久久亚洲| 国产午夜福利小视频合集| 亚洲中文字幕乱码免费| 免费看草逼操爽视频网站| 性猛交ⅹxxx富婆视频| 亚洲老妇色熟女老太| 日韩中文字幕精品免费一区| 亚洲一区二区懂色av| 国产精品无码人妻在线| 欧美性大战久久久久久久| 99热这里只有精品久久6| av在线不卡免费中文网| 人妻少妇出轨中文字幕|