Cover The Vertices Of A Graph By Induced Matchings

Graphs considered in this paper are finite and simple. For a graph G, V(G) and E(G) denote its sets of vertices and edges, respectively. For a vertex set X C V(G), setE_G(X) = {uv(?)E(G) : u,v (?) X}. The neighbor set N_G{X) of X is denned byN_G{X) = {y(?) V(G) \ X : there is x(?) X such that xy (?) E{G)}. The pendant neighbor set N₀(X) of X is denned byN₀(X) = {y (?)N_G(X) : d(y) = 1}. For any vertex v, the pendant degree of v is defined byd₀{v) = |N₀(v)|. For M C E(G), set V(M)={v (?)V(G): there is x(? ) V(G) such that vx (?) M}.If M (?) E(G) and X (?) V(G) are such that X (?) V(M), we say M covers X. If M (?) E(G) and, for every two distinct edges e, f(?) M, V(e) (?) V(f) = (?), we say that M is a matching of G. M is called a perfect matching of G, if V(M) = V(G). A matching M is induced if E_G{V(M)) = M.A κ-partition of a set X is a κ-tuple (X₁, X₂,…, X_κ) such that X₁, X₂, ? ? ?, X_k aremutually disjoint subsets of X such that A κ-induced-matching partition ofa graph G which has a perfect matching is aκ-partition (V₁, V₂, …, V_κ) of V(G) such that, for each i (1 ≤i≤ κ), the subgraph G[V_i] of G induced by V_i is 1-regular. The induced matching partition number of a graph G, denoted by imp(G), is the minimum integer k such that G has a κ-induced-matching partition.