Skip to Main content Skip to Navigation
Journal articles

Removable edges in near-bricks

Abstract : For a brick apart from a few small graphs, Lovász (1987) proposed a conjecture on the existence of an edge whose deletion results in a graph with only one brick in its tight cut decomposition. Carvalho, Lucchesi, and Murty (2002) confirmed this conjecture by showing the existence of such two edges. This paper generalizes the result obtained by Carvalho et al. to the case of irreducible near-brick, where a graph is irreducible if it contains no induced odd path of length 3 or more. Meanwhile, a lower bound on the number of removable edges of matching-covered bipartite graphs is presented.
Document type :
Journal articles
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/hal-00980764
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Friday, April 18, 2014 - 4:43:45 PM
Last modification on : Tuesday, April 24, 2018 - 1:24:02 PM
Long-term archiving on: : Monday, April 10, 2017 - 3:27:17 PM

File

2036-8207-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00980764, version 1

Collections

Citation

Xiumei Wang, Cheng He, Yixun Lin. Removable edges in near-bricks. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.157--164. ⟨hal-00980764⟩

Share

Metrics

Record views

769

Files downloads

1448