3正则3连通图的转发指数(英文)  

Forwarding indices of 3-connected and 3-regular graphs

作　　者：周敏杰[1] 徐敏[2] 徐俊明[1] 

机构地区：[1]中国科学技术大学数学系,安徽合肥230026 [2]北京师范大学数学科学学院,北京100875

出　　处：《中国科学技术大学学报》2008年第5期456-459,495,共5页JUSTC

基　　金：Supported by NNSF of China (No 10671191 and No 10301031)

摘　　要：n阶连通图G的路由选择R是由连接G的每个有向顶点对的n(n-1)条路组成.R经过G的每个顶点(每条边)的路的最大条数称为G关于R的点转发指数ξ(G,R)(边转发指数π(G,R)).对G的所有路由选择R,ξ(G,R)(π(G,R))的最小值称为G的点转发指数ξ(G)(边转发指数π(G)).对于k正则k连通图G,Fernandez de la Vega和Manoussakis[Discrete Applied Mathematics,1989,23(2) :103-123]证明ξ(G)≤(n-1)·┌(n-k-1)/k┐和π(G)≤n┌(n-k-1)/k┐,并且猜想ξ(G)≤┌(n-k)(n-k-1)/k┐.我们分别改进了ξ(G)≤(n-1) ┌(n-k-1)/k┐-(n-k-1)和π(G)≤n┌(n-k-1)/k┐-(n-k),并且证明了猜想对k=3的情形.A routing R of a connected graph G of order n is a collection of n （n--l） paths connecting every ordered pair of vertices of G. The vertex forwarding index ξ（G,R） （resp. the edge-forwarding index π（G,R）） of G with respect to R is defined to be the maximum number of paths of R passing through any vertex （resp. any edge） of G. The vertex-forwarding index ξ（G） （resp. the edge-forwarding index π（G）） of G is defined to be the minimum ξ（G,R） （resp. π（G,R）） over all routings R of G. For a h-regular k-connected graph G, it was shown by Fernandez de la Vega and Manoussakis [Discrete Applied Mathematics, 1989, 23（2）： 103-123]that ξ（G）≤（n-1）[（n-k-1）/k ] and π（G）≤n [（n-k-1）/k ], and conjectured that ξ（G）≤[（n-k） （n-k-1）/k]. The upper bounds as ξ（G）≤（n-1）[（n-k-1）/k]-（n-k-1） and π（G）≤n[（n-k-1）/k]-（n-k） were improved, and the conjecture for k=3 was proved.

关 键 词：转发指数 点转发指数 边转发指数 路由选择 k正则k连通图 

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