{
  "id": "1905.07301",
  "version": "v1",
  "published": "2019-05-17T14:42:43.000Z",
  "updated": "2019-05-17T14:42:43.000Z",
  "title": "$b$-invariant edges in cubic near-bipartite brick",
  "authors": [
    "Fuliang Lu",
    "Xing Feng",
    "Yan Wang"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A brick is a non-bipartite graph without non-trivial tight cuts. Bricks are building blocks of matching covered graphs. We say that an edge $e$ in a brick $G$ is $b$-invariant if $G-e$ is matching covered and it contains exactly one brick. Kothari, Carvalho, Lucchesi, and Little shown that each essentially 4-edge-connected cubic non-near-bipartite brick $G$, distinct from Petersen graph, has at least $|V(G)|$ $b$-invariant edges. Moreover, they made a conjecture: every essentially 4-edge-connected cubic near-bipartite brick $G$, distinct from $K_4$, has at least $|V(G)|/2$ $b$-invariant edges. We confirm the conjecture in this paper. Furthermore, we characterized when equality holds.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-05-17T14:42:43.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "cubic near-bipartite brick",
      "invariant edges",
      "non-trivial tight cuts",
      "cubic non-near-bipartite brick",
      "non-bipartite graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}