On 2-matching covered graphs and 2-matching deleted graphs

College of Science, Nanjing Forestry University, Nanjing, Jiangsu 210037, P.R. China

^* Corresponding author: guowei_dai@aliyun.com

Received: 24 June 2022
Accepted: 3 October 2022

Abstract

For a family of connected graphs A, a spanning subgraph H of a graph G is called an A-factor of G if each component of H is isomorphic to some graph in A. A graph G has a perfect 2-matching if G has a spanning subgraph H such that each component of H is either an edge or a cycle, i.e., H is a {P₂, C_i|i ≥ 3}-factor of G. A graph G is said to be 2-matching covered if, for every edge e ∈ E(G), there is a perfect 2-matching M_e of G such that e belongs to M_e. A graph G is called a 2-matching deleted graph if, for every edge e ∈ E(G), G − e possesses a perfect 2-matching. In this paper, we first obtain respective new characterizations for 2-matching covered graphs in bipartite and non-bipartite graphs by new proof technologies, distinct from Hetyei’s or Berge’s classical results. Secondly, we give a necessary and sufficient condition for a graph to be a 2-matching deleted graph. Thirdly, we we prove that planar graphs with minimum degree at least 4 and K_1,r-free graphs (r ≥ 3) with minimum degree at least r + 1 are 2-matching deleted graphs, respectively.