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

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

A TIGHT LOWER BOUND ON THE MAXIMUM GENUS OF 3-EDGE CONNECTED LOOPLESS GRAPHS

1.IntroductionThernchmumgenusl7M(G),ofacormectedgraphG~(V,E)isthem~amongthegenera,amongwhichGhasacellularembeddingonaspherewithkhandles.SinceanyembeddingofGhasatleastonefaCe,byEulerpolyhedralequation,itcanbeobtainedthatwhereP(G)=IE(G)I--IV(G)l IisthecyclerankofG.AgraphGiscalledop-imbeddableif7M(C)=Lop]exactly.Kund.[1]provedthatthereareatleasttWOedge-disjointspanningtreesinGifGis4-edgecormected.LiuandXuongcharacterizedtheuptheeddabilityofgraphsasinthefollowing.Theorem1.112'31.Acorm…     

关于图的上可嵌入性的一个充分条件

本文主要证明:设G是一个(k+1)-边连通的n阶简单图,其围长为g,如果对G的任意独立集I(G)={v_i|1≤i≤k~2+2},k=0,1,2,均满足那么图G是上可嵌入的,而且下界是紧的.     

类圈图的亏格分布

一个图 G 的亏格分布是指序列{g_k}, g_k表示 G 嵌入亏格为 k 的闭的可定向曲面的数目. 该文给出了标准类圈图的亏格分布的递推公式, 并得到类圈图的嵌入多项式的计算公式.     

平面与射影平面上近-$4$-正则地

设${\cal U}_n$ 和 ${\overline{     

嵌入在克莱茵瓶上的图的最大亏格

设$\phi: G\rightarrow S$是图$G$在曲面$S$上的2 -胞腔嵌入. 若$G$的所有面都是依次相邻, 即嵌入图$G$的对偶图有哈密顿圈, 则将$\phi$称为一个面依次相邻的嵌入. 该文研究了在克莱茵瓶上有面依次相邻嵌入的图的最大亏格.     

我所了解的图论(四)

第六讲群与图——图论中的对称性在我介绍关于拼方的早期工作时,曾提及四名研究者怎样从Brooks太太那里了解到在他们的图中对称性的重要.现在,我打算较详细地谈谈对称性.他们处理的对象称为“转子”,即具有旋转对称性的图.一个图称为转子,若它是连通的且具有一个有限阶n的自同构θ.即自同构θ,θ~2,…,θ~(n-1)互不相同,而θ~n是恒等自同构I.而且,这个图一定要有n个“边界”顶点集A_1,A_2,…,A_n=A_o,它们在由θ生成的循环群之下是等价的.就是说,它们满足     

射影平面上不可分近三角剖分地图的计算

众所周知,由于本质圈(或不可收缩圈)的作用,使得一般的曲面上要得到带有两到三个参数的地图计算公式(尤其是显式公式)变得十分困难。该文集中讨论射影平面上不可分近三角剖分地图的计算。通过引入含有面次,边数和内部面数的参数表达式与Lagrangian反演,作者得到了含有正项系数的显式公式用以计算射影平面上三角剖分地图 。     

关于有根简单平面三角地图数目的一个注记

一个地图,指图在某曲面上的一个嵌入.平面地图,自然就是在平面上的嵌入.三角平面地图,即所有面皆三角形的平面地图.一个地图,如果将它的一条边规定一个特殊的方向,此边称为根边.根边的始端称为根点,沿根边的方向走左手边的面称为根面,则这时称这个地图为有根的.之谓二个有根的地图是不同的,或曰组合上不等价,指二者之间不存在一个同构映像使得它们根点、根边和根面也相应.可想而知,研究有根地图的组合不变性与研究一般地图的组合不变性在根多情况下是一致的.特别是在着色理论中有根和无根一个样.然,