Some results on dominating induced matchings

DOI10.1007/S00373-022-02470-6MaRDI QIDQ2117540zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 21 March 2022

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

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

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)

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$.

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

Cites work

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

Cited in

(7)

• 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
• On the dominating induced matching problem: spectral results and sharp bounds
• On \(H\)-dominating matchings and some number partitions
• Exact algorithms for dominating induced matching based on graph partition
• Dominating induced matchings of finite graphs and regularity of edge ideals

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)