| Domination theory is an important branch of the graph theory, it can be used in the computer science, networks, society study and so on. With the development of computer science and networks, the domination theory has made important growth. The domination problem is NP-C, so the study of domination is very hard. For the domination number, it may decrease, increase or equal to the original value by removing a vertex from a graph. If the removal of any vertex from the graph decrease the domination number, then the graph is called domination vertex critical. But for the addition of an edge to a graph, the domination number can only be decreased, or equal to the one. If the addition of any edge decrease the domination number, we call the graph domination edge critical. In this dissertation, we concentrate on the domination vertex critical and domination edge critical graphs for domination number 3.In 1983, Sumner initiated the study of domination edge critical graphs research; in 1984, Brigham et al. began the study of domination vertex critical graphs. For these two classes of graphs, the characterization of them forγ≤2 is easily derived, but forγ≥3, the characterization is far away.In chapter 1, we give some definitions, terminology and, notations, and some related ones on domination theory.In chapter 2, we mainly study the domination vertex critical graphs. It is given some factor result under the assumption without some special graphs. We obtain the following results:1. Let G be a 3-γ-vertex-critical graph of even order. If the minimum degree is at least three, then G is 3-connected.2. Let G be a 3-γ-vertex-critical graph of even order. If G is K1,4-free, and the minimum degree is at least four, then G is bicritical.3. If G is a K1,5-free 3-vertex-critical 2-connected graph of odd order with minimum degree three, then either G is one of the graphs shown in Fig. 2.10 or G is factor-critical.4. Let G be a 3-γ-vertex-critical graph.(i) If G is K1,6-free and |V(G)| is even, |V(G)|≠12, then G has a perfect matching. (ii) If G is K1,7-free of odd order, and o(G) = 1, |V(G)|≠13, then either G has a near perfect matching or G is one of Fig. 2.12 and Fig. 2.15.In chapter 3, we mainly study the domination edge critical graphs. In the first section, we introduce some known general results on domination edge critical graphs, and give the outline of the proof of the exists of Hamiltonian cycles. In the final section, we prove a conjecture: Let G be a graph with k≥2 and k(?) |V| (mod 2). Suppose G is a k-connected 3-γ-edge critical claw-free graph, if the minimum degree of G is at least k + 1, then G is k-factor-critical.In chapter 4, we introduce some other critical graphs with various domination parameter, such as the total domination edge critical graphs and diameter critical graphs.
|
PDF Full Text Request