Spanning tree congestion of rook's graphs
Spanning tree congestion of rook's graphs
复制标题
rook 图的生成树拥塞
DOI：
10.7151/dmgt.1577
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Y. Otachi
中科院分区：
文献类型：
--
作者：
Kyohei Kozawa;Y. Otachi
令 G 为连通图，T 为 G 的生成树。对于 e ∈ E(T )，e 的拥塞度是 G 中连接 T − e 的两个分量的边数。 T 的拥塞度是 T 中所有边上的最大拥塞度。 G 的生成树拥塞是其所有生成树上拥塞最小的。在本文中，我们确定了任意 m 和 n 的车图 Km Kn 的生成树拥塞情况。
Let G be a connected graph and T be a spanning tree of G. For e ∈ E(T ), the congestion of e is the number of edges in G joining the two components of T − e. The congestion of T is the maximum congestion over all edges in T . The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook’s graph Km Kn for any m and n.