K, Domination Edge Critical Graphs, Hamiltonian And The Minimum Number Of Edges

The domination problem is an activity field of graph theory in recent years and it has a lot of actual applications. In 1981, Cockayne proved that the calculation of the domination number on arbitrary graph was a NP-hard problem. To some particular graphs, Dewdney proved the calculation of domination number on bipartite graph was a NP-hard problem; Booth proved it on chord graph; Yannakakis proved it on line graph. So researching the problems correlative to domination has great theory meaning.The domination-critical problem is an important embranchment of domination problem. It has two classes: one is domination edge-critical problem; the other is domination vertex-critical problem. This paper mainly uses the combine of computer's computation and mathematic ratiocination, aims at Hamilton and minimum edges properties on domination edge-critical graph.Wojcicka supposed that all 3-connected, domination 4-edge-critical graphs were Hamilton graph. She also supposed that all (k-1)connected, domination k-edge-critical graphs were Hamilton graph. This paper gives out a series of 3-connected, domination 4-edge-critical graphs without Hamilton cycle. So we prove that Wojcicka's conjecture can not come into existence when k=4.f(n,k) denotes the minimum edges of domination k-edge-critical graph with n vertexes.Easily we can get f(n,1) = , f(n,2) = , Sumner conjecturedf(n,3) . This paper gives out two classes of domination k-edge-critical graphrespectively when k is even and odd, proves that:f(n,k) (2k -2)...