Research On Domination In Some Families Of Graphs

Domination in graphs is one of the hottest fields of graph theory,and come into a series of application fields.Research on domination in graphs have not only important theoretical,but also varied applications in such fields as design and analysis of communi-cation networks,optimization,social sciences,computational complexity,and algorithm design.In this dissertation,the domination number,packing number,Roman domination number and the sign domination number of graphs,have been studied.And some new results have been obtained.Since most of problems as domination in graphs are NP-complete for arbitrary graph, it is natural to gain a few exact values for domination number,such as complete graphs, complete bipartite graphs,paths,circle,stars,corona graphs,some Cartesian product graphs and so on.In this paper,we studied the domination number of generalized Petersen graphs P(n,k)(k=1,2,3),circulant graphs C(n,(1,k))and given out the exact values of graphs P(n,k)(k=1,2,3),C(n;{1,k})(k=2,3,4),and give a bound generalized Petersen graphs P(n,2k+1).The packing set has many applications in the world.Fisher D C studied the packing number of graphs and given the exact value of complete bipartite graphs,paths,circle, complete grid graphs and so on.In this paper,we investigate the Packing number of generalized Petersen graphs P(n,k)(k=1,2,3),circulant graphs C(n;{1,k})and give the exact values of graphs P(n,k)(k=1,2,3)and a bound of circulant graphs C(n;{1,k}).Roman domination in graph can be said to be the new subject of domination in graph.Cockayne E J et al.studied Roman domination number of graph and gave the exact value of some graphs,such as complete graphs,complete bipartite graphs,paths, circle,stars and so on.They also proved that the graphs P_3k,P_3k+2,C_3kand C_3k+2 are Roman graph for k≥1,and the graphs K_m,nare Roman graph for min{m,n}≠2. In this paper,we investigate the Roman domination number of regular graphs and give the exact values of generalized Petersen graphs P(n,2k+1)(k≥0),circulant graphs C(n;{1,k})(k≥2)and Cartesian product graphs C_5m□C_5n(m≥1,n≥1),and showed that Circulant graphs C(n;{1,3})is a roman graphs for n≥7 and n≠4 mod 5);The Circulant graphs C(n;{1,2,3,...,k})is a roman graphs for n≥4(n≠2k)and n≠1 rood(2k+1);Generalized Petersen graphs P(n,1)is a roman graphs for n≥3 and n≠2 mod 4;The generalized Petersen graphs P(n,3)is a roman graphs for n=11 or n≥7 and n≠3 mod 4;The generalized Petersen graphs P(n,2k+1)is a roman graphs for n=0 mod 4 and 0≤k≤(「n-1/2」-1)/2 mod 4;and Cartesian product graphs C_5m□C_5nis a roman graphs for n≥1,m≥1.Furthermore,the paper also studied sign edge domination number of the k-connected graphs and showed that there exists a family of k-connected graphs G_m,kwithγ_s^′(G_m,k)= -(k(m-1)(km+k+1))/2(k≥2,m≥1).And disproved one of conjectures which Xu posed.