竞赛图的超生成连通性

作者：张云霞; 张博; 杨卫华^*

来源：中北大学学报(自然科学版), 2018, 39(04): 404-407.

• 哈密尔顿路
• Menger定理
• 竞赛图
• 生成连通性

在有向图上给出了超生成连通度的定义.令D是一个有向图,u和v是D中任意两个顶点,u和v之间的一个k-container是u和v之间有k条内部不相交的路的集合.如果k-container包含D中所有的点,则它被称为k*-container.如果从u到v有k条内部不相交的且方向相同的路的集合,并且它们包含D中所有的顶点,则k-container是从u到v的强k*-container.如果在有向图D中,都有从u到v的强k*-container和从v到u的强k*-container,则称D是超强k*-连通的.特别地,如果D是强哈密尔顿连通的,则称D是超强1*-连通的.证明了结论:当k≥2时,2k-强连通竞赛图T是超强r*-连通的(1≤r≤k).

• 单位
  太原理工大学; 山西省财政税务专科学校; 数学学院