| Within the last thirty years, concurrent with the growth of computer science, graph theory has seen explosive growth. Perhapes the fastest growing area within graph theory is the study of domination in graphs. The rapid growth in the number of domination papers is attributable largely to three factors: (1) the diversity of applications to both real-world and other mathematical 'covering' or 'facility location' problems, such as coding theory, computer communication networks, monitor system, landing surveying and social network theory. (2) the wide variety of domination parameters that can be defined, about 40-50 different types of domination have been defined. (3) the NP-completeness of the basic domination problem, its close and 'natural' relationships to other NP-complete problems, and the subsequent interest in finding polynomial time solutions to domination problems in special classes of graphs.In this paper, we pay our attention mainly on the following four parts of domination in graphs:· Determining the bounds on several domination parameters and investigating the relationship between the domination parameters and other graphical parameters.· Characterizing the extremal graphs for inequalities involving in domination parameters.· Determining the bounds on dominating functions in graphs.· Discussing some problems on centrum and balance vertices in graphs.In Chapter 2, we investigate the bounds on classical domination and characterize some extremal graphs for inequalities involving in domination parameters.In 1993, Reed in [70] proved that every graph of order n with minimum degree at least three has a dominating set of at most 3n/8 vertices. In section 2.2, by modifying Reed's "disjoint path covering" method, we improve Reed's result to γ(G) ≤ (3n+|V2|)/8 , where V2 is the vertex set of degree 2, if G is a graph on n vertices with δ(G) ≥ 2. As an application of above result, we obtain an upper bound rk{G,γ) ≤ (3n+5k)/8 on k-restricted domination number of a graph G with order n and minimum degree at least three. It is well-known that γ(G) ≤ β(G) < α(G) holds for any connected graph G. In section 2.3, we give a complete characterization of those graphs G for which γ(G) = β(G) and δ(G) = 2. Furthermore, we investigate some special types of graphs G for which γ(G) =β(G).Although [78] shows that the parameters β and γt are not comparable for graphs with minimum degree at most 2, yet it is likely to compare β with γt for graphs with large minimumdegree. In section 2.4, we obtain that if G is claw-free graph and S(G) > 4, then 7t(G) < /3(G). This implies that Favaron's conjecture is true for claw-free graphs with 8{G) > 4. We believe that the result is true for any claw-free graph with minimum degree 3, although we were not able to settle it. If it is true, an example is given to illustrates the tight inequality.In the end of Chapter 2, we establish the Nordhaus-Gaddum inequalities on /c-domination number of graphs, which strengthens the conjecture on double domination number of graphs proposed by Harary and Haynes [29] in 1996.In Chapter 3, we investigate the paired-domination number in graphs, which was introduced by Haynes and Slater in [40] in 1998.Haynes and Slater in [40] showed that the problem of determining the paired-domination number 7p(G) of an arbitrary graph is NP-complete, and for any connected graph G with order n > 6 and S(G) > 2 they presented an upper bound 2n/3 of 7P(G) in terms of order of a graph. However, the authors only give an example Cq to see that the above bound is sharp, and give a family of graphs for which 7P(G) approach 2n/3 for large n. In section 3.1, we will give a complete characterization of graphs for which 7P(G) = 2n/3.In section 3.2, we provide a constructive characterization of those trees with equal total domination and paired-domination numbers.In section 3.3, we investigate the relationship between the paired-domination number 7P(G) of a graph and the coloring number of its complement. We show that 7P(G) < x(Gc) + 1 for any connected graph G whose complement is i^-free, except for several families of graphs.In Chapter 4, we discuss the domination functions in graphs, and obtain the following results.In 1999, Dunbar et al.[18] introduced the concept of minus domination and posed conjectured that for any bipartite graph G with order n, the minus domination number 7G > A{s/n + 1 — 1) — n. In section 4.2, we prove that the conjecture is true and establish another attained lower bound 7"(G) > \n - (1^ + 1+Jfjg^y))] for a bipartite graph G = (X,Y) with order n. where 6x = min{d(v)\v € X},5y — min{d(v)\v € Y}.The concept of fc-subdomination number 7/ts was introduced by Cockayne et al.[ll]. In the special cases k = \V\, 7^s is the signed domination number 7S(G). Cockayne et al. established a sharp lower bound on 7^s for trees. In section 4.3, we show that for any graph G of order n and size e, iks > n - 2f+("^)(^+2). Qy aDOve the results, we immediately obtain the lower bounds...
|
PDF Full Text Request