点传递图中若干问题的研究

项目名称： 点传递图中若干问题的研究

项目编号： No.11201403

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 张翠

作者单位： 烟台大学

项目金额： 22万元

中文摘要： Cayley图是点传递图，但存在一些点传递图不是Cayley图，叫做non-Cayley点传递图。1983年，Dragan Maru?i? [Ars Combinatoria 16B (1983), 297-302]提出问题：对于哪些正整数n存在一个n阶的non-Cayley点传递图？经过且仅一次经过一个连通图的每一个顶点的路(圈)叫做Hamilton路（圈）。1969年，Lová [Proc. Calgary Internat. Conf., Calgary, Alberta, 1969] 提出这样一个问题：是否每一个有限的连通点传递图都含有Hamilton路？这两个问题提出近几十年来，更多的研究工作者投入到点传递图的研究工作中来，取得了相当丰富的结果，但仍未完全解决。本课题将会就特殊阶，特殊度数，以及其他一些限制条件的点传递图对这两个问题做进一步研究。

中文关键词： 图的不同传递性；凯莱图；哈密尔顿图；有限群；可解群

英文摘要： Every Cayley graph is vertex-transitive. However, there are vertex-transitive graphs which are not Cayley graphs called non-Cayley vertex-transitive graphs. In 1983, Dragan Maru?i? [Ars Combinatoria 16B (1983), 297-302.] asked for which positive integers n does there exist a non-Cayley vertex-transitive graph on n vertices? A path (cycle) containing every vertex in a graph is called a Hamilton path (Hamilton cycle). In 1969, Lová [Proc. Calgary Internat. Conf., Calgary, Alberta, 1969] asked whether every finite connected vertex-transitive graph has a Hamilton path? Motivated by these two questions much more researchers join the research on vertex-transitive graphs in the following decades, this resulted in a great deal of the work on these two problems, but both problems remain open. The aim of the proposed project is to obtain future results on these topics, in particular, to answer these questions for special infinite families of vertex-transitive graphs regarding special orders, special valencies and other restrictions of vertex-transitive graphs.

英文关键词： Different transitivity of graphs；Cayley graph；Hamilton graph；finite group；solvable group