Well-indumatched Trees and Graphs of Bounded Girth
From MaRDI portal
Publication:5060441
zbMATH Open1506.05165arXiv1903.03197MaRDI QIDQ5060441FDOQ5060441
Authors: S. Akbari, Tınaz Ekim, Amir Hossein Ghodrati, S. Zare 
Publication date: 10 January 2023
Abstract: A graph G is called well-indumatched if all of its maximal induced matchings have the same size. In this paper we characterize all well-indumatched trees. We provide a linear time algorithm to decide if a tree is well-indumatched or not. Then, we characterize minimal well-indumatched graphs of girth at least 9 and show subsequently that for an odd integer g greater than or equal to 9 and different from 11, there is no well-indumatched graph of girth g. On the other hand, there are infinitely many well-indumatched unicyclic graphs of girth k, where k is in {3, 5, 7} or k is an even integer greater than 2. We also show that, although the recognition of well-indumatched graphs is known to be co-NP-complete in general, one can recognize in polynomial time well-indumatched graphs where the size of maximal induced matchings is fixed.
Full work available at URL: https://arxiv.org/abs/1903.03197
Recommendations
- On a conjecture about trees in graphs with large girth
- Publication:4734761
- Graph-Theoretic Concepts in Computer Science
- Induced subgraphs of bounded degree and bounded treewidth
- Maximum induced forests in graphs of bounded treewidth
- Induced Forests in Regular Graphs with Large Girth
- scientific article; zbMATH DE number 1002021
- Bounds on the arboricities of connected graphs
- scientific article; zbMATH DE number 9665
- On upper bounds in tree-diameter sets of graphs
Cites Work
- WELL-COVERED GRAPHS: A SURVEY
- Clustering and domination in perfect graphs
- A Linear Algorithm for Computing of a Minimum Weight Maximal Induced Matching in an Edge-Weighted Tree
- Title not available (Why is that?)
- Induced matchings
- A characterization of graphs of girth eight or more with exactly two sizes of maximal independent sets
- Recognizing Greedy Structures
- Dominating sets for split and bipartite graphs
- Problems and results in combinatorial analysis and graph theory
- NP-completeness of some generalizations of the maximum matching problem
- Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
- New results on maximum induced matchings in bipartite graphs and beyond
- Strong edge-colouring and induced matchings
- Graphs with maximal induced matchings of the same size
- On the approximability of the maximum induced matching problem
- New results on induced matchings
- Title not available (Why is that?)
- Maximum induced matchings for chordal graphs in linear time
- Title not available (Why is that?)
- Title not available (Why is that?)
- On graphs with polynomially solvable maximum-weight clique problem
- Bipartite Domination and Simultaneous Matroid Covers
- Approximability results for the maximum and minimum maximal induced matching problems
- On graphs with maximal independent sets of few sizes, minimum degree at least 2, and girth at least 7
- Well covered simplicial, chordal, and circular arc graphs
- Efficient recognition of equimatchable graphs
- On two extensions of equimatchable graphs
- Irredundancy in circular arc graphs
- Title not available (Why is that?)
- Well-totally-dominated graphs
- On almost well-covered graphs of girth at least 6
- A characterization of well-indumatchable graphs having girth greater than seven
- Title not available (Why is that?)
Cited In (7)
- Induced and weak induced arboricities
- Graphs with maximal induced matchings of the same size
- Properties of Faltings height
- Heights and regulators of number fields and elliptic curves
- On the finiteness of abelian varieties with bounded modular height
- Well-indumatched pseudoforests
- A characterization of well-indumatchable graphs having girth greater than seven
This page was built for publication: Well-indumatched Trees and Graphs of Bounded Girth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5060441)
