{
  "id": "1710.00761",
  "version": "v1",
  "published": "2017-10-02T16:29:45.000Z",
  "updated": "2017-10-02T16:29:45.000Z",
  "title": "Resonance Graphs and Perfect Matchings of Graphs on Surfaces",
  "authors": [
    "Niko Tratnik",
    "Dong Ye"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a graph embedded in a surface and let $\\mathcal F$ be a set of even faces of $G$ (faces bounded by a cycle of even length). The resonance graph of $G$ with respect to $\\mathcal F$, denoted by $R(G;\\mathcal F)$, is a graph such that its vertex set is the set of all perfect matchings of $G$ and two vertices $M_1$ and $M_2$ are adjacent to each other if and only if the symmetric difference $M_1\\oplus M_2$ is a cycle bounding some face in $\\mathcal F$. It has been shown that if $G$ is a matching-covered plane bipartite graph, the resonance graph of $G$ with respect to the set of all inner faces is isomorphic to the covering graph of a distributive lattice. It is evident that the resonance graph of a plane graph $G$ with respect to an even-face set $\\mathcal F$ may not be the covering graph of a distributive lattice. In this paper, we show the resonance graph of a graph $G$ on a surface with respect to a given even-face set $\\mathcal F$ can always be embedded into a hypercube as an induced subgraph. Furthermore, we show that the Clar covering polynomial of $G$ with respect to $\\mathcal F$ is equal to the cube polynomial of the resonance graph $R(G;\\mathcal F)$, which generalizes previous results on some subfamilies of plane graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-10-02T16:29:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C70",
      "05C10",
      "05C31"
    ],
    "keywords": [
      "resonance graph",
      "perfect matchings",
      "even-face set",
      "plane graph",
      "matching-covered plane bipartite graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}