\(b\)-invariant edges in essentially 4-edge-connected near-bipartite cubic bricks (Q2309225): Difference between revisions

Summary: 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. \textit{N. Kothari} et al. [Electron. J. Comb. 27, No. 1, Research Paper P1.22, 44 p. (2020; Zbl 1431.05123)] 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.