竞赛图的超生成连通性

Super Spanning Connectivity of Tournaments

在有向图上给出了超生成连通度的定义.令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).

The definition of super spanning connectivity was given in digraphs.Let Dbe a digraph and u,v be any two vertices of D.Ak-container of Dis a set of kinternally disjoint paths between uand v.A k-container of Dis a k＊-container if it contains all vertices of D.Ak-container of Dis a strong k＊-container fromuto vif there is a set of internally disjoint paths with the same direction fromuto vand it contains all vertices of D.A digraph Dis super strongly k＊-connected if for any two vertices u,vof D,there is a strong k＊-container fromuto vand fromvto u.In particular,Dis super strongly 1＊-connected if Dis strongly Hamiltonian connected.It is shown that for all k≥2,a 2 k-strong tournament Tis super strongly r＊-connected（1≤r≤k）.