Independent Spanning Trees on Special BC Networks

Abstract:

There is a well-known conjecture on independent spanning trees (ISTs) on graphs: For any n-connected graph G with n≥1, there are n ISTs rooted at an arbitrary node on G. It still remains open for n≥5. We propose an integrated algorithm to construct n ISTs rooted at any node similar to 0 or 10^n-1 on n-dimensional HCH cube for n≥1 and give the simulations of ISTs on several special BC networks, such as HCH cubes, crossed cubes, Möbius cubes, twisted cubes, etc.

• Periodical: Applied Mechanics and Materials (Volumes 263-266)
• Pages: 3301-3305
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.263-266.3301
• Online since: December 2012
• Authors: Bao Lei Cheng, Jian Xi Fan, Ji Wen Yang, Yan Wang, Shu Kui Zhang
• Keywords: BC Network, HCH Cube, Independent Spanning Tree, Node-Disjoint Path

References

[1] F. Bao, Y. Funyu, Y. Hamada, and Y. Igarashi: IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, vol. E81-A, pp.796-806, 1998.

[2] Y.-S. Chen, C.-Y. Chiang, and C.-Y. Chen: J. Syst. Architect., vol. 50, no. 9, pp.575-589, 2004.

[3] Y.-C. Tseng, S.-Y. Wang, and C.-W. Ho: IEEE Trans. Parallel and Distributed Systems, vol. 10, no. 1, pp.44-61, 1999.

[4] A. Itai and M. Rodeh: Inform. Comput., vol. 79, no.1, pp.43-59, 1988.

[5] A. Zehavi and A. Itai: J. Graph Theory, vol. 13, no. 2, pp.175-188, 1989.

[6] J. Cheriyan and S. N. Maheshwari: J. Algorithms, vol. 9, no. 4, pp.507-537, 1988.

[7] S. Curran, O. Lee, and X. Yu: SIAM J. Comput., vol. 35, no. 5, pp.1023-1058, 2006.

[8] S.-M. Tang, Y.-L. Wang, and Y.-H. Leu: J. Information Science and Engineering, vol. 20, no.1, pp.143-155, 2004.

[9] Y.-J. Liu, W. Y. Chou, J. K. Lan, and C. Chen: Theoretical Computer Science, vol. 412, no. 22, pp.2237-2252, 2011.

[10] Y. Wang, J. Fan, G. Zhou, and X. Jia: J. Parallel and Distributed Computing, vol. 72, no. 1, 58-69, 2012.

[11] J.-S. Yang, J.-M. Chang, and H.-C. Chan, Independent spanning trees on folded hypercubes, in: Proceedings of 10th International Symposium on Pervasive Systems, Algorithms, and Networks(I-SPAN 2009), Kaohsiung, Taiwan, pp.73-83, 2009.

DOI: 10.1109/i-span.2009.55

[12] J. Fan and L. He(In Chinese): Chinese J. Computers, vol. 26, no. 1, pp.84-90, 2003.

[13] J. Fan, X. Jia, X. Liu, S. Zhang, and J. Yu: Information Sciences, vol. 181, no. 11, pp.2303-2315, 2011.

[14] K. Efe: IEEE Trans. Parallel and Distributed Systems, vol. 3, no. 5, pp.513-524, 1992.

[15] X. Liu, J. Fan, X. Zong, and C. X(In Chinese): vol. 32, no. 15, pp.83-86, 2005.

[16] X. Yang, L. Wang, L. Yang: Inf. Process. Lett. vol. 112, no. 4, pp.129-134, 2012.

[17] H. Gu, J. Zhang, K. Wang, C. Wang, rHALB: A new load-balanced routing algorithm for k-ary n-cube networks, APPT 2007, pp.392-401, 2007.

DOI: 10.1007/978-3-540-76837-1_43

[18] B. Cheng, J. Fan, J. Yang, and Y. Han. An algorithm to construct independent spanning trees on crossed cubes. Proc. 2nd Int' l Conf. Information Sciences Engineering. 2010, 2: 961-964.

DOI: 10.1109/icise.2010.5691221

[19] B. Cheng, J. Fan, X. Jia, S. Zhang, B. Chen: The Computer Journal 2012.

DOI: 10.1093/comjnl/bxs123