The Problem Of Partitioning Of Graphs Into Connected Subgraphs And The Connectivity Of Kronecker Product Of Graphs

In this article we will investigate the problem of partitioning the edge(vertex) set of a graph G into subsets of a prescribed size s such that the edges(vertices) in each part of the partition form the edge (vertex) set of a connected subgraph of G. Suppose T is a tree, we prove that T has a 3-edge partition if and only if for any vertex v with d(v)> 3, C1(T -υ)≥C2(T-υ). We also show that any connected graph G has a{3,4}-edge partition.For a graph G,κ(G) denotes its connectivity. The Kronecker product G1 x G2 of graphs G1 and G2 is the graph with the vertex set V(G1) x V(G2), two vertex (u1,υ1) and (u2,u2) being adjacent in G1x G2 if and only if u1u2∈E(G1) andυ1υ2∈E(G2). Guji and Vumar (A note on the connectivity of Kronecker products of graphs, Appl. Math. Lett.22(2009)1360-1363.) conjectured that for any nontrivial graph G,κ(G×Kn)= min{nK(G), (n - 1)δ(G)} when n≥3. In this article we will confirm that this conjecture is true.The thesis comprises three chapters.In Chapter 1, we presents the background of s-partition and connectivity of Kronecker products of graphs.In Chapter 2, we will prove that a connected graph has a 3,4-edge partition and presents a necessary and sufficient condition for the existence of a tree having a 3-edge partition.In Chapter 3, we confirm the validity of a conjecture, which states that for any non-trivial graph G,κ(G x Kn)= min{nκ(G), (n - 1)δ(G)} when n≥3.