线图的s-哈密尔顿性及其相关问题研究

The hamiltonian problems are extended to s-hamiltonity and s-hamilton connectedness of graphs. Many graph theory researchers pay attention to survey results and open problems in hamiltonian graph theory centered around two conjectures of the 1980s that are still open: Every 4-connected line (claw-free) graph is hamiltonian. These conjectures have lead to a wealth of interesting concepts，techniques, results and equivalent conjectures. In this project, using Catlin's collapsible graph, reduction method and the related results, we shall study on s-hamiltonian line graphs and related problems. Our research includes the following three problems. (1) We will concentrate our efforts on the s-hamiltonity and s-hamilton connectedness of the line graphs of graph without only one forbidden subgraph. (2) We shall deformine the best possible connectivity conditions which guarantee the s-hamilton connectedness of line graphs. (3) We shall investigate the sufficient conditions for s-hamiltonity and s-hamilton connectedness of graphs without more than one forbidden subgraphs.

图的s-哈密尔顿性及s-哈密尔顿连通性是对哈密尔顿性及哈密尔顿连通性的推广。20世纪80年代，Thomassen以及Matthews和Summer提出了两个重要猜想：每个4-连通的线图（无爪图）是哈密尔顿的。这些猜想一经提出就得到众多图论学者的重视及广泛研究，并取得了大量的研究成果。本项目主要是通过Catlin提出的可折叠图、收缩方法及其相关结果，对线图的s-哈密尔顿性及s-哈密尔顿连通性问题展开研究，主要包括以下三个方面的研究内容：（1）根据已有的线图的哈密尔顿性及哈密尔顿连通性条件，研究不含某一个特定禁止子图的图的线图是s-哈密尔顿及s-哈密尔顿连通的充要条件；（2）研究图G的线图是s-哈密尔顿连通的最好可能的连通度条件；（3）考虑不含有多个禁止子图的图的s-哈密尔顿及s-哈密尔顿连通的充分条件。

图的s-哈密尔顿性、s-哈密尔顿连通性及图的泛圈性是对图的哈密尔顿性质的推广。20世纪80年代，Thomassen以及Matthews和Summer提出了两个重要猜想：每个4-连通的线图（无爪图）是哈密尔顿的。至此众多图论学者以这些猜想为主要研究核心，展开广泛研究，并取得了大量的综述结果。在对这些猜想的研究中，学者们得到了许多有趣的概念、方法技巧、结果和一些等价猜想，并产生了大量参考文献。本项目主要是通过Catlin提出的可折叠图、收缩方法及其相关结果，对线图的s-哈密尔顿性、s-哈密尔顿连通性及泛圈性问题展开研究，主要包括以下方面的研究内容：(1) 根据已有的线图的哈密尔顿性结论，研究直径之多是2的图的线图的泛圈性及1-哈密尔顿性；(2) 考虑了不含有一类子图的线图的s-哈密尔顿及s-哈密尔顿连图性的充分必要的连通度条件；(3) 将一般连通图的Chvátal–Erdos 哈密尔顿性条件推广到了线图的情况。(4) 依据已知的线图的哈密尔顿性结果，考虑了(s+4)-连通的线图的s-哈密尔顿连通性及(s+4)-连通的无爪图的线图的s-哈密尔顿连通性问题。