Some Results on Dominating Induced Matchings
share
Let G be a graph, a dominating induced matching (DIM) of G is an induced matching that dominates every edge of G. In this paper we show that if a graph G has a DIM, then χ(G) ≤ 3. Also, it is shown that if G is a connected graph whose all edges can be partitioned into DIM, then G is either a regular graph or a biregular graph and indeed we characterize all graphs whose edge set can be partitioned into DIM. Also, we prove that if G is an r-regular graph of order n whose edges can be partitioned into DIM, then n is divisible by 2r - 1r - 1 and n = 2r - 1r - 1 if and only if G is the Kneser graph with parameters r-1, 2r-1.
READ FULL TEXT