Distance between two vertices of maximum matching graphs

DOI10.1007/S10255-004-0201-ZMaRDI QIDQ705048zbMATH OpenOpenAlexFDO

Authors Yan Liu

Publication date 25 January 2005

Published in Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10255-004-0201-z

zbMATH Keywords

alternating cyclesdistancemaximum matching graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

The maximum matching graph \({\mathcal M}(G)\) of a graph \(G\) is a graph whose vertices are the maximum matchings of \(G\), and two maximum matchings \(M\) and \(N\) of \(G\) are adjacent in \({\mathcal M}(G)\) if and only if \(| M-N| =1\). The author studies the distance between two vertices of the maximum matching graph. In particular, he gives a lower bound, and he presents a necessary and sufficient condition for graphs which achieve this bound.

Recommendations

• Subgraphs of maximum matching graphs
• Characterizations of maximum matching graphs of certain types
• The connectivity of maximum matching graphs
• Matching graphs
• On matchings in graphs

Cites work

• Graph theory with applications
• Hamiltonicity in (0-1)-polyhedra
• scientific article; zbMATH DE number 4051677 (Why is no real title available?)
• Matching graphs
• Z-transformation graphs of perfect matchings of hexagonal systems

Cited in

(8)

• Graphs isomorphic to their maximum matching graphs
• Subgraphs of maximum matching graphs
• The connectivity of maximum matching graphs
• scientific article; zbMATH DE number 4191716 (Why is no real title available?)
• Matching graphs
• \(Mn\)-polynomials of theta and Wagner graphs
• The structure of Eta graph with \(|V (g)| + 4\) maximum matchings
• Path-transformation graph of maximum matchings

This page was built for publication: Distance between two vertices of maximum matching graphs

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