The H-force Numbers Of The K-ary N-cubes And OTG Graphs

In Graph theory, Hamiltonian problems have attracted a large number of researchers for a long time. A cycle of G is called the Hamiltonian cycle, if it contains all vertices of G. The graph G is said to be a Hamiltonian graph if it has a Hamiltonian cycle. Let G be a Hamiltonian graph. For a nonempty vertex set X (?) V(G), if every cycle containing all vertices of X is a Hamiltonian cycle, then X is called an H-rorce set of G. The smallest cardinality of an H-force set of G is called the H-force number of G. The H-force set and H-force number were introduced by Fabrici et al. in 2009. Since these concepts play an important role on the Hamiltonian problems, these concepts have aroused wide concern among researchers.k-ary n-cubes are special network topology models and denoted by Qkn(k≥ 1, n≥ 1). The graph has kn vertices. Each vertex can be denoted by u = un-1un-2…uo while ui ∈ {0,1,...k - 1},0< i< n - 1. Vertices u=un-1nn-2...u0 and u= vn-1vn-2...vo are adjacent if and only if there exists an integer j,0≤j≤ n-1, such that uj = uj±1 (mod k) and ui= ui for each i ∈{0,1,..., j -1,j+1,...,n-1}. If d(u)+d(v)> n for every pair of nonadjacent vertices u and v of G, we say that G satisfies the condition of Ore’s theorem. For convenience, we call a graph satisfying the condition of Ore’s theorem an OTG. Ore proved that any OTG is Hamiltonian. In this paper, we will give the H-force sets and H-force numbers of the network graphs k-ary n-cubes Qkn and the OTG graphs. The conclusion is obtained by analysis and classification of the structure of graphs.The thesis consists of four sections.Chapter 1 is the preface. The research background and the relevant conclusions are introduced.Chapter 2 is the terminology and notations. Several useful concepts on graphs are given.In Chapter 3, we obtain the H-force number of the network graphs k-ary n-cubes Qkn by study the H-force number of Cm × Cn.We obtain the following three main results.(ⅰ)Let G=Cm×Cn(m>2,n>2).Then(ⅱ)Let G=Qkn(n≥2,k>2).Then(iii)Let G=Pn×Pn(n≥4,n is even).Then h(G)=n2/2-2.In Chapter 4,we study the H-force number and the minimum H-force set of the OTG graphs. By studying the weak closure of these graphs,we show that the H-force number of these graphs is possibly n,or n-2,orn/2 and give a classification of these graphs.The following is the main conclusion.Let G be an OTG with n≥5 vertices and X be the minimum H-force set of G.Let Cw(G)be the weak closure of G and S be the largest independent set of Cw(G).Then(1)the H-force number h(G)=n-2,n/2,or n,and(2) where x,y ∈V(G)with dCw(G)(x)=n-1 and dCw(G)(y)=n-1.