Halin图在环面上嵌入的性质

利用拓扑的方法,研究了Halin图在环面上的不同嵌入数目与其叶圈是否可收缩有关,并给出了Halin图在环面上的简单圈基性质,从而推广了Josef Leydold、Peter F.Stadler等人的相关结果.     

图的最大亏格综述(英文)

综述了近30年来关于图的最大亏格,以及它与其他不变量之间关系的重要研究进展,包括最大亏格与图的连通性、图的直径、图的染色数和图的z-因子之间的关系,最大亏格嵌入数,以及最大亏格与嵌入图等方面.     

一类近三角剖分图的上可嵌入性

-个图在某个曲面上的嵌入三角剖分该曲面.那么这个图是上可嵌入的,对于一个近三角剖分图却不一定是上可嵌人的.已经证明了平面近三角剖分图的上可嵌人性与独立边集之间的关系是:若G的对偶图G*有[1/2φ]个独立边集.那么图G的最大亏格γM(G)=(「)β(G)/2」-1.进一步讨论了平面近三角剖面图G有k个三角△1,△2,…,△k其上可嵌人的条件.     

图和它补图的上可嵌入性

主要得到了如下结果:如果G是一个重图,那么图G或者它的补图Gc是上可嵌入的.     

直径为2与3的符号图的上可嵌入

设Σ=(G,σ)是直径为2和3连通的简单符号图,G是Σ的基础图.若Σ扭转等价Δ_2-图或Δ_3-图,则Σ的Betti亏数ξ(Σ)=2,否则Σ是上可嵌入的,即ξ(Σ)≤1.     

图的上可嵌入性的一些表征

提供了这样一个事实：在一个简单图Ｇ和它的补Ｇ￣Ｃ中，总有一个是上可嵌入的。同时，也给出了一个图不是可嵌入的一个结构特征。     

G的立方图G~3的上可嵌入性

自从Nordhaus,Stewart和White[1]等引入图的最大亏格以来,图的最大亏格以及图的上可嵌入引起了广泛关注.而图的最大亏格rM(G)是指最大的整数k使得图G的一个2 胞腔嵌入到可定向的曲面Sk上.因为图在任意可定向曲面上的2 胞腔嵌入中至少有一个面,关于图的上可嵌入性,刘彦佩[2],Xuong[3]和Nebseky[4]分别给出不同形式的充要条件.主要证明下述结果:设G是一个简单图,则G3是上可嵌入的.特别地,当k≥4时,Gk也是上可嵌入的.     

上可嵌入图类

利用图的一些特殊性质,比如图的顶点存在一个C-划分,或者每条边都属于一个3-圈或者图不含割点等,研究图的最大亏格,从而得到一些上可嵌入图类.     

图的上可嵌入性与2-因子（英文）

对含有4边形2因子的3连通图和k正则图的上可嵌入性进行了讨论,得到了一些上可嵌入图类.     

3-边连通图的Betti亏数与奇度点

图G是3-边连通的且G的奇度点的数目为k.若k小于等于4,则G是上可嵌入的; 若k大于等于6,则ξ(G)小于等于k/2减去1.而且当k不小于6时,存在无限多个3边连通图G使得ξ(G)等于k/2减去1.     

Claw─centre Independent Graphs

Ｃｌａｗ┐ｃｅｎｔｒｅＩｎｄｅｐｅｎｄｅｎｔＧｒａｐｈｓＬｕＭｅｉ（陆玫）ＤｅｐａｒｔｍｅｎｔｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，ＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００８４Ａｂｓｔｒａｃｔ：ＩｆＦｉｓａｇｒａｐｈ，ｔｈｅｎ...     

连通、弱局部连通、K1,P-约束图的完全圈可扩性

给出了弱局部连通的定义，证明了顶点数不少于3的连通图、弱局部连通图、Kl,p-约束图是完全圈可扩的，改进了朱永津、王江鲁(1998)文中关于蜀Kl，p-约束图的完全圈可扩性的相应结果。     

拟无爪图的完全圈可扩性

拟无爪图是比无爪图更广泛的图类.证明如下结论:(i)顶点数 n ≥ 3 的连通、局部连通的拟无爪图是完全圈可扩的;(ii)若 G2是顶点数 n ≥ 3 的连通的拟无爪图,则G2是完全圈可扩的.这些结论推广了无爪图及拟无爪图中的相应结论.     

T3-受限图的路可扩性

剖分无爪图K1.3的一边所得到的图形称为L图，如果图G中任意一个与T3同构的导出子图的3个1度顶点之间至少有一条边，则称图G为T3-受限图．证明了连通、局部3-连通的L-受限图是路可扩的．     

完全扩容图的点圈扩张性

目的讨论了完全扩容图的圈扩张性。阿勇嘎在2011年给出了完全扩容图的概念，完全扩容图是G□L（G）唯一的非平凡分支，其中L（G）是G的线图。方法利用归纳法对其进行讨论。结果与结论对于最小度大于2的连通且局部连通的完全扩容图，它的任一点由所在的一个6-圈经过若干次1或2-扩张，最后得到哈密顿圈。     

几乎局部连通［4,2］-图的圈可扩性

如果图G的任意s个顶点的导出子图中至少含有t条边,则称图G为［s,t］-图。本文证明:连通、几乎局部连通［4,2］-图中任意一个满足5≤｜C｜≤｜G｜的圈是可扩的。     

基于核的有向强连通图计算机随机生成算法

针对图论算法研究和算法测试对随机生成有向强连通图的需求,在深入研究有向强连通图和极小有向强连通图的结构组成的基础上,提出了有向强连通图核的概念。参考有向连通图的随机生成算法,给出了一种有向强连通图的随机生成算法,并对该算法进行了测试。对具有上千个节点及上万条弧的强连通图的随机生成,采用该算法时间都在1 s以内,生成的结果能很好地应用于图论研究,以作为图论算法的随机测试用例。     

[4,1]-图的圈可扩性

如果图G的任意s个顶点的导出子图中至少含有t条边,则称图G为[s,t]-图。本文证明了连通、局部2-连通[4,1]-图是完全圈可扩的。     

4－连通无爪图中的Hamilton圈

Ｍａｔｔｈｅｗｓ等猜想：每一个４－连通无爪图是Ｈ－图．本文证实当Ｇ不含局部连通点及３团时该猜想成立．     

连通、局部2-连通[4，2]-图的路可扩性

如果G中任意s个点的导出子图中至少含有t条边，则称图G为[s，t]-图。证明了：设G是连通、局部2-连通的[4，2]．图，则G或者含有与K1.1，1.3同构的子图，或者是路可扩的。