2024/10/09 by Che, Zhongyuan · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2410.07411
Let G be a plane bipartite graph and M(G) be the set of all perfect matchings of G. The resonance graph R(G) is a graph whose vertex set is M(G), and two perfect matchings are adjacent in R(G) if their symmetric difference is a cycle forming the periphery of a finite face of G. It is known that any connected resonance graph can be isometrically embedded as a finite distributive lattice into hypercubes. The isometric dimension of a connected R(G), denoted by idim(R(G)), is the smallest dimension of a hypercube that R(G) can be isometrically embedded into. Let d be the number of finite faces of G such that there are no forbidden edges on their peripheries. We show that any connected R(G) has idim(R(G)) ≥ d and provide characterizations on when the equality holds. Moreover, if a connected R(G) has idim(R(G)) = d, then we design an algorithm to generate a binary coding of length d for all perfect matchings of G which induces an isometric embedding of R(G) as a finite distributive lattice into a d-dimensional hypercube without generating M(G). Our results provide answers for the fundamental cases of both open questions raised in [SIAM J. Discrete Math. \bf 22 (2008) 971--984.]