Wide Diameter Of The Kth Power Of Graphs

There are four chapters in this dissertation, which focuses on three subjects:the wide diameter of the kth power of paths and trees, and obtaining the boundof the wide diameter of the kth power of graphs; the wide diameter the kth powerof cycles and getting the bound of the kth power of hamiltonian graphs; the widediameter of the Harary graphs.The outline of the paper is arranged as follows:Chapter 1 presents the background, concept and main results of the research.Let G=G(V, E) be a k-connected simple graph and u, v be any two distinctvertices in V(G). Let D_k(u, v) be the collection of all k internally disjoint (u, v)-paths. Let P_k(u, v) be a family of k internally disjoint paths between u and v,i.e. P_k(u,v)={P₁, P₂, ..., P_k}, |P₁|≤|P₂|≤…≤|P_k|where |P_i| denotes the length of path P_i. We define the k-wide distance d_k(u, v)between u and v by d_k(u,v)=min{|P_k|:P_k(u,v)∈D_k(u,v)}and we define the k-wide diameter of G by d_k(G)=max{d_x(u,v):u,v∈V(G),u≠v}.Clearly, d_k(G)≥d_k-1(G)≥...≥d₁(G)=d(G), where d(G) is the diameter ofG.The purpose of chapter 2 is devoted to studying the connectivity of the kthpower of paths and trees, and their wide diameter i.e.,for k≤n-1, d_k(P_n^k)=「n/k」,and for k≤d(T)-1, d_k(T^k)≤「n/k」.Moreover, we obtain the upper bound of the wide diameter for the kth power ofa graph: for k≤d(G)-1, d_k(G^k)≤「n/k」. The purpose of Chapter 3 is devoted to study the wide diameter of the kthpower of cycles. For k≤(n-1)/2, we deduce the following d_2k(C_n^k)=「(n-2)/k」+1.By the above result, we obtain an upper bound of the wide diameter for the kthpower of a hamiltonian graph: for k≤d(G)-1, d_2k(G^k)≤「(n-2)/k」+1.In Chapter 4, we proceed to arrive at the wide diameter of Harary graphs H_k,n.For k odd and n even, d_k(H_k,n=「(n-2)/(k-1)」+1 for k≤n/2and for k＞n/2 d_k(H_k,n≤4.For a Harary graph H_k,n, if both k and n are odd, then d_k(H_k,n-1)≤d_k(H_k,n)≤d_k(H_k,n+1).