Research On The Removable Edges Of Several Types Of Graphs

A connected graph G with at least two vertices is matching covered,if any edge of G is contained in a perfect matching of G.An edge e of a matching covered graph G is removable,if G-e is still a matching covered graph.Removable edge is related to the ear decompositions of matching covered graphs proposed by Lovász and Plummer,and it is a special removable ear.A single ear of a graph is a path of odd length with internal vertices of degree 2.A double ear of a graph G is a pair of vertex-disjoint single ears of G.Let G be a matching covered graph.Let R be an ear(single or double)of G.Denote by G-R the graph obtained from G by removing the edges and internal vertices of each single ear of G.If R is a removable single ear of length one then the edge of R is a removable edge.The removable edges of graphs are a powerful tool to study the construction of graphs and prove some properties of graphs by induction.In this paper,we mainly research on removable edges of several types of graphs.Firstly,the source of the subject and the research progress of removable edges are given.Then,it shows G×C2m(m≥2)is a matching covered graph and removable edges of G×C2m(m≥2)for nontrivial connected graph G;G×P2 is a matching covered graph,and removable edges of G×P2 for connected graph G;G ×Pl(l≥4)is a matching covered graph and removable edges of G × Pl(l≥4)for graph G with perfect matching.Next,we research on removable edges of graph by operation Y→Δ of 3 regular bipartite graphs.Finally,we research on removable edges of the generalized Petersen graphs.