Deyu Wu ; Yipei Zhang ; Xiumei Wang - A note on removable edges in near-bricks

dmtcs:11747 - Discrete Mathematics & Theoretical Computer Science, June 19, 2024, vol. 26:2 - https://doi.org/10.46298/dmtcs.11747
A note on removable edges in near-bricksArticle

Authors: Deyu Wu ; Yipei Zhang ; Xiumei Wang

    An edge $e$ of a matching covered graph $G$ is removable if $G-e$ is also matching covered. Carvalho, Lucchesi, and Murty showed that every brick $G$ different from $K_4$ and $\overline{C_6}$ has at least $\Delta-2$ removable edges, where $\Delta$ is the maximum degree of $G$. In this paper, we generalize the result to irreducible near-bricks, where a graph is irreducible if it contains no single ear of length three or more.


    Volume: vol. 26:2
    Section: Graph Theory
    Published on: June 19, 2024
    Accepted on: April 10, 2024
    Submitted on: August 21, 2023
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 65 times.
    This article's PDF has been downloaded 35 times.