Back to Search Start Over

Removable edges in near‐bipartite bricks.

Authors :
Zhang, Yipei
Lu, Fuliang
Wang, Xiumei
Yuan, Jinjiang
Source :
Journal of Graph Theory. Jan2025, Vol. 108 Issue 1, p113-135. 23p.
Publication Year :
2025

Abstract

An edge e of a matching covered graph G is removable if G−e is also matching covered. The notion of removable edge arises in connection with ear decompositions of matching covered graphs introduced by Lovász and Plummer. A nonbipartite matching covered graph G is a brick if it is free of nontrivial tight cuts. Carvalho, Lucchesi and Murty proved that every brick other than K4 and C6¯ has at least Δ−2 removable edges. A brick G is near‐bipartite if it has a pair of edges {e1,e2} such that G−{e1,e2} is a bipartite matching covered graph. In this paper, we show that in a near‐bipartite brick G with at least six vertices, every vertex of G, except at most six vertices of degree three contained in two disjoint triangles, is incident with at most two nonremovable edges; consequently, G has at least |V(G)|−62 removable edges. Moreover, all graphs attaining this lower bound are characterized. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
03649024
Volume :
108
Issue :
1
Database :
Academic Search Index
Journal :
Journal of Graph Theory
Publication Type :
Academic Journal
Accession number :
180925400
Full Text :
https://doi.org/10.1002/jgt.23173