顶点最大度被限制的图的边转发指数(英文)  

On Edge-Forwarding Index of Graphs with Degree Restriction

作　　者：徐敏[1] 徐俊明[1] 侯新民[1] 

机构地区：[1]中国科学技术大学数学系

出　　处：《中国科学技术大学学报》2005年第6期732-737,共6页JUSTC

基　　金：Supported by NNSF of China(10271114 ,10301031 ,70221001 ,60373012) .

摘　　要：对于给定的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.

关 键 词：转发指数 点转发指数 边转发指数 路由选择 

分 类 号：O157.5[理学—数学] O157.9[理学—基础数学]