Research On Games And Matching Problems On Graphs

Game on graphs and matching of graphs are important topics in graph theory.They not only benefit to understand the structure and properties of graphs but also have wide applications in computer science,combinatorial optimization,information theory and so on.This dissertation first studies two types of games played on graphs by using tradi-tional combinatorial game theory,and gives the outcome and winning strategy of these games.Moreover,this dissertation analyzes the non-feasible edge sets of matching cov-ered graphs by using the interrelated properties of matching covered graphs and ear de-compositions theorem,and obtains some results about non-feasible edge sets of matching covered graphs.The main contributions of this dissertation are summarized as follows:(1)Proper 2-coloring game on some trees are studied.Based on the Sprague-Grundy function theory,we study proper 2-coloring game on a special caterpillar by splitting proper 2-coloring game on larger graph into some proper 2-coloring games on smaller graph.We compute the Sprague-Grundy value of all positions of this game,and provide the winning strategy of this game.(2)We discuss SOS game on graphs which may end in a draw.Based on the theory of positional game,we obtain the outcomes and the optimal strategy of SOS game played on path and cycle respectively by analyzing the decisions taken by players.According to the properties of complete bipartite graph,we prove that the outcome of SOS game played on complete bipartite graph is draw,and give the optimal strategy.By the results of SOS game played on path and cycle,we show that the outcome of SOS game played on Petersen graph is draw,and give the optimal strategy.(3)Non-feasible edge sets of matching covered graphs are studied.First when G is matching-covered and bipartite,we show that X is non-feasible if and only if X is switching-equivalent to empty set,which extends the result of Lukot'ka and Rollova.Next we study matching-covered graphs G whose non-feasible edge sets are switching-equivalent to empty set or E,and partially characterizes these matching-covered graphs in terms of their ear decompositions.Finally,we focus on a problem proposed by He et al about non-feasible edge sets of 3-connected and r-regular graphs.For an arbitrary integer r with r? 3,we construct infinitely many r-connected and r-regular graphs of class 1 containing non-feasible edge sets which are not switching-equivalent to either empty set or E.This result provides a negative answer to the problem proposed by He et al.