Xiumei Wang ; Cheng He ; Yixun Lin - Removable edges in near-bricks

dmtcs:600 - Discrete Mathematics & Theoretical Computer Science, July 29, 2013, Vol. 15 no. 2 - https://doi.org/10.46298/dmtcs.600
Removable edges in near-bricksArticle

Authors: Xiumei Wang 1; Cheng He 2; Yixun Lin 1

  • 1 School of Mathematics and Statistics [Zhengzhou]
  • 2 School of Science [Zhengzhou]

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.


Volume: Vol. 15 no. 2
Section: Graph Theory
Published on: July 29, 2013
Accepted on: June 9, 2015
Submitted on: October 7, 2011
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 368 times.
This article's PDF has been downloaded 840 times.