Research On Rainbow Domination Problem In Generalized Circulant Graphs

Graph theory is not only an important branch of combinatorial mathematics, but also an important branch of Discrete Mathematics. Graph of the rainbow domination and its related problems are a hot research issue in recent years. Research on rainbow domination problem not only has important theoretical value, but also has important application value. It has been widely used to solve the problem of computer science, information science, network theory and other subject, and it has great significance for its research.In this thesis, we focus on 2-rainbow domination problem of generalized circulant graphs, and results of the study are as follows:(1). we studied 2-rainbow domination problem of generalized circulant graphs C(n;{1,2}). Then we proposed the exact values of 2-rainbow domination number of generalized circulant graphs C(n;{1,2}); (2). we studied 2-rainbow domination problem of generalized circulant graphs C(n;{1,3}). Then we proposed the exact values of 2-rainbow domination number of generalized circulant graphs C(n;{1,3}); (3). we studied 2-rainbow domination problem of generalized circulant graphs C(n;{1,2,...,k}). Then we proposed the exact values of 2-rainbow domination number of generalized circulant graphs C(n;{1,2,...,k}).Because the 2-rainbow domination problem of generalized circulant graphs is a NP-complete problem in this paper, so this research work not only has great significance for the rainbow domination problem, but also has a reference for other NP-complete problem. These results further enriched the circulant graphs rainbow domination problem.