| All graphs considered in this paper are finite, simple and undirected. Let G=( V(G), E(G) ) be a graph, where V(G) and E(G) denote the vertex set and edge set of G respectively. For v ∈ V(G), we denote by d(v) the number of vertices adjacent to vertex v, by N(v) the set of vertices adjacent to vertex v. S(G) denotes the minimum degree of all vertices of G. G denotes the complement graph of graph G. G1∪ G2 denotes the union graph of G1 and G2 and G1 V G2 denotes the joint graph of G1 and G2. For any a 6∈(G), A $ V(G) and any subgraph H of G, (A) denotes the subgraph of G induced by A.G-H = ( V(G)-V(H] },G-{v} = ( V(G)-{v} ),NH(a) ={ v∈V(H): av ∈ E(G) },N(a) = NG(a),|H| = |V(H)}.If P=v1v2...vp is a (u,v)-path in G (u = v1, v = vp], then the length of path P refers to the number of the edges in P. we let viPvj, for 1 < i < j < p, be the subpath vivi+1...vj of P, and the subpath of P. For any i, we put vi+m= vi+m, vi-m = Vi-m For convenience, we often regard vi- and vi+ as vi-1 and vi+1. For any set A ∈ V(P), we define A+ = {a+ : a 2 A}, and A- = (a- : a ∈ A}. If there is no (u,v)-path P* which satisfies V(P*) ∈ V(P) and |V(P*)| < |V(P)|, then the (u,v)-path P is minimal. In G, for any two distinct vertices u , v and a nonhamilton (u,v)-path P, if there is a (u.v)-path P' which satisfies V(P] C V(P') and |P'| = |P| + 1, then the graph G is called path extendable graph. For convenience, we call the (u,v)-path P' an extendable path of P.Suppose p be an integer which is at least three, we define the subgraph in G which is isomorphic to K1,p a p-claw of G. [X0; x1, ... xp] denotes a p-claw whose vertex set is x0,x1,...xp, and the first vertex x0 denotes the vertex whose degree is p in the p - claw. For all p-claws in G, if the subgraph induced by vertices whose degree in p-claw is one has at least ( p-2 ) edges, then we call G a K1,p-confined graph. Especially, if p is three, then K1,p-confined graph is claw-free graph. If p is four, then K1,p-confined graph is the graph we discuss in this paper. If for all v V(G), (N(v)) is k-connected, then we call G a locally k-connected graph.Hamilton problem is one of fundamental problems in graph theory, the following aspects are mainly focused on: cycle problem and path problem. In detail, they are mainly problems of Hamilton cycle, cycle extensibility, longest cycle and Hamilton path, Hamilton-connectivity, panconnectivity, path extensibility, longest path etc. As to Hamilton cycle problem, we have got many results. In 1952, Dirac gave the minimum degree condition on the existence of the longest cycle ( Dirac type condition ). In 1960, Ore gave the sum of degree condition ( Ore type condition ). In some cases, Ore condition can get the better result. In 1984, Fan g.H. gave Fan type condition in [9]. But usually it is difficult to work out the Hamilton problem of any graph, then we turn to explore the graphs containing forbidden subgraph, for example, claw-free graph, almost claw-free graph, quasi claw-free graph. While in this paper, a new class of graphs is defined which contains claw-free graphs. It is called K1,p-confined graph. We mainly discuss the related path problems of K1,4-confined graph.In the first chapter, we give a brief introduction on the basic concepts and terminology which are involved in this paper.In the second chapter, we first introduce some conclusions of almost claw-free graph and quasi claw-free graph, then we prove a simple but very important result of K1,p-confined graph, that is:Theorem 2.5 K1,p-confined graph is bound to K1,p+1-confined graph .In the third chapter, there are three sections. In the first section of chapter three,we introduce some conclusions of path problems of claw-free graph. In the second sectionof chapter three, we prove theorem 3.7 and a good example is given to show that thebound of locally connectivity is sharp. In the third section of chapter three, we obtain aconjecture which is deduced by theorem 3.6[4] and theorem 3.7, and also a good...
|
PDF Full Text Request