论文部分内容阅读
Hamilton问题一直以来都是图论界所关注的焦点，但是迄今为止也没能完全解决．Cayley图是定义在群上的一类图，在交换群上已经得出了都是Hamilton图的结论．模n的剩余类加群是简单的交换群，And(k)是定义在模3k-1的整数加群上的Cayley图，因此And(k)是Hamilton图．
在解决Hamilton问题的过程中，与之有关的概念被不断提出，1997年，Lenhard定义了k-可序Hamilton图．而具有Hamilton性的Cayley图中，k-可序性尚未有明确结论．由于And(3)不是4-可序的，因此本文研究的是当k≥4时，And(k)的4-可序性．对于所有4元集，显然穷举方法是行不通的，本文采用了图与组合中分类讨论的方法，找到了行之有效的分类，证明And(k)的4-可序性．
本文的第二部分讨论了小度数射影平面上的一些完全弧，1955年Segre在Fano定义的射影空间基础上给出了射影平面上k-arcs的概念，并提出了问题：对于给定的r，q，PG(r，q)中存在最大k-arcs的k值是多少?问题至今未能完全解决．本文通过研究射影平面的关联图，得到当r=2时的小度数射影平面上的完全k-arcs，并在关联图上定义了(q+1)阶矩阵，提供了找到k-arcs的新方法．