r-正则图的边连通度和k-对等性质

既是κ-覆盖又是κ-消去的图称为κ-对等图．给出了边连通度为λ的r-正则图是后．对等图的若干充分条件，得到了如下结论：设r，κ，λ均为正整数，G是边连通度为λ的r-正则图，λ≥2且｜V（G）｜为偶数、若r／λ≤κ≤r-r／λ，则G是κ-对等图．设r为奇数，后为偶数，G边连通度为λ（G）=λ≥2的r-正则图，λ^＊=2[λ／2]＋1．若2≤κ≤r-r／A^＊。则G为κ-对等图．     

关于r-(P_0,…,P_(t-1))—泛圈图

若G中长为r+tj+i的圈恰好有Pi(0≤i≤t-1)个,其中r+tj+t-1≤n,j是P_0,…,P_(t-1)重复的次数,则称G为r-(P_0,…,P_(t-1))-泛圈图.主要采用构造法,给出当t=8时r-(P_0,…,P_7)-泛圈图的一些结果 .即设n≥14,≥6若2-3+-3≤n2-2+-2且n-(r_((n,)-1))=s(mod8),s=0,1,…,7时,那么存在一个n阶r-(4,4,4,4,5,5,5,5)泛圈图,其中r=r_(0, λ)+s=﹛2~(λ-4)+3+s,当n≤3·2~(λ-4)+2时n-2~(λ-3)+1+s当n3·2~(λ-4)+2时同时,利用类似的方法证明了r-(1,1,3,3,4,4,5,5)—泛圈图、r-(4,4,4,4,5,5,5,5)—奇(偶)泛圈图以及r-(1,1,3,3,4,4,5,5)奇(偶)泛圈图.进一步,给出相应圈长分布的最小可能边数.     

完全t部图K(n-k,n-2,n,…,n)的色唯一性

文章介绍了完全t部图K(n-k,n-2,n,…,n)的色唯一性,设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图,通过比较t部图的t+1色类的划分数和三角形子图的个数证明,如果n>[(k+1)2/4]+1,并且k>2,则完全t部图K(n-k,n-2,n,…,n)是色唯一图。     

关于Enomoto和Saito的猜想

1985年Enomoto和Saito提出了下面的猜想:每一个r-正则图G有一个〔k-1,k〕-因子使每个分支是一个正则图,1≤k≤r.Kano证明了,当r是奇数且02r/3时在某些情况下上述猜想成立.     

自同构群作用下具有两个轨道的连通图的连通性(英文)

若连通图G在自同构群作用下具有两个轨道V1和V2且满足|V1|=|V2|;G[V1]是k-正则图;G[V2]是r-正则图且G[V1V2]是l-正则图,则K(G)≥min{k,r}+1.构造的例子表明上述结果是最好可能的.     

判断k-可序哈密顿-连通图的新条件

具有n个顶点的图G(n≥3)是k-可序哈密顿-连通的(k是整数,且2≤k≤n),如果对于G中每一个具有k个不同顶点的可序集合S={v1v2,…,vk},都存在G中的哈密顿路P包含S且不改变其中元素的次序.本文证明了:对于具有n个顶点的图G,u、v是G中任意两个不相邻的顶点,且d(u)+d(v)≥n+1.如果G是「k+1/2﹁-连通的k-可序图,k是整数且2≤k≤n/12,则G是k-可序哈密顿-连通图.     

一类r-(d0,d1,…,dt-1)-泛圈图的结果

设r,t,j是正整数,若对每一个r+tj+i(r+tj+i≤n),n阶简单图G中长为r+tj+i的圈恰好有di个,0≤i≤t?1,其中t是di的周期数,j是t重复的次数,则称图G为r-(d0,…,dt?1)-泛圈图.主要讨论了r-(6?2μ1,6?2μ1,8?2μ1,6?2μ1)-泛圈图,r-(6?2μ1,8?2μ1,...     

关于完全3部图的色唯一性

文章设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图;通过比较3部图的4色类的划分数证明,如果4≤v+2≤k≤2v,n>(k-1)2/4,则完全3部图K(n,n+v,n+k)是色唯一图。     

多叶生成树及N.Linial猜想

利用简单图G 的最小支配集顶点数γ刻画了该图的最多叶生成树中叶数的下确界。即 L(G)≥n-3γ+2。其中 L(G)表示图 G的生成树的叶数,n是G 的顶点数。同时对于 N.Linial 关于r-正则留图的最多叶生成树叶数的猜想公式 L(G)≥n·((r-2)/(r+1))+d 中的 d做出了估计,即 d≤(r+4)/(r+1) r=2k d≤(r+7)/(r+1) r=2k+1     

关于色多项式一次系数与简单图特征的若干结论

利用Whitnoy的著名结果 :P(G ,λ) = n - 1i =1 (- 1) ibiλn -i给出并证明了 :①G为连通偶图 ,当bn -1为奇数 ;②G为树 ,当bn -1=1;③分支数为k的图是偶图 ,当bn -k是奇数且bi=0 (n -k +1≤i≤n - 1)等八个定理     

k-对等图的邻集和最小度

证明了如下结论 :设G是阶数为n的二边连通的简单图 ,k≥ 2 ,k·n是偶数 ,并且n>4k + 1- 4 k .假设对V(G)的所有非空独立子集X都有 ｜N(X) ｜≥(k- 1)n+｜X｜+ 12k - 1并且δ(G) >(k- 1) (n+ 2 ) + 12k - 1,则G是k 对等图 .     

平面图的(4,1)*-可选性

图G称为 (k ,d) 可选的 ,如果对满足条件L(v) =k(v∈V(G) )的任意指派L ,存在G的一个L着色使得G的每一个顶点至多有d个邻点与之着同色 .本文证明了每个无 4 圈的平面图是 (4 ,1) 可选的 .     

（k，k-1）-双正则图的平衡Judicious Partitions

Bollobás和Scott提出猜想:任意一个边数为m且最小度大于1的图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数不超过m/3.Bollobds和Scott证明了绝大部分正则图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数比m/4小.这里讨论(k,k-1)-双正则图的平衡二部划分,证明了每一个(k,k-1).双正则图存在平衡二部划分使得每一部分点集的导出子图包含的边数是m/4左右.     

图的邻域并和连通的[k,k+1]-因子

设G是阶为n的图.F是G的支撑子图且对所有的x∈V(G)都有k≤dF(x)≤k+1,则称F为G的[k,k+1]-因子.一个[k,k+1]-因子如果连通,则称为连通的[k,k+1]-因子.一个[k,k+1]-因子若包含一个哈密顿圈,则称为哈密顿[k,k+1]-因子.给出了图有哈密顿[k,k+1]-因子或连通的[k,k+1]-因子关于邻域并的若干新的充分条件.     

排列图的代数性质

构造了一种新的Cayley陪集图,并且证明了这种Cayley陪集图能够被表示成〈n〉上的k-置换集V(An,k)上的置换图An,k,进一步说明了得到广泛深入研究的(n,k)-排列图An,k是基于对称群的Cayley陪集图,从而是点传递的.     

2－退化图的全色数

对任意简单图Ｇ，Δ（Ｇ）和ＸＴ（Ｇ）分别表示Ｇ的最大度和全色数．证明了当Δ（Ｇ）≥４时，２－退化图Ｇ的全色数ＸＴ（Ｇ）＝Δ（Ｇ）＋１．     

一类特殊图的顶点染色数

如果图G含有的所有最大团存在公共顶点,且公共顶点的个数为κ,就称此图为第κ类图。据此,本文给出了研究图的顶点染色的一种新方法,并以此研究了一类特殊图的顶点染色及一些图的顶点染色数。     

顶点距离大于2的局部化条件与hamiltonian图

对任意正整数i,若图G的导出子图L的顶点满足x,y∈V(L), dL(x,y)=imax{dG(x),dG(y)}≥|G|/2,则称L具有性质DL(i).设C(G)为图G的闭包,本文证明了下述结果任意一个C(G)=G且边连通度≥3的2-连通图,若存在正整数s使得G中的导出子图L满足(i) L(≌)K1.3有性质DL(2);(ii) 任意正整数i,1≤i≤s,L(≌)Bi有性质DL(i);(iii) L(≌)Z s+2有性质DL(s+2),则G为hamiltonian图.由此得到每个边连通度≥3的2-连通{K1.3;Bi,1≤i≤s}-free图, 若C(G)＝G且max{dG(x),dG(y) 对任意导出子图L(≌)Zs+2 ,dL(x,y)=s+2}≥|G|/2,则G一定是hamiltonian图.从而Fan条件中顶点距离可扩展为s+2.     

关于图G-v,G-e和W_(2n+1)的星色数

讨论了图Ｇ－ｖ与Ｇ－ｅ的星色数的一些基本性质，得到了一些不等式和等式．给出了等式χ＊（Ｇ）＝χ（Ｇ）成立的图Ｇ的一个特征，并进一步证明了χ＊（Ｗ２ｎ＋１）＝χ（Ｗ２ｎ＋１）＝４，从而回答了Ａ．Ｖｉｎｃｅ提出的某些问题．     

舵轮图都是强协调图

一个有e条边的简单图G称为是强协调的,若有V(G)到{0,1,…,e-1}的单射h,使导出映射h~*:h~*(uv)=h(u)+h(v)是由E(G)到{1,2,…,e}的一个双射。舵轮图H_n是由含n个顶点的圈C_n内添加一个与C_n的每个顶点都相邻的顶点,且再在C_n的每个顶点上都添上一条悬挂边而得到的图。本文中证明了,所有舵轮图都是强协调图,因而回答了[2]中一个open问题。