连通、几乎局部连通无爪图是完全圈可扩的

设Ｇ是一个图,Ｂ ＝ ｛ｖ ∈Ｖ（Ｇ）｜〈Ｎ（ｖ）〉不连通｝．如果Ｂ是独立集,并且ｖ ∈Ｂ,ｕ ∈Ｖ（Ｇ）, 使〈Ｎ（ｕ） ∪｛ｕ｝〉连通,则称Ｇ是几乎局部连通图．本文证明：连通、几乎局部连通无爪图是完全圈可扩的．     

Petersen图中包含给定边集的最长圈及其在3－正则图中的应用

给出了Petersen图中包含给定边集的最长圈的结果及该结果在3-连通、3-正则图中的应用;最后提出两个问题。     

局部几乎正则多部竞赛图中的分量共轭圈

一个n-部竞赛图是n-部完全图的一个定向.令V₁,V₂,…,V_n是n-部有向图D的部集.如果D中存在两个不相交的圈C和C'使得对于每一个i∈{1,2,…,n}都有V_i∩(V(C)∪V(C'))≠ƒ,则称C和C'是D的一对分量共轭圈.针对多部竞赛图的共轭圈问题,提出了分量共轭圈的定义,同时证明了每一个至少有6个顶点的部集具有相等基数的局部几乎正则多部竞赛图的分量共轭圈的存在性问题.     

无界时延混合Petri网(UTHPN)的可覆盖性演变图及性质

时延混合Petri网(THPN)是由David最早提出的一类混合Petri网模型,而构造时延混合Petri网的演变图是对其性质进行分析的有效方法.赵义军等在文[1]中给出了有界时延混合Petri网的演变图构造方法及性质分析,但对无界的时延混合Petri网,其演变图却不能用同样的方法构造出来.在本文中,通过引入无界量符号ω,给出了UTHPN的可覆盖性演变图的构造方法,并在此基础上讨论了UTHPN的有关性质.     

PATH EXTENSIBILITY OF CONNECTED,LOCALLY 2-CONNECTED K_(1,3)-FREE GRAPHS

1.IntroductionandNotationqInthispaperswewillconsideronlyfinite,undirectedgraphs,withoutloopsandmultipleedges.Weusethenotationsandterminologyin[1].Inaddition,ifGisagraph,wedenotebyV(G)andE(G),respectively,thevertexsetandtheedgesetofG.ForanyaEV(G),ACV(G),BC…     

HAMILTONICITY IN 2-CONNECTED {K_(1,3) F}-FREE GRAPHS

ＨＡＭＩＬＴＯＮＩＣＩＴＹＩＮ２－ＣＯＮＮＥＣＴＥＤ｛Ｋ_（１，３）Ｆ｝－ＦＲＥＥＧＲＡＰＨＳ￥ＬＩＧｕｏｊｕｎ（ＭａｔｈｅｍａｔｉｃｓＤｅｐｅｒｔｍｅｎｔｏｆＹａｎｔａｉＴｅａｃｈｅｒ＇ｓＣｏｌｌｅｇｅ，Ｙａｎｔａｉ２６４０００，Ｃｈｉｎａ）ＬＩＵ?..     

LONGEST CYCLES IN REGULAR 3—CONNECTED GRAPHS

It is proved that for k≥71,the circumference c(G)of a 3-connected k-regular graphG on n vertices is at least min{|G|,3k+5}.This result is essentially best possible.     

A Degree Condition on Long Paths and Large Cycles

We present a new condition ensuring the existence of a large cycle of passing throughgiven edge.Let l(C)denote the length of the cycle C.Suppose G is a 4-connected graph withvertices set{x_1,x_2….x_n}and edge set E and with the property that,for any two positiveintegers j and k,j相似文献   

CONNECTED [1, k]-FACTORS OF BALANCE BIPARTITE GRAPHS

1.IntroductionAllgraphsconsideredaresimpleandfinite.Wereferthereaderto[1]forstandardgraphterminologiesnotdefinedinthispaper.LetGbeagraphwithvertexsetV(G)andedgesetE(G).ForanySCV(G),wedenotebyNG(S)theneighborsetofSinG,anddefineNG[S]=NG(S)US.LetdG(v)denotethedegreeofvinG.IfwewriteG=(VI,VZ),itmeansthatGisabipartitegraphwiththepartition(VI,V2)ofV(G).IfIVII=IVZI,wecallGabalancebipartitegraph.LetafbbetwopositiveintegerssuchthataSb.AspanningsubgraphFofGiscalledan[a,b]-factorofGi…     

A LOCALIZATION CONDITION FORBIPANCYCLIC BIPARTITE GRAPHS

1.IntroductionThefollowingNash--william'stheoremtellsusthatthehamiltonianproblemconcerningbipartitegraphsisimportant,thoughwedonotseemuchliteratureonit.Theorem111]Thejollowingproblemsareequivalent:1)thedete~inationofallhamiltoniangmphs,2)thedete~inationof…     

A CONNECTED GRAPH IS PATH-POSITIVE IFF ITS SPECTRAL RADIUS IS AT LEAST TWO

ＡＣＯＮＮＥＣＴＥＤＧＲＡＰＨＩＳＰＡＴＨ－ＰＯＳＩＴＩＶＥＩＦＦＩＴＳＳＰＥＣＴＲＡＬＲＡＤＩＵＳＩＳＡＴＬＥＡＳＴＴＷＯ￥ＳＨＩＲｏｎｇｈｕａ（ＤｅｐａｒｔｍｅｎｔｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，ＮａｎｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＳ...     

Star Chromatic Numbers of Planar Graphs

１ＩｎｔｒｏｄｕｃｔｉｏｎＤｅｆｉｎｉｔｉｏｎ１．１Ｌｅｔｋ,ｄｂｅｎａｔｕｒａｌｎｕｍｂｅｒｓｓｕｃｈｔｈａｔｋ２ｄ,ａ（ｋ,ｄ）－ｃｏｌｏｒｉｎｇｏｆａｇｒａｐｈＧ＝（Ｖ,Ｅ）ｉｓａｍａｐｐｉｎｇｃ：Ｖ→Ｚｋ,ｓｕｃｈｔｈａｔｆｏｒｅａｃｈｅｄ...