摘要
对于给定的n阶连通图G,一个路由选择R是指G中的n(n-1)条路集,其中每个有序点对都有路集中的一条路连接.图G关于R的边转发指数π( G,R)是R中路经过一条边的最大条数.图G的边转发指数π( G)是G关于任何路由选择R的边转发指数π( G,R)的最小值.符号πΔ,n表示所有顶点数为n,最大度至多为Δ的图中最小边转发指数.当n≥4p+1,且n [4p+(1/3)(2p-1) -1,6p]时,其中p≥1,确定了πn-2p,n的值.
For a given graph G of order n, a routingR is a set ofn（n- 1） elementary paths such that every ordered pair of vertices in G are connected by a path in the set. The edge-forwarding index ofGwith respect to a given routing R, denoted by π（G,R）, is the maximum number of paths in R passing through any edge e of G . The edge-forwarding index π（G） of G is the minimum of π（G,R） taken over all possible routings R of G. The parameter π△,n is the minimum of π（G） taken over all graphs G of order n with maximum degree at most △. We determine all values of πn-2p,n for n≥ 4p＋ 1 butn n∈/[4＋[1/3（2p- 1） ]- 1,6p] for any p≥1.
基金
Supported by NNSF of China(10271114 ,10301031 ,70221001 ,60373012) .
关键词
转发指数
点转发指数
边转发指数
路由选择
forwarding index
vertex-forwarding index
edge-forwarding index
routing
