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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.157--164
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00980764
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 18 avril 2014 - 16:43:45
Dernière modification le : mardi 24 avril 2018 - 13:24:02
Document(s) archivé(s) le : lundi 10 avril 2017 - 15:27:17

Fichier

2036-8207-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

713

Téléchargements de fichiers

300