Research On Domination In Graphs

Domination in graphs is one of hot fields of graph theory. Research on domination in graphs have not only important theoretical, but also varied applications in such fields as optimization, design and analysis of communication networks, social sciences, computational complexity, and algorithm design.In this dissertation, the connected and tree domination of generalized Petersen graphs P(n, k) and some properties of several types of domination critical graphs, including Hamiltonicity, diameter and size, have been studied.Connected dominating set has many applications in networks design. Tree dominating set is one type of connected dominating set. The paper studied the connected and tree domination number of generalized Petersen graphs P(n, k), proved that these parameters of P(n, k) are equal for generalized Petersen graphs P(n, k), and showed that the connected and tree domination number of generalized Petersen graphs P(n, k) for k=1,2,4,6,8,n/2.Hamiltonicity is a significant property of graphs. Wojcicka proved that every 3-edge domination critical graph with more than 6 vertices has a Hamilton path and conjectured (k-1)-connected, k-edge domination critical graphs are Hamiltonian. The paper extended the graphs with Hamilton path from 3-edge domination critical graphs to 3-(-γ,2)-critical graphs, constructed a class of 3-connected, 4-edge domination critical Non-hamiltonian graphs and disproved Wojcicka's conjecture.The size of a graph represents the number of networks links. The paper constructed several classes of k-edge domination critical and k-(γ, 2)-critical graphs and showed the upper bounds of size in k-edge domination critical and k-(γ, 2)-critical graphs.The diameter of a graph is closed with transmission delay of networks. Throughout constructing one classes of k-vertex domination critical and k-vertex total domination critical graphs with diameter 2, the paper solved one of problems which Goddard et. al. posed. The paper studied dot-critical graphs and showed the diameter of 4-dot-critical and totally 4-dot-critical graphs. The paper also studied and showed the diameter of k-edge connected domination critical graphs.