关于图与圈之并图的圈唯一性

Farrell[1]引进图 G 的圈多项式 c(G;■).文[6]猜测:轮形图 W_8是圈唯一的.本文中我们证明上述猜测为真且讨论了某些图与圈之并图的圈唯一性.     

三次平面图中包含六点二边集的圈

得到了３－连通三次平面图具包含其给定六点二边集的圈的一个充分必要条件。并且列出一些悬而未决的研究问题。     

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

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

泛圈图方面的著名Bondy定理的简单证明

本文用极好的新方法给出泛图图方面的Bondy定理的简捷证明。     

超图的路和圈

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

拟阵的可去圈

本首先用拟阵语言将图论的新概念定义成了拟阵的新概念，然后用拟阵语言将Goddyn和Heuevl所得的图论上的新结果平移成了拟阵的新结果，最后用拟阵的方法对它们给出了新的证明。     

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

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

一类线图的泛圈性

本文的主要结果是:设G是n≥3阶简单图,ε≥2,且不含3度的边,若GC_4,C_5及C_4∪K_1且对任意无公共顶点的两边e_1和e_2,有d(e_1) d(e_2)≥2n-3,则G的线圈L(G)是泛圈图。     

由圈长分布确定的偶图

阶为n的图G的圈长分布是序列(C1，C2，…，Cn)，其中ci是图G中长为i的圈数．本文得到如下结果：设A∈_E(Kn,r)，|A|≤1，且n≤r≤min{n 6，2n-3)，则G=Kn,r，r-A是由它的圈长分布确定的．     

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

一个边割被称为圈边割,如果该边割能分离图的两个不同圈.如果一个图有圈边割,称该图为圈边可分离的.一个圈边可分离图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]中研究了两种不同的双轨道图的圈边最优性.本文我们将研究具有两个同阶轨道的双轨道图的圈边连通度.     

不含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.     

完全对称有向图Dn的偶长圈分解

证明了将奇数阶完全对称有向图Dn分拆为偶长有向圈的必要条件也是充分的。     

Bondy的泛圈图定理的改进

记G=(V,E)是简单图,1971年Bondy得到O re条件下的泛圈图的著名结果:若2连通n阶图G的不相邻的任两点x、y均有d(x) d(y)≥n,则G是泛圈图或G=Kn/2,n/2.这里进一步研究条件d(x) d(y)≥n-1,得到:若2连通n阶图G的不相邻的任两点x、y均有d(x) d(y)≥n-1,则G是泛圈图或G∈{K(Cn 1)/2∨G(n-1)/2,Kn/2,n/2}.本文作者得知最近国际著名权威专家Ho lton等人也得到完全相同的结果,但本证明更简捷.     

曲面上图的短圈结构与Mohar和Thomassen的一个问题的解决

研究了(赋权)图的圈基结构并且对包含在最小圈基中的短圈提供了大量信息. 建立了一个基变换的Hall型定理, 利用此定理, 给出了判断一个圈基是最小圈基的充分必要条件, 而且，证明了一个(赋权)图的最小圈基结构是唯一的. 这一性质对于最大圈基也成立 (尽管在最小圈基方面已有很多工作, 而在最大圈基方面的工作几乎没有). 利用这些方法， 发现了(赋权)图中具有特定性质的短圈的一些新结果. 作为应用， 决定了一个嵌入图的短圈的结构, 并找到一个多项式算法能够判断一个嵌入图中是否存在双侧圈, 如果这样的圈存在, 就可以找到一个最短的双侧圈. 这回答了B. Mohar和C. Thomassen提出的一个未解决问题, 并对他们提出的另一个未解决问题给出了部分解答.     

完全3-一致超图的圈分解

The problem of decomposing a complete 3-uniform hypergraph into Hamilton cycles was introduced by Bailey and Stevens using a generalization of Hamiltonian chain to uniform hypergraphs by Katona and Kierstead. Decomposing the complete 3-uniform hypergraphs K_n~(3) into k-cycles(3 ≤ k n) was then considered by Meszka and Rosa. This study investigates this problem using a difference pattern of combinatorics and shows that K_(n·5m)~(3) can be decomposed into 5-cycles for n ∈{5, 7, 10, 11, 16, 17, 20, 22, 26} using computer programming.     

长圈的邻域交条件的推广

证明了若G为一个k(k≥2)连通简单图,独立数为α,V(G)=n≥3,X1,X2,…,Xk是顶点集合V的子集,X=X1∪X2∪…∪Xk,且对于Xi(i=1,2,…,k)中任意两个不相邻点u,v,|N(u)∩N(v)|≥α,则X在G中可圈,并给出几个相关推论.     

偶图Kn,r-A(|A|≤3)的圈长分布唯一性

阶为n的图G的圈长分布是序列(c_1,c_2,…,c_n),其中c_i是图G中长为i的圈数。设A(?)E(K_(n,r))。本文得到如下结果：若|A|=2,且n≤r≤min{n 6,2n-5),则G=K_(n,r)-A是由它的圈长分布确定的；若|A|=3,且n≤r≤min{n 6,2n-7),则G=K_(n,r)-A也是由它的圈长分布确定的。     

关于简单MCD图

设G是阶为n的简单图，若G中没有两个等长圈且具有最大可能的边数，则称G为简单MCD图。本文通过引进路分解概念给出了两个关于图中圈数的结果并应用它们证明了下述定理：若G是简单MCD图，则G不是2连通可平面图且对所有整数n，除七个例外，G不是阶为n的含有同胚于K4的2连通图。     

完全有向图的奇长圈覆盖

设DK_v表示完全有向对称图,C（v,m）表示覆盖DK_v的m长有向圈的最小圈数（称为覆盖数）.对任意正整数m和v,当m≤v≤m+6时,覆盖数C（v,m） 被确定.     

关于含k圈标号图的计数问题

含k个圈的标号图的计数问题是一个未解决问题.迄今仅对于k=1,2被解决,可是,所得出的计数式均较复杂.本文改进了已得到的一系列公式,并且解决了K=3的上述计数问题.