Abstract
Due to the application in reliable information transmission, parallel transmission and safe distribution of information, and parallel diagnosis algorithm for faulty servers, completely independent spanning trees (CISTs) play important roles in the interconnection networks. So far, researchers have obtained many results on CISTs in many specific interconnection networks, but the results of their line graphs are limited. Some data center networks are constructed based on the line graphs of interconnected networks, such as SWCube, BCDC, AQLCube, etc. Therefore, it is also necessary to study the construction of CISTs in line graphs. A torus network is one of the most popular interconnection networks. The line graph of a torus network is 6-regular, whether there exist 3-CISTs is an open question. In this article, we established the relationship between the completely independent spanning trees in the line graph and the edge division of the original graph. By dividing the edges of the torus network, we can construct three completely independent spanning trees in its line graph in some cases. Some simulation experiments are also implemented to verify the validity.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Araki, T.: Dirac’s condition for completely independent spanning trees. J. Graph Theory 77(3), 171–179 (2014)
Cheng, B., Fan, J., Li, X., Wang, G., Zhou, J., Han, Y.: Towards the independent spanning trees in the line graphs of interconnection networks. In: Vaidya, J., Li, J. (eds.) ICA3PP 2018. LNCS, vol. 11336, pp. 342–354. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-05057-3_27
Chen, G., Cheng, B., Fan, J., Wang, D., Wang, Y.: A secure distribution method for data. Patent No. ZL201910811364.0, 9 July 2021
Cheng, B., Wang, D., Fan, J.: Constructing completely independent spanning trees in crossed cubes. Discret. Appl. Math. 219, 100–109 (2017)
Dong, F., Yan, W.: Expression for the number of spanning trees of line graphs of arbitrary connected graphs. J. Graph Theory 85(1), 74–93 (2017)
Hasunuma, T.: Completely independent spanning trees in the underlying graph of a line digraph. Discret. Math. 234(1), 149–157 (2001)
Hasunuma, T.: Structural properties of subdivided-line graphs. J. Discrete Algorithms 31, 69–86 (2015)
Hasunuma, T.: Completely independent spanning trees in maximal planar graphs. In: Goos, G., Hartmanis, J., van Leeuwen, J., Kučera, L. (eds.) WG 2002. LNCS, vol. 2573, pp. 235–245. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-36379-3_21
Hasunuma, T., Morisaka, C.: Completely independent spanning trees in torus networks. Networks 60(1), 59–69 (2012)
Harvey, D.J., Wood, D.R.: Treewidth of the line graph of a complete graph. J. Graph Theory 79(1), 48–54 (2015)
Li, D., Wu, J.: On data center network architectures for interconnecting dual-port servers. IEEE Trans. Comput. 64(11), 3210–3222 (2015)
Li, H., He, W., Yang, W., Bai, Y.: A note on edge-disjoint Hamilton cycles in line graphs. Graphs Comb. 32, 741–744 (2016)
Pai, K.-J., Chang, J.-M.: Constructing two completely independent spanning trees in hypercube-variant networks. Theoret. Comput. Sci. 652, 28–37 (2016)
Pai, K.-J., Chang, R.-S., Chang, J.-M.: A protection routing with secure mechanism in Möbius cubes. J. Parallel Distrib. Comput. 140, 1–12 (2020)
Péterfalvi, F.: Two counterexamples on completely independent spanning trees. Discret. Math. 312(4), 808–810 (2012)
Su, G., Xu, L.: Topological indices of the line graph of subdivision graphs and their Schur-bounds. Appl. Math. Comput. 253, 395–401 (2015)
Tian, T., Xiong, L.: Traceability on 2-connected line graphs. Appl. Math. Comput. 321, 1339–1351 (2018)
Wang, Y., Du, H., Shen, X.: Topological properties and routing algorithm for semi-diagonal torus networks. J. China Univ. Posts Telecommun. 18(5), 64–70 (2011)
Acknowledgment
This work is supported by the National Natural Science Foundation of China (Nos. 62172291, U1905211), the Natural Science Foundation of the Jiangsu Higher Education Institutions of China (No. 18KJA520009), A Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions, and Future Network Scientific Research Fund Project (No. FNSRFP-2021-YB-39).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Bian, Q., Cheng, B., Fan, J., Pan, Z. (2022). Completely Independent Spanning Trees in the Line Graphs of Torus Networks. In: Lai, Y., Wang, T., Jiang, M., Xu, G., Liang, W., Castiglione, A. (eds) Algorithms and Architectures for Parallel Processing. ICA3PP 2021. Lecture Notes in Computer Science(), vol 13157. Springer, Cham. https://doi.org/10.1007/978-3-030-95391-1_34
Download citation
DOI: https://doi.org/10.1007/978-3-030-95391-1_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-95390-4
Online ISBN: 978-3-030-95391-1
eBook Packages: Computer ScienceComputer Science (R0)