Flip dynamics on perfect matchings beyond bipartite and planar graphs
Abstract
We study the flip dynamics on perfect matchings of graphs, where a flip consists of replacing the edges of a perfect matching along an even cycle with the complementary alternating edges. In particular, we want to bound the minimum length of cycles such that any two perfect matchings are related by flips of such cycles.
Given a finite graph $G$, we consider the families of decorated graphs obtained by replacing each vertex of $G$ with a decoration satisfying suitable conditions on the existence of perfect matchings in its subgraphs. We prove a general upper bound for this family. We then obtain stronger bounds for two families of decorations: clique decorations and Fisher decorations, the latter under the assumption that the underlying graph is planar. In both cases, the bounds are independent of the sizes of the decorations.
이 뉴스, 어떠셨어요?
탭 한 번으로 반응 · 로그인 불필요