完全偶图的圈基内插性质

图G的一个圈基的长度是该圈基的所有圈的长度之和。设C^-、C^ 分别是G的最小、最大圈基长度,如果对任一偶数C,C^-＜C＜C^ ,都存在G的一个长为C的圈基,则称G具有偶圈基内插性质,本证明了,完全偶图Km,n具有偶圈基内插性质。     

局部大边宽嵌入图的最小圈基

利用Thomassen等人在大边宽嵌入方面的工作,给出局部大边宽嵌入的定义,并运用线性代数和相异代表系的知识,证明了局部大边宽嵌入图的最小圈基.     

Ford-Fulkerson算法与嵌入图中的短圈

关于嵌入图中最短圈的多项式算法的存在性问题,是由Thomassen最早提出的.本文通过改进的Ford-Fulkerson算法,可以得到最短割算法.另一方面,通过定义嵌入图的几何对偶图及其相应的嵌入系统,得到几何对偶图中的可分离圈就对应于原图中的割;反之,若几何对偶图中的割在原图中对应于-个圈,那么该圈一定可分离.从而在射影平面上解决了Mohar与Thomassen关于是否存在多项式算法寻找短圈的问题.对于-般曲面上嵌入图,只要它的面宽度充分大,那么同样有多项式算法发现最短可收缩圈.     

两个不交图的联图的最小圈基长度

这篇文章中,我们分两种情形分别给出了计算两个不交图的联图的最小圈基长度的公式.作为它们的应用,我们给出了计算n个相同的图的联图以及完全r-部图等图的最小圈基长度的公式.     

赋权图中存在重圈的一个定理的新证明

给出了如下定理的一个新的简短的证明:若G是一个满足k≥2的k连通赋权图,则G或者包含一个权至少为2m/(k 1)的圈,或者包含一个Hamilton圈,如果以下条件成立:(1)任意k 1个相互独立的顶点的赋权度和至少为m;(2)在G的每个导出爪,导出修正爪和导出P4中,所有边的权都相等.     

联图的圈基

MacLane于1937年给出了圈基方面的重要定理: 图G是平面图, 当且仅当图G有2-重基. 连通图G_1和G_2的联图G_1\vee G_2指的是在它们的不交并G_1\bigcup G_2上添加边集(u,v)|u\in V(G_1), v\in V(G_2). 对G_1和G_2的联图G_1\vee G_2的圈基重数进行了研究, 得到了一个上界, 改进了Zare的结果. 并在此基础之上, 进一步得到特殊联图C_m\vee C_n的圈基重数的一个上界.     

1-可嵌入曲面的图的边染色北大核心CSCD

一个图称为是1-可嵌入曲面的,当且仅当它可以画在一个曲面上,使得它的任何一条边最多交叉另外一条边.x′(G)和△(G)分别表示图G的边色数和最大度.给定图G是1-可嵌入到欧拉示性数x(∑)≥0的曲面∑上的图.如果△(G)≥8且不含4-圈或者△(G)≥7且围长g(G)≥4,则图G满足等式△(G)=x′(G),其中,g(G)表示图G中最短圈的长度.     

具有两个同阶轨道的双轨道图的圈边连通度

一个边割被称为圈边割,如果该边割能分离图的两个不同圈.如果一个图有圈边割,称该图为圈边可分离的.一个圈边可分离图G的最小圈边割的阶数被称为圈边连通度,记作cλ（G）.定义：ζ（G）=min{w（X）｜X导出G的最短圈},其中w（X）为端点分别在X和V（G）-X中的边的数目.如果一个圈边可分离图G使得cλ（G）=ζ（G）成立,称该图是圈边最优的.Tian和Meng在文章[11]以及Yang et al在文章[15]中研究了两种不同的双轨道图的圈边最优性.本文我们将研究具有两个同阶轨道的双轨道图的圈边连通度.     

第一类图的一个充分条件

图G的一个k-边染色是一个映射ψ:E(G)→{1,2…k},使得每一对相邻边x和y,有ψ(x)≠ψ(y,).G的边色数χ'(G)是使得G有一个k-边染色的最小的整数k.本文证明了:如果G是一个最大度为6能嵌入到欧拉示性数非负的曲面的图,且满足下列条件之一,那么χ'(G)=6:(1)不含带弦4-圈;(2)同时不含带弦5-圈和带弦6-圈.     

类圈图的亏格分布

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

边赋权图支撑树权的介值性

有关图的介值性,已有若干较好的结果,但这些结果都未涉及图的赋权。本文考虑边赋权图支撑树权的介值性。证明了定理A 设双射w:E(G)→{1,2,…|E(G)|}是连通图G=(V(G),E(G))的边赋权,如果存在G的圈基使w在它的每个圈上的象集为连续整数集,则w((G))={w(e)|T∈J(G)}是连续整数集。其中(G)是G的支撑树的集合。     

赋权图中的路和圈

本文研究了赋权图中的最长路和最长圈,将关于非赋权图中最长路和最长圈的一些结果推广到赋权图上.     

Ore度和条件下赋权triangle-free图中的重圈(英文)

设G是一个2-连通赋权图,且G中每一对不相邻顶点u和v都满足d~w(u)+d~w(v)≥2d.Bondy等人证明了G或者包含一个哈密尔顿圈,或者包含一个权至少为2d的圈.如果G不是哈密尔顿图,这个结论意味着G中包含一个权至少为2d的圈.但是当G是哈密尔顿图时,我们不能判断G是否包含一个权至少为2d的圈.这篇文章中,在Fujisawa的一篇文章的启发下,我们证明了当G是triangle-free图并且|V(G)|是奇数时,G中一定包含一个权至少为2d的圈,即使G是哈密尔顿图.     

不含4-,6-圈和相交三角形的平面图的无圈边色数

图G的一个边染色φ:E(G)→{1,2,…,k},若满足任意相邻边都染不同的颜色,且图G不存在双色圈,则称φ为图G的一个无圈k-边染色.图G的无圈边色数χ’_α(G)为使得图G有一个无圈k-边染色的最小正整数k.本文主要证明了对于无4-,6-圈且3-圈与3-圈不相交的平面图G,若Δ(G)≥9,则χ’_α(G)≤Δ(G)+1.     

简单图圈基长度的最大值

图的圈基是图的一个重要结构，一个圈基的长度是该圈基中所有圈的长度之和，本讲座了简单图的圈基长度的最大值，得到了如下结果：设基圈数为k，顶点数为n的简单图的圈基长度最大值为C^*,i)若k≥4且n ≥k 2时，C^*-kn；Ⅱ）若k=2,3,则对任意n≥4，C^*=kn-1,Ⅲ）若n(n≥5）为奇数，则对k(k≥4）的所有可能值，C^*=kn。     

嵌入曲面的特殊图的边染色

设图G是嵌入到欧拉示性数χ(∑)≥0的曲面上的图,χ′(G)和△(G)分别表示图G的边色数和最大度.将证明如果G满足以下条件:1)△(G)≥5;2)图中3-圈和4-圈不相邻;3)图G中没有5-圈的一次剖分,则有χ′(G)=△(G).     

超图的路和圈

超图是离散数学中最一般最复杂的结构 .无圈超图已被证明在数据库设计中非常有用 .从关系数据的结构出发 ,建立了关于超图的路、连通性和圈的新的公理系统 .该系统与特殊情形———图是符合的 .引入了虚圈和实圈的概念 ,这是一对相关联的概念 .虚圈在特殊情形———图中不存在 ,退化掉了 .定义了超图圈的相关性和独立性 ,给出了超图中最大独立实圈数目的计数公式 ,对特殊情形———图 ,这个公式就是Euler公式 .     

一类三圈图的Wiener指数

图G的Wiener指数是指图G中所有顶点对间的距离之和,即W（G）=∑dc（u,u）,{u,u}CG其中de（u,u）表示G中顶点u,u之间的距离.三圈图是指边数与顶点数之差等于2的连通图,任意两个圈至多只有一个公共点的三圈图记为T_n~3.研究了三圈图T_n~3的Wiener指数,给出了其具有最小、次小Wiener指数的图结构.     

一般图的哈密顿图的研究进展

1991年刘振宏和李明楚在南京大学召开的首届哈密顿图研讨会的综述文章中说"要给出一个一般图具有哈密顿圈的充分条件是一件非常不容易的事"。因哈密顿图是含哈密顿圈的图类,如此哈密顿图主要有六个方向:哈密顿圈、哈密顿连通、泛圈图、点泛圈图、泛连通图、最短路径泛圈图。本文中,我们就给出一般图的这些领域新进展的小综述。     

1-可嵌入曲面的图的边染色

一个图称为是1-可嵌入曲面的,当且仅当它可以画在一个曲面上,使得它的任何一条边最多交叉另外一条边.x′(G)和△(G)分别表示图G的边色数和最大度.给定图G是1-可嵌入到欧拉示性数x(∑)≥0的曲面∑上的图.如果△(G)≥8且不含4-圈或者△(G)≥7且围长g(G)≥4,则图G满足等式△(G)=x′(G),其中,g(G)表示图G中最短圈的长度.