Graphs with many independent vertex cuts Yanan Hu Xingzhi Zhan and Leilei Zhang Department of Mathematics East China Normal University Shanghai 200241 China

2025-05-06 0 0 251.72KB 5 页 10玖币
侵权投诉
Graphs with many independent vertex cuts∗
Yanan Hu, Xingzhi Zhan and Leilei Zhang†
Department of Mathematics, East China Normal University, Shanghai 200241, China
Abstract
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≥
3 there exists a unique graph Gsatisfying the following conditions: (1) Gis k-
connected; (2) the independence number of Gis greater than k; (3) any independent
set of cardinality kis a vertex cut of G. The edge version of this result does not hold.
We also consider the problem when replacing independent sets by the periphery.
Key words. Vertex cut; connectivity; independent set
Mathematics Subject Classification. 05C40, 05C69
We consider finite simple graphs. For terminology and notations we follow the books
[2, 5]. It is known [4, p.46] that the cycles are the only 2-connected graphs in which any
two nonadjacent vertices form a vertex cut. We will generalize this fact and consider two
related problems.
We denote by V(G) the vertex set of a graph G. The order of G, denoted by |G|,is
the number of vertices of G. For S⊆V(G),the notation G[S] denotes the subgraph of
Ginduced by S. Let Ks, t denote the complete bipartite graph whose partite sets have
cardinality sand t, respectively.
Notation. The notation Ks,s −P M denotes the graph obtained from the balanced
complete bipartite graph Ks,s by deleting all the edges in a perfect matching of Ks,s.
∗E-mail addresses: huyanan530@163.com(Y.Hu), zhan@math.ecnu.edu.cn(X.Zhan),
mathdzhang@163.com(L.Zhang).
†Corresponding author.
1
arXiv:2210.15151v1 [math.CO] 27 Oct 2022
摘要：

Graphswithmanyindependentvertexcuts*YananHu,XingzhiZhanandLeileiZhang„DepartmentofMathematics,EastChinaNormalUniversity,Shanghai200241,ChinaAbstractThecyclesaretheonly2-connectedgraphsinwhichanytwononadjacentverticesformavertexcut.Wegeneralizethisfactbyprovingthatforeveryintegerk3thereexistsaunique...

展开>> 收起<<
Graphs with many independent vertex cuts Yanan Hu Xingzhi Zhan and Leilei Zhang Department of Mathematics East China Normal University Shanghai 200241 China.pdf

共5页,预览1页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：5 页 大小：251.72KB 格式：PDF 时间：2025-05-06

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 配电装置 动力学连接体 力的合成 高考理综 全宋诗作者索引 公务员考试
/ 5
评分 收藏
分享
立即下载
客服
关注