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 Connect in order to contact the contributor
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

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. ⟨10.46298/dmtcs.600⟩. ⟨hal-00980764⟩

Share

Metrics

Record views

84

Files downloads

938