Study On Some Kinds Of Parameters Of Graphs

With the rapid development of social productivity and science and technol-ogy, the practical application of graph theory has penetrated into all fields, and the parameters in the graph theory can be used as a measure in the study of these areas. This thesis is focus on three parameters:Hamiltonian, spanning connected index and isoperimetric arc connectivity.In chapter1, we introduce the backgrounds of our study and some basic definitions, notations, terminology, and the research status of the above three parameters to a certain extent, at last we outline the main results of this thesis.In chapter2, we study the sufficient condition of a3-connected claw-free graph to be Hamiltonian. For an integer s1, s2,s3>0, let Ns1,s2,s3denote the graph obtained by identifying each vertex of a K3with an end vertex of three disjoint paths Ps1+1, Ps2+1> Ps3+1of length s1,s2, and s3, respectively. We determine a family F of graphs and prove the following,(i) If s1+s2+1≤10, every3-connected{K1,3,Ns1,s2,1}-free graph Γ is hamil-tonian if and only if the closure of Γ is the line graph L(G) for some graph G(?)F.(ii) If s1+s2+s3≤9, every3-connected{K1,3,Ns1,s2,s3}-free graph is hamil-tonian.(iii) If s1+s2≤9, every3-connected{-K1,3,Ns1,s2,0}-free graph Γ is hamilto-nian if and only the closure of Γ is the line graph L(G) for some graph G(?)F.(iv) If s1+s2≤8, every3-connected{K1,Ns1,s2,0}-free graph is hamiltonian.In chapter3, we study spanning3-connected index of graphs. Let Lm(G) be the m-th iterated line graph of G. For an integer s>0and for u,v∈V(G) with u≠v, an (s; u, w)-path-system of G is a subgraph H of G consisting of s internally disjoint (u, v)-paths, and such an H is called a spanning (s; u, v)-path system if V(H)=V(G). The spanning connectivity κ*(G) of graph G is the largest integer s such that for any integer k with1≤k≤s and for any u, v∈V(G) with u≠v, G has a spanning (k; u, v)-path-system. Let G be a simple connected graph that is not a path, a cycle or a K1,3. The spanning k-connected index of G, written sk(G), is the smallest nonnegative integer m such that Lm(G) is spanning k-connected. Let l(G)=max{m:G has a divalent path of length m that is not both of length2and in a K3}, where a divalent path in G is a path whose interval vertices have degree two in G. In this chapter, we prove that s3(G)≤l(G)+6. The key proof to this result is that every connected3-triangular graph is2-collapsible.In chapter4, we study the isoperimetric arc connectivity of digraphs. A digraph D with γk+(D)=βk+(D) is γk+-optimal, where γk+(D)=min{|(U,U)|: U C V,|U|≥k,|U|≥k}, which is called isoperimetric arc connectivity, βk+(D)=min{|(U,U)|:U (?) V,|U|=k,|U|≥k}. We prove that a strongly connected regular digraph D with connectivity κ(D)>3, then L(D) is γ2+-optimal.