阶为偶数交换群上6度Cayley图的Hamilton圈分解

利用"Hamilton圈的侧枝循环理论和方法"证明了阶为偶数阿贝尔群上的任意一个6度Cayley图都能被分解为3个Hamilton圈的并,这回答了Alspach关于2K度Cayley图的Hamilton圈分解的推测的一部分问题.

关于完全二分3—超图的Hamilton圈分解

超图是离散数学中最一般的结构 ,无圈超图已被证明在数据库设计中非常有用 ,笔者在文〔4〕所建立的超图的公理系统基础上 ,用巧妙而构造性方法分别给出了完全二分 3—超图H3 ( p ,p) (p是素数 )的Hamilton圈分解和完全二分 3—超图H3 (p ,p) (2 |p)的Hamilton圈分解 ,并提出猜想 :当 p为素数且p≡ 1(mod4)时 ,H4 ( p ,p)

完全三部图的5圈分解问题

给出了一些可以５圈分解的具体的完全三部图；利用一个引理构造了若干可以５圈分解的完全三部图系列；给出一个完全三部图可以５圈分解的必要条件，并猜测它也是充分条件．

m<50时完全二部图K_(n,n)的循环m-圈分解

设Kn,n表示每部分具有n个顶点的完全二部图,本文利用差集的方法来构造Kn,n的循环m-圈分解,讨论了30<m<50时的所有整数的循环m-圈分解的存在性,并最终给出了当m<50时,Kn,n存在循环m-圈分解的充分必要条件.

完全3-匀齐超图K_(37)^((3))的5-圈分解

设H=(V,E)是一个k-匀齐超图,V上的一个l-元子集的循环序列C=(v_(0),v_(1),...,v_(l-1))被称为H上的一个l-圈,如果C中任意连续的k个顶点恰好构成H的一条边,这里3≤k≤l-1.如果超图H=(V,E)的边集E可以被划分成若干个l-圈,则称H有一个l-圈分解;特别地,当l=|V|时,则H有一个Hamilton圈分解.国内外许多学者研究了超图的l-圈分解.k_(n)^((3))的5-圈分解的彻底解决仍是一个公开问题.这里,用完全3-匀齐超图的边划分和圈序列的方法证明了完全3-匀齐超图K_(37)^((3))有一个5-圈分解.

强连通竞赛图的圈分解(英文)

设T为n阶强连通竞赛图.本文通过详细刻画不能进行圈分解的强连通竞赛 图的特征,证明了满足maX{δ+,δ-}>5k-5和k>2的强连通竞赛图T,能够分解为k 个圈.

4度Cayley图的Hamilton圈分解方法的进一步研究

J.C Bermond在1989年已证"Abel群上4度Cayley图可分解为两个边互不相交的Hamilton圈的并",其分解方法首先要对简化图进行分解后才能实现,产生一定局限性,不但数目少,而且方法也比较繁杂.4度Cayley图的Hamilton圈分解的新方法与理论证明是利用Hamilton圈上"单向通道"的"离合"理论和方法,给出了Abel群上4度Cayley图的Hamilton圈分解方案和理论证明.对新方法分解方案多且简明快捷的特点作进一步研究,并对两种方法进行比较,得到"H操作法"分解方案,超过Bermond分解方案的6倍(含Bermond分解方案).

2~np^m阶群上Cayley图的Hamilton圈分解

Alspach于1985年对Abel群上Cayley图的Hamilton圈分解提出了著名的A猜想,Bermond(1989)证明了4度Abel群上Cayley图对A猜想成立。为了将其研究领域拓广到非Abel群上,采取了有限群上Cayley图的Hamilton圈分解的新方法—"Hamilton方"操作法,Abel群上Cayley图对A猜想成立,进一步证明了阶为23p群所含12个群中有10个群的Cayley图(对给定的生成集合)对A猜想成立;另两个群的Cayley图也可分解为边互不相交的Hamilton圈和一个2—因子的并。结果表明:"Hamilton方"操作法,具有简明、快捷的优点,而将A猜想拓广到非Abel群上,将为设计互连网算法提供更多的直观路径。

完全图圈分解的一种新方法

本文给出完全图圈分解的一种新方法,设K_n(n≥3)是一个n阶完全图,我们得到下列结果: (1) 若n为奇数,G是n阶群,并且{o(x)|x∈G,o(x)≥3}={a_1,…,a_t},则K_n=m_1C_(a_1)+…m_tC_(a_t)。 (2) 若n为偶数,G是n阶群,T={x∈G,o(x)=2}={x_0,x_1,y_1,…,x_s,y_s},o(x_iy_i)=b_i,i=1,…,s及{o(x)|x∈G,o(x)≥3}={a_1,…,a_t},则K_n-F=n_1C_(2b_1)+…+n_sC_(2b_s)+m_1C_(a_1)+…+m_tC_(a_t)。

一类具有强偶圈分解的4-正则线图

如果一个图的边集能划分成偶数长度圈的集合,则称该图有一个偶圈分解.如果一个图的任何一个具有偶数条边的细分,都有一个偶圈分解,则称该图是强偶圈分解的.在文献[European Journal of Combinatorics,94(2021),103315]中已证明:对于2-连通立方图G,如果它存在一个圈C使得G-V(C)是一个线性森林(即这个森林仅仅由路组成),则L(G)是强偶圈分解的.本文推广上述结论,证明了如下定理:对于2-连通立方图G,如果它存在一个圈C使得G-V(C)是一个森林,则L(G)是强偶圈分解的.

完全3-一致超图K_(32)^(3)的5-圈分解

Bailey-Stevens和Meszka-Rosa研究了完全k-一致超图的Hamiltonian圈分解问题,并解决了对n≤32的完全3-一致超图K^(3)_n的Hamiltonian圈分解.同时,详细介绍非Hamiltonian圈分解问题.到目前为止,除了当n≤17,并且n=4m+1,m是正整数时完全3-一致超图K(3)n的5-圈分解以外.其他的5-圈分解的存在性问题仍然是公开的.本文中,在使用边划分方法的基础上、设计一个算法并得到了K^(3)_(32)的一个5-圈分解.

最大圈分解问题的研究进展

最大圈分解问题最早由Erds和Pósa提出,随后研究人员在图论领域和理论计算机科学领域中对其进行了广泛的探索。最近研究发现,该问题在计算生物学上特别是在构建进化树与分析基因组的研究方面有重要的应用。主要介绍了该问题的研究现状。首先讨论了该问题在图论方面的研究进展;随后对该问题的近似算法、参数算法、参数复杂性与不可近似性进行了分析和讨论;最后给出了该问题的进一步研究方向。

完全3-一致超图K_(50)^(3)的7-圈分解

在Katona-Kierstead和王建方分别独立定义的Hamiltonian链和圈的定义的基础上.一些国内外学者研究了完全3-一致超图K_n^(3)的Hamiltonian与非Hamiltonian圈分解问题.特别的,Bailey Stevens使用团的方法找到了K(3)7,K(3)8的Hamiltonian圈分解.Meszka-Rosa证明了对于n≤32所有可能值的K_n^(3)可以Hamiltonian圈分解,并介绍了对任意的n≤17和所有n=4m+1,当m是正整数时,K_n^(3)可以5圈分解.一般来说,K_n^(3)的l(l≥5)圈分解问题仍然是公开的.目前已得到n∈{7,8,14,16,22,23,29,37,43,44}时完全3-一致超图K_n^(3)可以7-圈分解,并且若K_n^(3)可以7-圈分解,则K(3)7n也可以7-圈分解.文章使用完全3-一致超图K_n^(3)的边划分和圈序列方法得到了K_(50)^(3)的7-圈分解.

超图的无圈分解问题

引入了超图的无圈分解的荫度的概念,研究了n阶r-完全超图Knr的无圈分解问题,给出了n阶r-完全超图Krn的荫度的一个下界T(Knr)≥(n!/r!(n-r+1)!).并提出猜想这里[x]表示x的整数部分.

m≡0(mod8)时完全二部图K_(n,n)的循环m-圈分解

研究完全二部图Kn,n的循环m-圈分解的存在性问题.利用差的方法构造完全二部图Kn,n的循环m-圈分解的初始圈.对于m≡0(mod8)且m≥8这种情况,证明当n≡0,m/2,m,3m/2(mod2m)时完全二部图Kn,n存在循环m-圈分解;对于m≡0(mod8),m≥8且m/4无平方因子这种情况,证明了完全二部图Kn,n存在循环m-圈分解的充分必要条件是n≡0,m/2(modm).

C_m×C_n×C_r的Hamilton圈分解——A·Kotzig猜想的一个新的证明

A·Kotzig研究J·C_m×C_n有两条Hamilton圈的问题。提出了如下猜想:C_m×C_n×C_r可分解成三条边不重Hamilton圈。本文作者曾独立地证明了A·Kotzig的关于C_mC_n的Hamilton圈分解的猜想。本文在Marcha·F·Forcgger之后独立地构造性地证明了C_m×C_n和C_m×C_n×C_r的Hamilton圈分解定理。

2-连通奇度为2的立方图的线图的偶圈分解

一个图的偶圈分解就是划分图的边集成一个偶圈的集合.Klas Markstr?m猜想:2-连通立方图的线图有偶圈分解,并证明了猜想对于2-连通奇度为2且含有无弦2-因子的立方图成立.文中通过讨论有弦情况猜想也成立,从而完成证明:2-连通奇度为2的立方图的线图有偶圈分解.

λ重完全二部3-一致超图的紧六圈分解

研究了一类特殊类型的超图分解问题,即λ重完全二部3-一致超图λK_(n,n)^((3))的紧6圈分解,记作S_(λ)(3,C_(6)^((3)),n,n).首先,通过计算得到其分解存在的必要条件为λn~2(n-1)≡0(mod 6),且n≥3.故对于λ=1的情况,只需考虑n≡0,3,4,7 (mod 6);对于λ=3的情况,只需考虑n≡5,8(mod 6).然后,建立递归构造,找到递归构造中所需要的小阶数设计,针对阶数比较大的超图,可以由一些阶数较小的设计递归生成.最后得到S_(λ)(3,C_(6)^((3)),n,n)存在的必要条件也是充分的,即存在S_(λ)(3,C_(6)^((3)),n,n)当且仅当λn~2(n-1)≡0 (mod 6),且n≥3.

非Abel群度Cayley图的Hamilton圈的分解

利用"本源法"和同构理论证得两类非Abel群上2K+1度Cayley图对Alspach猜想成立.