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.