Some Results About Path Spectrum

A path P of a graph G is maximal if P is not a proper subpath of any other path of the graph G.And the path spectrum of G,denote by ps(G) ,is the set of length of all maximal paths in the graph. A set S of positive integers is called a path spectrum if there is a connected graph G such that ps(G) = S.For a graph G of order n,if there exists an integer s(G) such that ps(G) — {s(G),s{G) + 1,... ,n — l},then G is called a string path spectrum graph (SPS-graph for short).This paper is composed of three parts:in the first part we introduce some concepts and results about path spectrum; in the second part we show that every 2-connected,{K_1,3, P₅}-free graph is either a SPS-graph or a special kind of graph;in the third part we study the path spectrum of a tree,characterize the path spectrum of order two or the path spectrum of order three.The main results are as follows:Theorem 2.2: Let G be a 2-connected,{K_1,3, P₅}-free graph,Then G is either a SPS-graph or satisfies the following conditions:(i)V(G) = A∪X∪Bisa partition of V(G) ;(ii)Both G[A] and G[B] are complete;(iii)Every vertex of X is adjacent to all vertices of B;(iv)Either G[X] is complete or \X\ = 2 and {N_a(x)}_x∈x forms a partitionof A;(v) Every vertex of A has at most one neighbor in X.Theorem I: Let a, b be two positive integers,Then S = {a, b} is a path spectrum of a tree if and only if one of the following two conditions holds :(i)a, b are evens;(ii)only one of o, b is even and < a < 2b.Theorem // : Let S be a set composed of three positive integers, then S is a path spectrum of a tree if and only if one of the following three conditions holds .(i)The elements in S are evens ;(ii)5 = {a, b, c},where c is even,a, b are odds, a + b > c and \a — b\ < c;(iii)5 = {a, b, c},where a, b are evens,c is odd and c > max{a, b}.