Research On Connected Domination In Generalized Petersen Graph And Circle Graph

Connected Domination in graphs is one of hot fields of graph theory. The research on connected domination in graphs has not only important theoretical, but also varied applications in such fields as optimization, design and analysis of communication networks, network search and pattern recognition.Since E. Sampathkumar and H. B. Walikar define a connected dominating set of a graph in 1979, many researches are made on connected domination. And many of them focus on algorithm application and character study. At the same time, some related conception, for example totall domination, critical domination, dependence domination and tree domination, are created by connected domination and attract people's attentions and are studied.For the connected domination and tree domination of generalized Pertersen graph and Circle graph not be solved, in this paper, mainly use the combine of computer's computation and mathematic ratiocination, aims at connected domination properties on generalized Pertersen graph and Circle graph, and then get the following conclusions.For every n≥4 and every k≥1, then we haveγ_c(P(n, k)) =γ_rr(P(n, k)). For every n≥4 and k=1, thenγ_c(P(n, 1))=γ_tr(P(n, 1))=n. For every odd n≥5 and k=2, thenγ_c (P(n, 2))=γ_tr(P(n, 2))=n-1. For every even n≥6 and k=2, thenγ_c(P(n, 2))=γ(1r)(P(n, 2))=n. For every n≥17 and k=4, thenγ_tr(P(n, 4))=n-1. For every n≥25 and k=6, thenγ_tr(P(n, 6))=n-1. For every n≥33 and k=8, thenγ_tr(P(n, 8))=n-1. Then by these conclusions, this paper gives a conjecture: for every even k≥4 and every n≥4k+1, thenγ_c(P(n, k))=γ_1r(P (n, k))=n-1.For every k≥1, then the lower bounds of the connected domination number and the tree domination number areγ_c(C(n;{1, k}))≥(?) andγ_1r(C(n; {1,k}))≥(?). For every n≥5, and k=2, thenγ_tr(C(n;{1,2}))=(?)-1. Forevery n≥7 and k=3, then (?)...