具有两个弧轨道有向图的点连通性
|
摘要
图D是带有两个弧轨道的强连通有向图,D1与D2是图D在自同构Aut(D)作用在边集E(D)上的两个弧轨道,有:D1=D[E1];D2=D[E2]为D的两个弧传递部分.我们证明,图D的弧连通度等于最小度,并且图D的点连通度,当加入围长条件,如果满足g(G)≥δ(D)-1/δ(Di)+1;则κ(D)=δ(D),这里我们只考虑δ(Di)≥0(i=1,2)的情况,并且δ(Di)是Di的最小度;κ(D)是有向图D的点连通度.
Let D be a strongly connected digraph with two arc orbits,D1 and D2be its arc orbits under the action of Aut( D) on E( D). Let D1= D[E1]and D2= D[E2],Which are called the arc transitive parts of D.It is proved that the arc connectivity was its minimum degree. And for the vertex connectivity of graph,when the condition of the girth is added,it is inferred κ( D) = δ( D) if g( G) ≥δ( D)-1/δ( Di)+ 1. Under only considering the case where δ( Di) ≥0(i = 1,2) and δ(Di) is the minimum degree of Di;κ(D) is the minimum degree of Di and κ( D) is the vertex connectivity of D.
Let D be a strongly connected digraph with two arc orbits,D1 and D2be its arc orbits under the action of Aut( D) on E( D). Let D1= D[E1]and D2= D[E2],Which are called the arc transitive parts of D.It is proved that the arc connectivity was its minimum degree. And for the vertex connectivity of graph,when the condition of the girth is added,it is inferred κ( D) = δ( D) if g( G) ≥δ( D)-1/δ( Di)+ 1. Under only considering the case where δ( Di) ≥0(i = 1,2) and δ(Di) is the minimum degree of Di;κ(D) is the minimum degree of Di and κ( D) is the vertex connectivity of D.
引文
[1]Hamidoune Y O.Quelques de connecite dans les graphes oriente[J].Comb Thoery Ser B,1981,30:1~10.
[2]Hamidoune Y O.An application of connectivity theory in graphs to factorization of elements in group[J].Eur J Combine,1981,2:349~355.
[3]Mader W.Minimale n-fach kantenzusammenhangenden graphen[M].Math Ann,1971,191:21~28.
[4]Tindell R.Connectivity of cayley graphs,in:D.Z.Du,D.F.Hsu(Eds.).Combinatorial Network Theory[M].Dordrecht:Kluwer Academic Publishers,1996.41~64.
[5]侯学慧.2-边-轨道图的点连通性[J].山西师范大学学报(自然科学版),2012,(3):17~19.
[2]Hamidoune Y O.An application of connectivity theory in graphs to factorization of elements in group[J].Eur J Combine,1981,2:349~355.
[3]Mader W.Minimale n-fach kantenzusammenhangenden graphen[M].Math Ann,1971,191:21~28.
[4]Tindell R.Connectivity of cayley graphs,in:D.Z.Du,D.F.Hsu(Eds.).Combinatorial Network Theory[M].Dordrecht:Kluwer Academic Publishers,1996.41~64.
[5]侯学慧.2-边-轨道图的点连通性[J].山西师范大学学报(自然科学版),2012,(3):17~19.