2019/12/01 by Saieed Akbari, Hossein Baktash, Akbari, Saieed +7
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1912.00511
openalex publication_date 2019/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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) \leqslant 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 \binom2r - 1r - 1 and n = \binom2r - 1r - 1 if and only if G is the Kneser graph with parameters r-1, 2r-1.