Restricted Edge Connectivity Of Cartesian Product And Direct Product Graphs

In this article, we study the restricted edge connectivity of Cartesian product and direct product of regular graphs. For any connected graph G, letβ(G)=min{|S|:S(?)E(G) and G-S is a bipartite graph}. An edge cut S of G is called m-restricted if G-S contains no components of order less than m. The sizeλ_m(G) of minimum m-restricted edge cuts of graph G is called its m-restricted edge connectivity. Letξ_m(G) denote the minimum size of sets of edges with exactly one end in any given connected vertex-induced subgraph of order m. It is known that when m≤3,λ_m(G)≤ξ_m(G) holds for graph G that contains m-restricted edge cuts. Graph G is called maximally m-restricted edge connected ifλ_m(G)=ξ_m(G), and super m-restricted edge connected if any minimum m-restricted edge cut separates a component of order m. Let G₁â–¡G₂ and G₁×G₂ denote the Cartesian product and strong product of grahps G₁ and G₂. In this thesis, we obtain the following results.Theorem 2.1.7 Let G_i be a maximally edge connected k_i-regular graph with k_i≥2,i=1,2. Then G₁â–¡G₂ is super restricted edge connected if and only if it is not isomorphic to K_nâ–¡C_m.Theorem 2.2.9 Let G_i be a maximally edge connected k_i-regular graphs with k_i≥3, i = 1,2 and g(G₁â–¡G₂) = 3. Then G₁â–¡G₂ is super 3-restricted edge connected if and only if it is not isomorphic to K_nâ–¡G, where G is 3-regular.Theorem 2.3.1 Let G_i be a maximally edge connected k_i-regular graph with k_i≥3 and g(G_i)≥4, i = 1,2. Then G₁â–¡G₂ is super 3-restricted edge connected.Theorem 3.1.5 Let G_i be a super edge connected nonbipartite graph with 2β(G_i)＞δ_i, i = 1,2. Then G₁×G₂ is super edge connected.Theorem 3.2.2 Let G_i be a k_i-regular nonbipartite graph with k_i≥3, i = 1,2. If G_i is super restricted edge connected and 2β(G_i)＞3k_i-2, then G₁×G₂ is super restricted edge connected.