由轮生成的Cayley图的广义3-连通度

摘要

令S?V（G）,κ_G（S）表示图G中内部不交的S-树T₁,T₂,…,T_r的最大数目r,使得对任意i,j∈{1,2,…,r}且i≠j,有V（T_i）∩V（T_j）=S,E（T_i）∩E（T_j）=?.定义κ_k（G）=min{κ_G（S）|S?V（G）,且|S|=k}为图G的广义k-连通度,其中k是整数,且2≤k≤n.令Sym（n）是在{1,2,…,n}上的对称群,T是Sym（n）的对换集合.G（T）表示点集是{1,2,…,n},边集是{ij|（ij）∈T}的图.若G（T）是一个轮图,则将Cayley图Cay(Sym（n）,T)简记为WG_n.主要研究由轮生成的Cayley图WG_n的广义3-连通度,并证明κ₃（WG_n）=2n-3,其中n≥4.

关键词

Cayley图 / 广义k-连通度 / 内部不交的S-树