Advanced search
Start date
Betweenand
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

On essentially 4-edge-connected cubic bricks

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