| Full text | |
| Author(s): |
Kothari, Nishad
[1]
;
de Carvalho, Marcelo H.
[2]
;
Lucchesi, Claudio L.
[1]
;
Little, Charles H. C.
[3]
Total Authors: 4
|
| Affiliation: | [1] Univ Estadual Campinas, Campinas - Brazil
[2] UFMS Campo Grande, Campo Grande, MS - Brazil
[3] Massey Univ, Palmerston North - New Zealand
Total Affiliations: 3
|
| Document type: | Journal article |
| Source: | ELECTRONIC JOURNAL OF COMBINATORICS; v. 27, n. 1 JAN 24 2020. |
| Web of Science Citations: | 0 |
| Abstract | |
Lovasz (1987) proved that every matching covered graph G may be uniquely decomposed into a list of bricks (nonbipartite) and braces (bipartite); we let b(G) denote the number of bricks. An edge e is removable if G - e is also matching covered; furthermore, e is b-invariant if b(G - e) = 1, and e is quasi-b-invariant if b(G - e) = 2. (Each edge of the Petersen graph is quasi-b-invariant.) A brick G is near-bipartite if it has a pair of edges [e, f] so that G - e - f is matching covered and bipartite; such a pair [e, f] is a removable doubleton. (Each of K-4 and the triangular prism (C-6) over bar has three removable doubletons.) Carvalho, Lucchesi and Murty (2002) proved a conjecture of Lovasz which states that every brick, distinct from K-4, (C-6) over bar and the Petersen graph, has a b-invariant edge. A cubic graph is essentially 4-edge-connected if it is 2-edge-connected and if its only 3-cuts are the trivial ones; it is well-known that each such graph is either a brick or a brace; we provide a graph-theoretical proof of this fact. We prove that if G is any essentially 4-edge-connected cubic brick then its edge-set may be partitioned into three (possibly empty) sets: (i) edges that participate in a removable doubleton, (ii) b-invariant edges, and (iii) quasi-b-invariant edges; our Main Theorem states that if G has two adjacent quasi-b-invariant edges, say e(1) and e(2), then either G is the Petersen graph or the (near-bipartite) Cubeplex graph, or otherwise, each edge of G (distinct from e(1) and e(2)) is b-invariant. As a corollary, we deduce that each essentially 4-edge-connected cubic non-near-bipartite brick G, distinct from the Petersen graph, has at least vertical bar V(G)vertical bar b-invariant edges. (AU) | |
| FAPESP's process: | 18/04679-1 - Conformal minors and Pfaffian orientations |
| Grantee: | Nishad Bharat Kothari |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |