Scholarlink

<p>A 3-connected graph is a <i>brick</i> if the graph obtained from it by deleting any two distinct vertices has a perfect matching. The importance of bricks stems from the fact that they are the building blocks of matching covered graphs. An edge cut <i>C</i> of a matching covered graph <i>G</i> is separating if the two <i>C</i>-contractions of <i>G</i> are matching covered. A brick is solid if it does not have any nontrivial separating cuts. Solid bricks have many interesting properties, but the complexity of determining whether a given brick is solid remains unknown. In this paper, we characterize all the claw-free solid bricks.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Claw-Free Solid Bricks

  • 期刊论文

  • 发表日期：

    2025年7月25日

查看全文
  • Jinqiu Zhou,
  • Xing Feng,
  • Weigen Yan

摘要

A 3-connected graph is a brick if the graph obtained from it by deleting any two distinct vertices has a perfect matching. The importance of bricks stems from the fact that they are the building blocks of matching covered graphs. An edge cut C of a matching covered graph G is separating if the two C-contractions of G are matching covered. A brick is solid if it does not have any nontrivial separating cuts. Solid bricks have many interesting properties, but the complexity of determining whether a given brick is solid remains unknown. In this paper, we characterize all the claw-free solid bricks.