The Paired Domination Number Of Some Cartesian Product Graphs

Let G=(V, E) be a simple undirected graph without isolated vertices. A set D C V is a dominating set of G if every vertex in V\D is adjacent to at least one vertex in D. A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number, denoted by yp(G), is the minimum cardinality of a paired-dominating set in G. The paired domination number was first proposed by Haynes and Slater, and they proved that the problem of determining the paired domination number of general graphs is NP-complete.In this thesis, we determined the paired domination number of some special graphs. In the first chapter, we introduce the background and some definitions, and give a brief survey of the paired domination number of the cartesian product of paths with cy-cles. In the second chapter, we mainly determine the paired domination number of the Cartesian product of Cn□C5 according to the structural characteristics of the cartesian product of cycles with cycles. In the third chapter, we determine the paired domina-tion number of the Cartesian product of Cn□Pm (m=2,3) and Cm□Pn (m=3,4,5). In the fourth chapter, we summarize this paper and propose some further question of paired domination number of the cartesian product.