Study On Some Properties Of Perfect 2-matching Covered Graphs And Matching Extension

In this thesis,we study on some properties of perfect 2-matching covered graph and matching extension.Let G be a graph and V(G),E(G),? and ? denote the vertex set,the edge set,the vertex number and the edge number of G,respectively.Let v ? V(G)and H be a subgraph of G.Then ?H(v)= {u|uv ? E(G)and u ? V(H)}.In general,let D be a subgraph of G,then ?H(D)= {u|uv ? E(G)and v ? V(D)and u ? V(H)}.When H = G,we simply write ?(v)and ?(D)for ?H(v)and ?H(D).A perfect 2-matching M of a graph G is a spanning subgraph of G such that each component of M is either an edge or a cycle.If each edge of a graph G lies in some perfect 2-matching of G,then G is a perfect 2-matching covered graph.The bipartite double cover of G is a bipartite graph with bipartition(U,W)and has two vertices u?and u??for each vertex u of G such that u?? U and u??? W.If uv is an edge of G,then u?v??and v?u??are both edges of the bipartite double cover of G.In Chapter 2,we study the relationship between the perfect 2-matching covered graph and bipartite double cover.We prove that the bipartite double cover of a non-bipartite graph G with ??2 is a 1-extendable graph if and only if G is a perfect2-matching covered graph.So,we design an algorithm to determine whether G is a perfect 2-matching covered graph or not in O(???)time.The time complexity of the algorithm is optimal.Furthermore,we prove that the bipartite double cover of a non-bipartite graph G with ??2 is a minimally 1-extendable graph if and only if G is a minimally perfect 2-matching covered graph and for each e = xy?E(G),there is an independent set S in G such that |?G(S)| = |S| +1,x?S and |?G-xy(S)| = |S|.Let G be a connected graph and n be a position integer(n ??-22).The graph G is said to be n-extendable if every matching of size n extends to a perfect matchingof G.Lou and Yu conjectured that if G is n-extendable and ? ? 6n,then G is Hamiltonian.Li and Lou confirmed the conjecture for bipartite graphs.In Chapter3,we generalize Li and Lou's result and prove that if G is an n-extendable bipartite graph with ? > 6n,then G has a longest cycle C such that |V(C)| ? 6n.We prove that the bound for |V(C)| is sharp.Then,if G is an n-extendable bipartite graph,then the longest cycle in G has length at least min{?,6n}.We study that whether there is a Hamilton path between two vertices in an n-extendable bipartite graph or not.In Chapter 4,we prove that if G =(X,Y)is an n-extendable bipartite graph with ? ? 6n-2,then for any pair of vertices x ? X,y ? Y,there is a Hamilton path from x to y in G.The bound for ?(G)is sharp.Defect d-matching in a graph G is a matching which covers all but d vertices in G.A defect 0 matching is also called a perfect matching.A defect 1 matching is also called a near perfect matching.Let G be a connected graph and n be a positive integer(n ??-32).The graph G is said to be defect n-extendable if every matching of size n extends to a near perfect matching of G.Plummer showed that no planar graph is 3-extendable.In Chapter 5,we prove that no planar graph with ?(G)? 2 is defect 6-extendable and conjecture that no planar graph with ?(G)? 2 is defect 5-extendable.The result gives an upper bound of defect n-extendable for the planar graph.A planar graph G with ?(G)= 1 can be defect n-extendable where n is any positive integer.