Domination Number And Restricted Edge Connectivity Of Product Graphs

As a special kind of graphs, product graphs have many particular and beau-tiful properties. The topologies of most of the international network are product graphs, so practically it is worth studying the property of these graphs.Connectivity, which mainly includes connectivity and edge connectivity, is one of the most basic invariants of graphs. It is an important parameter to measure the reliability of interconnection networks. Domination number is also a basic invariants of graphs, it is one of the most important parameters to reflect the optimization of networks. So the study on these two parameters is of practical value. This work study the properties of domination number and restricted edge connectivity of product graphs.Chapter 1 presents a simple introduction of the background and some basic concepts.In Chapter 2, we determine the domination number of 7 x n grid graph, i.e.γ7,n=[5n+3/3].A minimum dominating set of 7×n grid graph is also presented.Chapter 3 shows that the domination numberγ(G (?) H) of the lexicographic product graph G(?)H is upper bounded byγ(G)γ(H), which is exemplified reach-able. It is also proved thatγ(G(?)H)=γ(G) whenγ(H)=1;γ(G(?)H)=γt(G) whenγ(H)≥2 and G contains no isolated vertex, whereγt is the total domina-tion number.Chapter 4 determines the restricted edge connectivity of strong product of two triangle-free graphs, i.e.λ'(G1(?)G2)=min{λ1(n2+2m2),λ2(n1+2m1),ξ(G1)(?) G2}, which yields a sufficient and necessary condition and a simple sufficient condition for these strong product graphs to be super restricted edge connected.Chapter 5 presents an explicit expression of the restricted edge connectivity of lexicographic product graphs, i.e.λ'(G1(?)G2)=min{λ1n22,ξ(G1(?)G2)}, which yields a sufficient and necessary condition and two simple sufficient conditions for these graphs to be super restricted edge connected.