$b$-Invariant Edges in Essentially 4-Edge-Connected Near-Bipartite Cubic Bricks

摘要

A brick is a non-bipartite matching covered 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 a tight cut decomposition of $G-e$ contains exactly one brick. A 2-edge-connected cubic graph is essentially 4-edge-connected if it does not contain nontrivial 3-cuts. A brick $G$ is near-bipartite if it has a pair of edges ${e_1, e_2}$ such that $G-{e_1,e_2}$ is bipartite and matching covered.Kothari, de Carvalho, Lucchesi  and Little proved that each essentially 4-edge-connected cubic non-near-bipartite brick $G$, distinct from the 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, all the essentially 4-edge-connected cubic near-bipartite bricks, the numbers of $b$-invariant edges of which attain the lower bound, are presented.