Some Relationships Among Parameters Of K-domination In Graph

Concurrent with the growth of computer science, graph theory has seen explosive growth. Perhaps the fastest growing area within graph is the study of domination in graphs. Now, most researchers in domination concentrate their attention on the following aspects: (1) Determining the bounds on several domination parameters and investigating the relationships between domination parameters and other graphical parameters; (2) Studying the algorithmic complexity of domination-related parameters and designing algorithm of domination-related parameters; (3) Researching the dominating function and related parameters; (4) Discussing applications of domination theory in other fields.In this paper, we pay our attention mainly on the following four parts:1. We study upper bounds for k-domination, get one result: if graph G, with order n,its each connected branch has at least k+1 points, thenγ_k(G)≤[n/(k+1)], and weprove it is the best; the next result is: for any positive integer k, if G is a connectedgraph with order n (n≥k+1), the maximum degree A ,thenγ_k(G)≤[(n-Δ+k-1)]/k2.We discuss bounds for k-domination in connected graphs and getdiam(G)-2k+1≤γ_k~c(G)≤n-Δ_k,when k≥1,γ_k~c(G)<[2k+(k+1)/2]ir(G)-2k.3.Using the method of probability, we give upper bounds for k-domination and connected k-domination, that is for any positive integer k, if G is a connected graphwith order n (n>k + 1), the minimum degree 8 , thenγ_k{G)≤n(1+lnq)/q,γ_k~c{G)<(1 + o_δ(1))n(lngq)/q,when q = m(δ+1) + 2-t,m = [k/3] and t = 3[k/3]-k.4.We introduce other k-domination and investigate the relationships among them.