学 术 报 告
（运筹控制组）
报告题目：Constructing independent spanning trees for hypercubes and locally twisted cubes
报告人：陈秋媛（台湾交通大学应用数学系教授兼系主任）
时间：2010年10月23日（周六）上午10:00-10:50；
地点：闵行校区数学楼102会议室
摘要：The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages such as the increase of fault-tolerance and bandwidth. Thus the designs of multiple ISTs in several classes of networks have been widely investigated. In 1989, Zehavi and Itai stated two versions of the $n$ independent spanning trees conjecture. The vertex (edge) conjecture is that any $n$-connected ($n$-edge-connected) graph has $n$ vertex-ISTs (edge-ISTs) rooted at an arbitrary vertex $r$. In 1992, Khuller and Schieber proved that the vertex conjecture implies the edge conjecture. Recently, Hsieh and Tu proposed an algorithm to construct $n$ edge-ISTs rooted at vertex 0 for an $n$-dimensional locally twisted cube $LTQ_n$, which is a variant of the hypercube. Since ${LTQ}_n$ is it not vertex-transitive, Hsieh and Tu's result does not solve the edge conjecture for the locally twisted cube. In this work, we confirm the vertex conjecture (and hence also the edge conjecture) for the locally twisted cube by proposing an algorithm to construct $n$ vertex-ISTs rooted at any vertex for the $LTQ_n$. We also confirm the vertex conjecture (and hence also the edge conjecture) for the hypercube