曲面上构造三次3-连通非Hamiltonian地图的一种方法(英文)

Tutte在1946年构造性证明了并非每个简单的3-凸胞腔都是Hamiltonian的后,人们又陆续提出了多种构造三次3-连通非Hamiltonian平面图的方法,但无一能用于在一般曲面上寻找三次3-连通非Hamiltonian地图.本文提出了一种新的构造方法,可在任一个曲面上构造出三次3-连通非Hamiltonian地图.

树的自同构群的一个新的恒等式(英文)

通过计数给定基础图的标根地图数,本文得到了树的自同构群的如下恒等式 这里T(n),D(T)分别表示n阶不同构树集,树T的次序列.

图的可定向嵌入的标根可数性

给定一族图 G,可定向曲面上存在多少个以其中某个图为基础图的标根地图 ?采用图的自同构群对图在可定向曲面上的嵌入集合进行分类 ,该文解决了这个问题 ,同时得到了求解计数函数 fr( M)的一种新的方法 .

图的离心率值列的研究(英文)

设 G为一个图 ,对 x∈ V(G) ,其离心率 e(x)定义为 e(x) =max{ d(x,u) | u∈ V(G) }。将 G中各点的离心率的值按照 (不重复 )从小到大排列而得到的数列称为 G的离心率值列。现设 { ei} 1≤ i s为一个非减的整数数列。本文得到了下面三个结果 :(i) { ei} 1 i s是图的离心率值列当且仅当 { ei} 1 i s=[e1 ,es]且 e1 ≥ 1,es≤ 2 e1 ;(ii)定义 NG(e) ={ x|x∈ V(G)且 e(x) =e} ,若 |NG(e) |=1则 e =r(G) ;(iii)有给定离心率值列 [r,r +s]的图的最小阶 f [r,r +s]为f [r,r +s]=2 r +s,若 0≤ s≤ r - 2 ;r +s+1,若 s=r - 1或 r;这里 ,[s,s+k]表示 [r,r +s]数列 { r - 1+i} 1≤ i≤ s+ 1 。

完全二部图的少面数强嵌入

通过调整完全二部图G的少双圈覆盖中的某些圈 ,可得到一个强嵌入 ,不同的双圈覆盖可以得到不同的强嵌入 .最后作为推论 ,得到完全三部图Kn ,n ,n可以强嵌入到某一亏格的曲面上 .

哈密尔顿图的局部化临域并条件(英文)

采用图的局部化临域并条件 ,本文证明了下述结果 :设G是一个p阶 2 -连通图 ,Li- <G ,i=1,2 (L1≠L2或L1=L2 )且对任意顶点xi,yi∈V(Li) ,i=1,2和 {x1,y1}≠ {x2 ,y2 } ,dLi(xi,yi) =2 ,有下列不等式(D) 3|N(x1)∪N(y1) |+3|N(x2 )∪N(y2 ) |≥ 4p - 2 ,(1)若Li≌K1.3 或K1.3 +e ,i=1,2 ,则G为哈密尔顿图 .(2 )若Li≌K1.3 +e或P4 ,i=1,2 ,则除非G中有一个强D1-圈 ,G一定是哈密尔顿图t这一结果推广了Lindquester的结果 :每个p阶 2 -连通图G ,若有NC2≥ (2p - 1) /3,则一定是哈密尔顿图 .

Cayley图的泛因子性质(英文)

一个κ-正则图若满足对任意正整数s,1≤s≤κ,均存在一个s-因子或一个2[s/2]因子,则称其有泛因子或偶泛因子性质.本文证明了每个奇度Cayley图是泛因子的,每个偶度Carley图是偶泛因子的.同时证明了二面体群上的每个Cayley图均是泛因子的.