Basic Maximal (m+1)K₂-free Graph

A matching M of G is induced [4]if E(V (M)) = M. The induced matchingnumber of G, denoted by IM(G), is the number of edges of a maximum inducedmatching of G. Is there a connected but not complete simple graph G, such that foreach pair of nonadjacent vertices x and y, IM(G+xy) = IM(G)+1? This problemis fundamental and very interesting . In this paper, we will consider the propertyof a maximal 2K2?free graphs and construct some maximal 2K2?free graphs oforder 12, 13, 14. H is called a proper induced subgraph of G if H is an inducedsubgraph of G with H = G. We call G a maximal (k + 1)K2?free graph, if G isa connected but not complete simple graph, such that for each pair of nonadjacentvertices x and y, IM(G + xy) = IM(G) + 1 = m + 1. Is there any cubic maximal(k + 1)K2?free graph? This problem is still open. We say G is a basic maximal(m+1)K2?free graph, if G is a maximal (m+1)K2?free graph without any properinduced subgraph of G being a maximal (n + 1)K2?free graph for any n∈N. LetX be a set of graphs, we say a simple connected graph H is a forbidden subgraph ofX, if, for each graph G∈X, H is not an induced subgraph of G. In this paper wewill study this problem and introduce some forbidden subgraphs of XC = {G : Gis a basic maximal (m + 1)K2?free graph, m∈N, G is cubic }.