3正则3连通图的转发指数

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的情形.

Forwarding indices of 3-connected and 3-regular graphs

A routing R of a connected graph G of order n is a collection of n (n-1) 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 k-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-l) and π(G)≤n(n-k-1)/k]-(n-k) were improved, and the conjecture for k=3 was proved.