无向和有向Euler环游变换图的直径

本文得到了无向和有向Ｅｕｌｅｒ环游交换图的直径的上界．（１）设Ｇ是一个无向Ｅｕｌｅｒ多重图．令Ｑ（Ｇ）＝｛ｖ∈Ｖ（Ｇ）｜ｄｖ的Ｅｕｌｅｒ环游（Ｋ－）变换图Ｅｕ（Ｇ）的直径ｄｉａｍ（Ｅｕ（Ｇ））≤λ（Ｃ）－３．（２）设Ｄ是一个有向Ｅｕｌｅｒ多重图，ｄ（ｖ）＝ｉｄ（ｖ）＝ｏｄ（ｖ），令Ｑ（Ｄ）＝｛ｖ∈Ｖ（Ｄ）｜ｄ（ｖ）≥２｝及。则Ｄ的有向Ｅｕｌｅｒ环游（Ｔ－）变换图Ｅｕ．（Ｄ）的直径我们给出例子说明这两个上界都是最佳可能的．     

广义笛卡尔积图的连通度

本文定义了图G_1、G_2的广义笛卡尔积图G=G_1∫G_2,并且证明了它们的连通度具有关系k(G)≥k(G_1)+k(G_2)。这一结果是对文[1]中关于G_1与G_2直积的结果的推广。此外,本文还讨论了G=G_1∫G_2的直径及Hamilton性。最后,利用G=G_1∫G_2的结果对循环图的连通度进行了讨论。     

有向循环图的连通度

本文给出了有向循环图连通度达到其最小度的一个充要条件.     

小度数点传递图的连通度

众所周知,ｋ（ｋ≤４）正则连通点传递图的连通度达到了它的正则度ｋ,本文证明了除Ｃｎ◎Ｋ２（ｎ≥４）外,每个５正则连通点传递图的连通度都是５,其中Ｃｎ◎Ｋ２是ｎ长圈与完全图Ｋ２的字典积。     

广义Mycielskian图的连通度(英文)

Mycieski定义了一个图的运算即把一个图G变换为一个称为G的Mycielskian图的新图μ(G).广义Mycielskian图μm(G)(m≥0)是图的Mycielskian图的一个自然推广.本文证明对任意非平凡连通图G有κ(μm(G))=min{δ(G)+1,(m+1)κ(G)+1},而且对于m,i≥1,λ(μm(G))=λ(G)+i当且仅当δ(G)=λ(G)+i 1,其中κ(G),λ(G)和δ(G)分别为图G的连通度,边连通度和最小度.     

变换图τ_2(G)连通度

M.Farber 等在[2]中引入了“边不交的生成树对”的变换图τ_2(G)的定义,证明了它是连通的.本文讨论了τ_2(G)的连通度,得到了一个下界.特别地,对于2-补树图,即恰含有两个边不交的生成树的图,本文先给出了一种递归方法去构造全体2-补树图,然后证明了2-补树图 G 的τ_2(G)的连通度≥|V(G)|-1,井给出了例子,说明这一下界是最佳可能的.     

0—1多面体图连通度猜想的一个反例

本文给出０－１多面体图连通度猜想的一个反例。由此说明０－１多面体图的连通度未必等于最小度。     

Harary图的外连通度(英文)

一个顶点集是一个Rg-点割,如果它将一个连通图分割成一些连通分支使得每个连通分支至少含有g个顶点.图G的g-外连通度(记作κg(G))是Rg-点割的最小基数.图G的通常的点连通度和上连通度分别相应的为κ0(G)和κ1(G).本文将分别证出第一类和第二类Harary图的κg和刻画它们的Rg-点原子部分.     

完全图K7上欧拉链和欧拉闭链的计数

文[1]提出了 K_(2n 1)上有多少条欧拉链的计数问题,其中已知 K_3 上有一条欧拉链,K_5 上有22条欧拉链,对于 K_(2n 1)(n≥3)上有多少条欧拉链的计数问题没有解决.本文计算出 K_7 上的欧拉链的数目为541568条,在此基础上又计算出 K_7 上的欧拉闭链的数目为180544条,并估计出 K_(2n 1)(n≥4)上欧拉链的数目的一个上界.     

线图的邻域连通度

研究了图G的边邻域连通度λNB（G）和它的线图L（G）的点邻域连通度κNB（L（G））之间的关系,证明了AλB（G）≤κNB（G）．提出了一个新的概念：限制性边邻域连通度λrNB（G）,证明了κNB（L（G））≤λArNB（G）．最后,研究了上述两个不等式成为等式的充分条件．     

传递图中的限制性边连通度

设G=(V，E)是一个连通图，S包含于E是一个边子集，如果G—S不再连通，且G—S的每一个连通分支都至少含有r个点，则称S为一个r-限制性边割．最小r-限制性边割中所含的边数为G的r-限制性边连通度，记作λ(G)．如果对所有的i=1，…，r，λ(G)都达到其最大可能值，则称G为λ-最优图．王铭和李乔证明了：若G是一个d-正则的点传递图，d≥4，围长g≥5，或者G是一个d-正则的边传递图，d≥4，围长g≥4，则G是λ（g-1)-最优图．本文推广了这一结果，证明了：在同样的条件下，G是λg-最优图．     

线图和有向线图的第二等周点连通度

证明了最小度大于等于2的强连通有向线图的第二等周点连通度等于它的点连通度.对于无向线图,给出了第二等周点连通度存在的充要条件,并且证明了在第二等周点连通度存在的前提下它或者等于限制点连通度或者等于d1 d2,其中d1和d2分别是最小和次小度.     

关于二部图和欧拉图的列表着色

设G-（V．E）是二部图．D是G的一个定向具有出度序列（dD^＋（v）｜v∈V）．设fD（v）=dD^＋（v）＋1是定义在V上的整数函数．在本文中我们利用代数方法证明了G是fD-可选的，并由此推出G是（[（（△（G））/2]＋1）-可选的．2d-正则偶图是（d＋1）-可选的．定义了欧拉图的半度-可选概念．并给出了一类半度-可选的欧拉非偶图．最后，提出了刻化半度-可选的欧拉图．     

对称群上Cayley图的连通性

本文研究限制性边连通度的λ′-原子．运用所得结果可以证明Cayley图C(Sn,S)是最优超-λ的．这里Sn是n次对称群,S是若干由奇置换构成的共轭类的并，另外，我们还证明了C(Sn，S)是Vosperian的．除非它是完全二部图．     

ABMV中函数的Euler平均逼近

本文考虑了ABMV函数的Euler平均逼近,给出了逼近阶的估计,