\(b\)-invariant edges in essentially 4-edge-connected near-bipartite cubic bricks (Q2309225): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3010897959 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1905.07301 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Revision as of 04:53, 19 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(b\)-invariant edges in essentially 4-edge-connected near-bipartite cubic bricks |
scientific article |
Statements
\(b\)-invariant edges in essentially 4-edge-connected near-bipartite cubic bricks (English)
0 references
30 March 2020
0 references
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.
0 references
non-bipartite matching covered graph
0 references