Forwarding index of cube-connected cycles

作者：Yan, Jun; Xu, Jun-Ming^*; Yang, Chao

来源：Discrete Applied Mathematics, 2009, 157(1): 1-7.

DOI：10.1016/j.dam.2008.04.011

• Routings
• Forwarding index
• Cube-connected cycle

For a given connected graph G of order v, a routing R in G is a set of v(v - 1) elementary paths specified for every ordered pair of vertices in G. The vertex (resp. edge) for-warding index of G is the maximum number of paths in R passing through any vertex (resp. edge) in G. Shahrokhi and Szekely [F. Shahrokhi, L.A. Szekely, Constructing integral flows in symmetric networks with application to edge forwarding index problem, Discrete Applied Mathematics 108 (2001) 175-191] obtained an asymptotic formula for the edge forwarding index of n-dimensional cube-connected cycle CCCn as 5/4 n(2)2(n) (1 - o(1)). This paper determines the vertex forwarding index of CCCn as 7/4 n(2)2(n) (1 - o (1)) asymptotically.

• 出版日期2009-1-6
• 单位中国科学技术大学