Connectivity Of The Cartesian Product And The Lexicographic Product Of Graphs

With the rapid development of communication networks, many theoreticalproblems have come into focus, one of which is the reliability of the network.Graphs are often used as a model for networks, for example transport networks,telecommunication systems, a network of servers and so on. Typically, the net-works and thus the representing graphs are connected; that means, that thereexists a path between all pairs of two vertices in the graph. But sometimes anelement of the network fails, for the graphs that means the removal of a ver-tex or an edge. Clearly, it is desirable that a network stays connected as longas possible in case faults should arise. The graph theoretical parameter edge-connectivityλ(G) equals the minimum number of edges, whose removal discon-nects the graph. Analogously, the vertex-connectivityκ(G) equals the minimumnumber of vertices, whose removal disconnects the graph. The connectivity andedge connectivity are important measure of the network's reliability. The con-cept of the connectivity, however, has some deficiencies. Consequently, manyvariations have been introduced, which are known as higher connectedness, suchas max-λ(a)(max-κ(G)), super-λ(G)(super-κ(G)) and hyper-κ(G), etc.On the other hand, the Cartesian product and lexicographic product are impor-tant methods to construct a bigger graph, and play an important role in designand analysis of networks. In this thesis, we study the higher connectedness forthe Cartesian product and the lexicographic product of two graphs.In this paper, sufficient conditions for the Cartesian product of two graphs or thelexicographic product of two graphs to be maximum edge-connected, maximumconnected, super edge-connected, super connected or hyper connected are pre-sented. Some conditions are shown to be also necessary. In addition, propertieson local cuts and generalized cuts in these two kinds of product of graphs arealso considered.For the Cartesian product of two graphs, we have the following main results: (1) If G_i are max-λfor i=1, 2, then G₁×G₂ is max-λ.(2) Assumeλ_i≥2 orλ₁=1, 2≤λ₂＜n-1. If G_i are max-λfor i=1, 2, thenG₁×G₂ is super-λ.(3) If G_i are max-κfor i=1, 2, then G₁×G₂ is max-κ.(4) Assumeκ_i≥2 orκ₁=1, 2≤κ₂＜n-1. If G_i are max-κfor i=1, 2, thenG₁×G₂ is super-κ.(5) Assumeκ_i≥2 orκ₁=1 and 2≤κ₂＜n-1. If G_i are max-κfor i=1, 2,then G₁×G₂ is hyper-κ.(6) Every smallest generalized cut in G₁×G₂ is a local cut if it satisfies one ofthe following conditions:(a) G_i are max-κandδ(G_i)≥2 for i=1, 2,(b) G₁≌K₂, 2≤δ(G₂)＜n-1 and G₂(?)K₃.For the lexicographic product of two graphs, we have the following main re-sults:(1) If X and Y are max-λ, then X[Y] is super-λ.(2) X[Y] is max-κif and only if X is a complete graph and Y is max-κ.(3) X[Y] is super-κif and only if X is a complete graph and Y is super-κ.(4) X[Y] is hyper-κif and only if X is a complete graph and Y is hyper-κ.(5) If X is a complete graph and Y have the property that every smallest gener-alized cut is a local cut, then every smallest generalized cut of X [Y] is a local cut.