论文摘要
设P是图G中的一条路,如果P不是G中任何路的真子路,则称P为G中的极大路。并称G中所有极大路的长度所成之集为G的路谱,记为ps（G）。设S为一个正整数集合,如果存在一个连通图G使得ps（G）=S,则称S为一个路谱。对于一个阶为n的图G,如果存在一个正整数s（G）使得ps（G）={s（G）,s（G）+1,…,n-1},则称G为一个SPS-图。 本文共分三节,第一节简单介绍了路谱的概念和相关的研究成果。第二节证明了一类含有禁用子图的哈密顿图是SPS-图或者是一类特殊的图。第三节对树的路谱进行了研究,给出了一棵树有阶为2的路谱和阶为3的路谱的充要条件。本文主要结果如下: 定理2.2 设G为2-连通图,如果G中任何导出子图都不与K1,3或P5同构,则G是一个SPS-图或者G满足下面的条件: （ⅰ） V（G）=A∪X∪B是V（G）的一个划分; （ⅱ） G[A],G[B]是完全图; （ⅲ） X中每个点都与B中所有点相邻; （ⅳ） G[X]是完全图或者|X|=2且{NA（x）}x∈X形成A的一个划分; （ⅴ） A中的每个点在X中至多有一个邻点。 定理Ⅰ 设a,b是两个正整数,则S={a,b}是树的路谱当且仅当下述条件之一成立: （ⅰ） a,b均为偶数; （ⅱ） a,b中恰有一个为偶数且b/2<a<2b。 定理Ⅱ 设S是三个正整数所构成的集合,则S是树的路谱当且仅当下述条件之一成立: