\(b\)-invariant edges in essentially 4-edge-connected near-bipartite cubic bricks

Fuliang Lu ; Xing Feng ; Yan Wang

The electronic journal of combinatorics, Tome 27 (2020) no. 1

Résumé

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.

Détail

DOI : 10.37236/8945

Classification : 05C70, 05C75
Mots-clés : non-bipartite matching covered graph