Spanning Connectivity And Hamilton-connected Index Of Graphs

Let G=(V, E) be a connected graph. A graph G is hamiltonian if it has a Hamiltoncycle, and G is Hamilton-connected if there exists a Hamilton path between any two dis-tinct vertices of G. G is k-connected if there is a k-internally disjoint paths between anydistinct pair of vertices. The connectivity of a graph G, denoted by κ(G), is defined asthe smallest integer k such that after removing k vertices resulting graph is disconnected.In this thesis we investigate the spanning connectivity of powers of graphs and Hamilton-connected index of graphs. k-connectedness of graphs is a hybrid concept and extensionof connectivity and hamiltonicity. The main results are as follows.(a). For u, v∈V (G), ak-container C(u, v) is the set of k internally disjoint (u, v)-paths that contains all verticesof G. G is k-connected if there is a k-container between any distinct pair of vertices.The spanning connectivity of a graph G, denoted by κ (G), is defined as the largest in-teger k such that G is i-connected for1≤i≤k if G is1-connected and undefinedotherwise. We prove that if G is a connected graph with|V (G)|≥k+1≥4, then Gkis k-connected.(b). The hamiltonian index h(G)(Hamilton-connected index hc(G))of G is the least k for which the iterated line graph Lk(G) is hamiltonian (Hamilton-connected). Chatrand and Wall give an exact formula for the hamiltonian index of atree. We prove that for a tree T, h(T)≤hc(T)≤h(T)+1, and for unicyclic graphs G,h(G)≤hc(G)≤max{h(G)+1, k+1}, where k is the length of a longest path with allvertices on the cycle such that the two ends of it are of degree at least3and all internalvertices are of degree2. We also characterize the trees and unicyclic graphs G for whichhc(G)=h(G)+1.