The Upper Bound Of Paired Domination Number Of Bipartite Cubic Graphs And Heuristic Algorithms For Pairing Domination Of Graphs

The domination set problem of graphs is a classic problem in graph theory research,and the paired-domination set problem is an important variant of the domination set problem,which is of great significance in both theory and applicationLet G=(V,E)be a simple undirected graph.For S (?) V,if every point in V\S has an edge connected to a point in S,and G[S]has a perfect match,then S is called a paireddomination set of G.γpr(G)=min{|S|:S is the paired-domination set of G.In 2014,a conjecture was proposed by Hartnell and Henning(see《Topics in Domination in Graphs》):If G is a third regular bipartite graph of order n,then γpr(G)≤n/2.In Chapter 2 of this article,we focus on this conjecture.Firstly,we prove that the paired-domination number of a three regular bipartite graph does not exceed 5/9n.Furthermore,we prove that if a three regular bipartite graph has a Hamiltonian cycle,this conjecture holds.In Chapter 3 of this article,we present two heuristic algorithms for solving paired-domination sets.