The routing number of an s-graph arises in the social-law approach to the problem of coordination of robots moving on a network. Onn and Sperber showed that the determination of the routing number of an sgraph is NP-complete and further posed the question of whether planar graphs always admit routing numbers that can be bounded in terms of their radius. In this paper, we introduce the routing number of the directed sgraph and show that it is equal to the perimeter (i. e. the length of a longest directed cycle) of the directed sgraph. This implies that the routing number of an undirected s-graph is equal to the minimum perimeter among all its orientations. Using this result ,we give a counter example to a question of Onn et al. and further show that the routing number of the product graph, a graph frequently used as a network, is equal to its radius and hence can be determined in polynomial time.%s-图的路由数源自于网格上行走的机器人的坐标规则问题.Onn和Sperner指出该问题是NP-完全的并进而提出这样一个问题:平面图上的路由数是否一定存在仅由半径为参数构成的界?本文引入有向s-图的路由数这一概念并证明该数等于其周长.这一结果表明无向s-图的路由数等于该图所有定向图的最小周长,同时也对上面的问题给出了一个反例.做为一个应用,我们证明乘积图的路由数等于其半径.
展开▼
