论文部分内容阅读
本文共分三节，第一节简单介绍了路谱的概念和相关的研究成果。第二节证明了一类含有禁用子图的哈密顿图是SPS-图或者是一类特殊的图。第三节对树的路谱进行了研究，给出了一棵树有阶为2的路谱和阶为3的路谱的充要条件。本文主要结果如下：
定理2.2 设G为2-连通图，如果G中任何导出子图都不与K1，3或P5同构，则G是一个SPS-图或者G满足下面的条件：
(i)V(G)=A ∪ X ∪ B是V(G)的一个划分；
(ii)G[A]，G[B]是完全图；
(iii)X中每个点都与B中所有点相邻；
(iv)G[X]是完全图或者｜X｜=2且{NA(x)}x∈X形成A的一个划分；
(v)A中的每个点在X中至多有一个邻点.
定理Ⅰ设a，b是两个正整数，则S={a，b}是树的路谱当且仅当下述条件之一成立：
(i)a，b均为偶数；
(ii)a，b中恰有一个为偶数且b/2＜a＜2b.
定理Ⅱ设S是三个正整数所构成的集合，则S是树的路谱当且仅当下述条件之一成立：
(i)S中的元素全为偶数；
(ii)S={a，b，c}，其中c为偶数，a，b为奇数，a+b＞c且｜a-b｜＜c；
(iii)S={a，b，c}，其中a，b为偶数，c为奇数，且c＞1/2max{a，b}.