正圆有向图中的弧不相交的Hamilton路和圈

2012年,Bang-Jensen和Huang(J.Combin.Theory Ser.B.2012,102:701-714)证明了2-弧强的局部半完全有向图可以分解为两个弧不相交的强连通生成子图当且仅当D不是偶圈的二次幂,并提出了任意3-强的局部竞赛图中包含两个弧不相交的Hamilton圈的猜想.主要研究正圆有向图中的弧不相交的Hamilton路和Hamilton圈,并证明了任意3-弧强的正圆有向图中包含两个弧不相交的Hamilton圈和任意4-弧强的正圆有向图中包含一个Hamilton圈和两个Hamilton路,使得它们两两弧不相交.由于任意圆有向图一定是正圆有向图,所得结论可以推广到圆有向图中.又由于圆有向图是局部竞赛图的子图类,因此所得结论说明对局部竞赛图的子图类――圆有向图,Bang-Jensen和Huang的猜想成立.

关于随机相交图中Hamilton圈的门限函数的注记

随机相交图G(n,m,p)的定义如下:记V为一n顶点集.M为一m个元素的集合.对每个顶点v∈V,赋予一随机子集Fv■M,其中从M中独立以概率p选取每个元素构成Fv,顶点u和v之间有边相连当且仅当Fu∩Fv≠Φ.当m=na,a≠1时.C.Efthymiou和P.G.Spirakis得到了G(n,m,p)中Hamilton圈的门限函数.对于a=1情形,本文利用二阶矩方法(Chebyshev不等式)得到了类似结果.

K_p和K_(p+1)的具有最多Hamilton圈的定向图

在文献[3]中,Hoffman等人证明了完全图Kn中最多边不交的Hamilton圈个数为[n-1/2].这说明Kn存在一个定向Tn,使得Tn具有[n-1/2]个弧不相交的Hamilton圈.给出了当n=p和p+1(其中p是一个奇素数)时,一种构造Tn的方法,使用这种方法,可以直接写出Tn的所有弧不相交的Hamilton圈.

一类HAMILTON图中圈的数目

Yap H P和Teo S K提出问题:下述等式是否成立?m(K)=(1/2)(k+1)×(k+2),M(k)=2~k+k。此外,对于任意介于m(k)与M(k)之间的整数i,是否存在G∈H(n,k)使得f(G,k)=i?本文解决了上述问题。

有向圈的矩阵算法及有关性质

用矩阵方法讨论了有向图的连通性 ,阐述了计算有向圈的矩阵方法及有向图为Hamilton图的充要条件 。

有向圈的行列式算法及HAMILTON图条件

本文引入有向路乘法、弧行列式等概念 ,讨论了弧行列式的性质 ,阐述了二种计算有向圈的行列式方法及有向图 D为 Hamilton图的充要条件 。