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

Graphs with Many Independent Vertex Cuts

  • Yanan Hu,
  • Xingzhi Zhan,
  • Leilei Zhang

摘要

Cycles are the only 2-connected graphs in which any two nonadjacent vertices form a vertex cut. We generalize this fact by proving that for every integer \(k\ge 3\) k 3 there exists a unique graph G satisfying the following three conditions: (1) G is k-connected; (2) the independence number of G is greater than k;  (3) any independent set of cardinality k is a vertex cut of G. However, the edge version of this result does not hold. We also consider the problem when replacing independent sets by the periphery.