关于n-方体的2-虹连通(英文)

On the rainbow 2-connectivity of graph n-cube

边着色图中的一条路称为虹当它的边着色各不相同.如果一个图的任意两点间存在k条内部不交的虹,则称该图为k-虹连通图.记rCk(G)为使图G为k-虹连通图的最小色数.本文考察了一类特殊图n-方体,在k=2时,有rC2(Qn)=max{4,n},n≥2.

A path of a graph with colored edges is called rainbow if each of its edges has a different color.Graph G is called rainbow k-connectivity if there exist k internally disjoint u-v rainbow paths for every two distinct vertices u and v of G.The rainbow k-connectivity rCk（G） of G is defined as the minimum integer j for which there exists a j-edge-coloring of G such that G is a rainbow k-connectivity graph.In this paper,we consider a special graph n-cube and restrict k to 2.We show that for n≥2,rC2（Qn） = max{4,n}.