SOME PROPERTIES OF A CLASS OF INTERCHANGE GRAPHS

§１ＩｎｔｒｏｄｕｃｔｉｏｎＬｅｔＧｂｅａｃｏｎｎｅｃｔｅｄｇｒａｐｈｗｉｔｈｖｅｒｔｅｘ－ｓｅｔＶ（Ｇ）ａｎｄｅｄｇｅ－ｓｅｔＥ（Ｇ）．Ｄｅｎｏｔｅｂｙｅ＝（ｘ，ｙ）ｔｈｅｅｄｇｅｊｏｉｎｉｎｇｔｈｅｖｅｒｔｉｃｅｓｘａｎｄｙｏｆＧ．Ａｍ－ｃｌｉｑ...     

6连通图中的可收缩边

Kriesell(2001年)猜想：如果κ连通图中任意两个相邻顶点的度的和至少是2[5κ/4]-1则图中有κ-可收缩边．本文证明每一个收缩临界6连通图中有两个相邻的度为6的顶点，由此推出该猜想对κ=6成立。     

本质集的邻域并和图的哈密尔顿性

Let G be a graph. An independent set Y in G is called an essential independent set (or essential set for simplicity) if there is {Y1, Y2} 包含于Y such that dist (y1,y2)=2. In this paper, we use the technique of the vertex insertion on l-connected (l=k or k 1, k≥2) graphs to provide a unified proof for G to be hamiltonian, or hamiltonian-connected. The sufficient conditions are expressed an inequality on ∑i=1 K|N(Yi)| b|N(y0)| and n(Y) for each essential set Y={y0,y1,…,yk}, where b (1≤b≤k）is an integer,Yi={yi,yi-1,…,yi-(b-1}包含于Y\{y0} for i属于V（G):dist(v,Y)≤2}|.     

3—连通正则无爪图的Hamilton圈

本文证明了：任一阶数不超过６ｋ－４的３－连通ｋ－正则无爪图是Ｈａｍｉｔｏｎ的。     

有向路和有向圈的控制集数

1引言设G=(V,E)为无向图．子集D (?)V(G)是无向图G的控制集,如果对于任意的y,∈V(G)-D,都存在x∈D,使xy∈E(G)．G的控制集D是G的分裂控制集,如果G中由V(G)-D导出的子图G〈V(G)-D〉是不连通的．G的一个控制集D是G的一个强(弱)控制集,若dG(x)≥d_G(y)(d_G(x)≤d_G(y)),其中d_G(x)表示G中与点x关联的边数．对于有向图H=(V,A),子集D(?)V(H)称为H的控制集,如果对于任意的y∈     

3—连通局部连通无爪图是泛连通图

本文证明了若G是连通、局部连通的无爪图,则G是泛连通图的充要条件为G是3-连通图.这意味着H.J.Broersma和H.J.Veldman猜想成立.     

P3-支配图哈密尔顿性的两个充分条件

在文献[3]中介绍了一个新的图类-P3-支配图.这个图类包含所有的拟无爪图,因此也包含所有的无爪图.在本文中,我们证明了每一个点数至少是3的三角形连通的P3-支配图是哈密尔顿的,但有一个例外图K1,1,3.同时,我们也证明了k-连通的(k≥2)的P3-支配图是哈密尔顿的,如果an(G)≤k,但有两个例外图K1,1,3 and K2,3.     

REFINED CONNECTIVITY PROPERTIES OF ABELIAN CAYLEY GRAPHS

1.IntroductionAgraphG=(V,E)meansafinitegraphwithoutloopsandmultipleedgeswithvertexsetVandedgesetE,theclassicaledgeconnectivityA(G)ofGistheminimumsizeofasetUofedgessuchthatG--Uisdisconnected,andsuchasetUiscalledaoutsetofG.Notethatintheabovedefinition,absolutelynoconditionsorrestrictionsareimposedeitheronthecomponelltsofG--UoronthesetU.ThusitwouldseemnaturaltogeneralizetheconceptofedgeconnectivitybyintroducingsomeconditionsorrestrictionsonthecomponentsofG--Uand/orthesetU.Asageneralizatio…