Removable edges in near-bricks - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2013

Removable edges in near-bricks

Résumé

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.
Fichier principal
Vignette du fichier
2036-8207-1-PB.pdf (142.16 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00980764 , version 1 (18-04-2014)

Identifiants

Citer

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

Collections

TDS-MACS
89 Consultations
1200 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More