Some results on dominating induced matchings

DOI10.1007/S00373-022-02470-6zbMATH Open1485.05125arXiv1912.00511OpenAlexW2990716390MaRDI QIDQ2117540FDOQ2117540

Authors: Yanyan Li 

Publication date: 21 March 2022

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: 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 $chi(G)leqslant3$. 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 $$ and $$ if and only if $G$ is the Kneser graph with parameters $r-1$, $2r-1$.

Full work available at URL: https://arxiv.org/abs/1912.00511

Recommendations

• Dominating induced matchings
• On the dominating induced matching problem: spectral results and sharp bounds
• Dominating induced matching in some subclasses of bipartite graphs
• Dominating induced matching in some subclasses of bipartite graphs
• Some results on matching and total domination in graphs
• The Maximum Number of Dominating Induced Matchings
• New results on induced matchings
• On induced matchings
• \(O(n)\) time algorithms for dominating induced matching problems
• On matching and total domination in graphs

zbMATH Keywords

Kneser graphinduced matchingdominating induced matching

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Induced matchings
• Efficient edge domination in regular graphs
• Efficient edge domination problems in graphs
• Dominating induced matchings for \(P_7\)-free graphs in linear time
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Dominating induced matchings in graphs containing no long claw
• On the dominating induced matching problem: spectral results and sharp bounds

Cited In (4)

• Partition the vertices of a graph into induced matchings
• The Maximum Number of Dominating Induced Matchings
• A simple matching domain with indifferences and a master list
• Exact algorithms for dominating induced matching based on graph partition

This page was built for publication: Some results on dominating induced matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117540)