Degree Bounded Spanning Tree Of Cartesian And Direct Product

For a fixed positive integer k, a spanning tree T of a connected graph G is saidto be a k-tree of G ifΔ(T)≤k. Given a connected graph G, finding the minimumpossible integer k such that G has a k-tree be called the degree bounded span-ning tree(which is also known as [1,k]-factor) problem. This problem has beenconsidered by many people as one of problems about factor(spanning subgraph)of a graph. In the present paper, we consider the degree bounded spanning treeproblem for the Cartesian product graph and direct product graph.In chapter one, we first introduce the problem of factor. Moreover, we intro-duce the background of our subject and main results. The problem of factor isone of classical problems in the field of graph. In 1891 Petersen [16] proved thata graph is 2-factorable if and only if it is 2p-regular, p≥1, and that a connectedcubic graph with at most two bridges has a 1-factor. Then, Hall, K¨onig, Tutte,Lov′asz et al. given a number of results about this field. The problem of factoris also an active direction in the field of discrete mathematics. In 1970s, Gareyand Johnson [8] proved that the problem of determining whether a graph has ak-tree is NP-Complete. Thus, the problem of finding the su?cient conditions ofthe existence of a k-tree in a connected graph is important. In 1972, Chva′taland Erd¨os [6] proved that every graph G with |G|≥3 andκ(G)≥α(G) hasa hamilton cycle. Therefore, G has a hamilton path T as its spanning tree.In this case,Δ(T)≤「(α(G))/(κ(G))」+ 1 = 2. It reminds many people to ask whetherk =「(α(G))/(κ(G))」+ 1 is the minimum possible k to find a k-tree of a connected graph.In 1990 and 1991, Jackson and Wormald [11], Neumann-Lara and Rivera-Campo[15] proved the above conjecture by the distinct way. They proved that everyconnected graph G has a「(α(G))/(κ(G))」+1 -tree. Furthermore, they showed that theirupper bound is sharp for connected graphs. In our paper, we consider the de-gree bounded spanning tree problem for the Cartesian product graph and directproduct graph, and improve their bound.Chapter two is devoted to study the degree bounded spanning tree problem on Cartesian product. Let G₁ and G₂ be graphs, their Cartesian product, denotedby G₁â–¡G₂, has the vertex set V (G₁)×V (G₂), and (u,v)～(u ,v ) if and only ifu = u and v～v or u～u and v = v . Let T be a tree and v∈V (T). Given apositive integer k with k≥Δ(T), let f_T(v,k) := k -d_T(v) be the deficiency of vto k in T, and let F_T(k) :=∑_v∈V(T) f_T(v,k) be the deficiency of T to k. Let Gibe a connected graph and let Ti be a ki-tree of Gi(i = 1,2), where |G₂|≥3 andk₂≥k₁. We prove that G₁â–¡G₂ has a k₁-tree if F_T1(k₁)≥k₂, or has a k₂-treeotherwise. Furthermore, we prove that if |T1|≥k₂ ? k₁ + 1 then G₁â–¡G₂ hasa k₁-tree. Let G be a connected graph with |G|≥3 and let r be a real numberwith r·κ(G)≥δ(G) andα(G)≥2r. We show that Gâ–¡G has a「(α(G))/(κ(G))」+1 -treeand (α(Gâ–¡G))/(κ(Gâ–¡G)) > (α(G))/(κ(G)). In addition, we give some examples to illustrate that ournew upper bound is better than the old one.Chapter three is devoted to study the degree bounded spanning tree problemon direct product. The direct product of two graphs G₁ and G₂, denoted byG₁×G₂, has the vertex set V (G₁)×V (G₂), and (u,v)～(u ,v ) in G₁×G₂if and only if u～u in G₁ and v～v in G₂. Let G₁ be a connected graphcontaining an odd cycle, and let G₂ be a traceable graph of even vertices. Weprove that if G₁ has a k-tree then G₁×G₂ has a (k + 1)-tree. Furthermore, ifG₁ has a k-tree T such that T + uu , uu∈E(G₁) \ E(T), contains an odd cyclefor vertices u,u∈V (T) satisfying that dT(u) <Δ(T) and dT(u ) <Δ(T), thenG₁×G₂ has a k-tree. We show that if G is a non-hamiltonian graph such thatG contains an odd cycle,δ(G)≥1 and n·κ(G)≥δ(G) for some positive integern then (α(G×P_2n))/(κ(G×P_2n)) > (α(G))/(κ(G)) +1. In addition, we give some examples to illustrate thatour new upper bound is better than the old one.