| Texto completo | |
| Autor(es): |
Kothari, Nishad
[1]
;
de Carvalho, Marcelo H.
[2]
;
Lucchesi, Claudio L.
[1]
;
Little, Charles H. C.
[3]
Número total de Autores: 4
|
| Afiliação do(s) autor(es): | [1] Univ Estadual Campinas, Campinas - Brazil
[2] UFMS Campo Grande, Campo Grande, MS - Brazil
[3] Massey Univ, Palmerston North - New Zealand
Número total de Afiliações: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ELECTRONIC JOURNAL OF COMBINATORICS; v. 27, n. 1 JAN 24 2020. |
| Citações Web of Science: | 0 |
| Resumo | |
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) | |
| Processo FAPESP: | 18/04679-1 - Menores conformes e orientações Pfaffianas |
| Beneficiário: | Nishad Bharat Kothari |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |