n阶连通图G的路由选择R是由连接G的每个有向顶点对的n(n-1)条路组成.R经过G的每个顶点(每条边)的路的最大条数称为G关于R的点转发指数ξ(G,R)(边转发指数π(G,R)).对G的所有路由选择R,ξ(G,R)(π(G,R))的最小值称为G的点转发指数ξ(G)(...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的情形.展开更多
基金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的情形.
