Triangle‐free equimatchable graphs

DOI10.1002/JGT.22750MaRDI QIDQ6057652zbMATH OpenOpenAlexFDO

Authors Yasemin Büyükçolak, Sibel Özkan, Didem Gözüpek

Publication date 5 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

equimatchablefactor-criticalgirthgraph familiestriangle-free

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Abstract: A graph is called equimatchable if all of its maximal matchings have the same size. Frendrup et al. [8] provided a characterization of equimatchable graphs with girth at least $5$. In this paper, we extend this result by providing a complete structural characterization of equimatchable graphs with girth at least $4$, i.e., equimatchable graphs with no triangle, by identifying the equimatchable triangle-free graph families. Our characterization also extends the result given by Akbari et al. in [1], which proves that the only connected triangle-free equimatchable $r$-regular graphs are $C_5$, $C_7$ and $K_{r,r}$, where $r$ is a positive integer. Given a non-bipartite graph, our characterization implies a linear time recognition algorithm for triangle-free equimatchable graphs.

Recommendations

• Equimatchable regular graphs
• Equimatchable claw-free graphs
• Equimatchable graphs are \(C_{2k+1}\)-free for \(k\geq 4\)
• Equimatchable bipartite graphs
• Efficient recognition of equimatchable graphs

Cites work

• Efficient recognition of equimatchable graphs
• Equimatchable claw-free graphs
• Equimatchable factor‐critical graphs
• Equimatchable graphs are \(C_{2k+1}\)-free for \(k\geq 4\)
• Equimatchable Graphs on Surfaces
• Equimatchable regular graphs
• Finding and counting given length cycles
• scientific article; zbMATH DE number 3873377 (Why is no real title available?)
• scientific article; zbMATH DE number 5717196 (Why is no real title available?)
• Matching-perfect and cover-perfect graphs
• Matchings in polytopal graphs
• Powers of tensors and fast matrix multiplication
• Randomly matchable graphs
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• The structure of well-covered graphs and the complexity of their recognition problems

Cited in

(9)

• Equimatchable claw-free graphs
• Equimatchable bipartite graphs
• On well-edge-dominated graphs
• scientific article; zbMATH DE number 1080082 (Why is no real title available?)
• Equimatchable regular graphs
• Graphs with each edge in at most one maximum matching
• Critical equimatchable graphs
• On well (edge) dominated and equimatchable strong product graphs
• Equimatchable graphs are \(C_{2k+1}\)-free for \(k\geq 4\)

This page was built for publication: Triangle‐free equimatchable graphs

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