Graphs with many independent vertex cuts

Yanan Hu, Xingzhi Zhan, Leilei Zhang

The 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$ there exist…