World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Regular Connected Bipancyclic Spanning Subgraphs of Torus Networks

    It is well known that an n-dimensional torus T=T(k1,k2,,kn) is Hamiltonian. Then the torus T contains a spanning subgraph which is 2-regular and 2-connected. In this paper, we explore a strong property of torus networks. We prove that for any even integer k with 3k2n, the torus T(n3) contains a spanning subgraph which is k-regular, k-connected and bipancyclic; and if k is odd, the result holds when some ki is even.

    References

    • 1. J. A. Bondy and U. S. R. Murty, Graph Theory with Applications (Springer, New York, 1980). Google Scholar
    • 2. Y. M. Borse and S. R. Shaikh, On 4-regular 4-connected bipancyclic subgraph of hypercubes, Discrete Math. Algorithms Appl. 9 (2017). LinkGoogle Scholar
    • 3. Y. M. Borse and S. A. Kandekar, Decomposition of hypercubes into regular connected bipancyclic subgraphs, Discrete Math. Algorithms Appl. 7 (2015). LinkGoogle Scholar
    • 4. N. W. Chang and S. Y. Hsieh, Fault-tolerant bipancyclicity of faulty hypercubes under the generalized conditional-fault model, IEEE Trans. Comput. 59 (2011) 3400–3409. Google Scholar
    • 5. X. B. Chen, Panconnectivity and edge-pancyclicity of multidimensional torus, Discrete Appl. Math. 178 (2014) 33–45. CrossrefGoogle Scholar
    • 6. D. Djokovic, Distance preserving subgraphs of hypercubes, Journal of Combinatorial Theory, Series B 14 (1973) 263–267. CrossrefGoogle Scholar
    • 7. W. Duckworth, P. E. Dunne, A. M. Gibbons and M. Zito, Leafy spanning trees in hypercubes, Appl. Math. Lett. 14 (2001) 801–804. CrossrefGoogle Scholar
    • 8. J. S. Fu, Fault-tolerant cycle embedding in the hypercube, Parallel Comput. 29 (2003) 821–832. Crossref, ISIGoogle Scholar
    • 9. N. Graham and F. Harary, Some small sized spanning subgraphs of a hypercubes, Comput. Math. Appl. 34 (1997) 51–57. CrossrefGoogle Scholar
    • 10. S. Y. Hsieh and T. J. Lin, Panconnectivity and edge-pancyclicity of k-ary n-cube, Networks 54 (2009) 1–11. CrossrefGoogle Scholar
    • 11. F. Harary and M. Lewinter, Spanning subgraphs of a hypercubes II: Double starlike trees, Math. Comput. Model. 11 (1988) 216–217. CrossrefGoogle Scholar
    • 12. F. Harary and M. Lewinter, Spanning subgraphs of a hypercubes IV: Rooted trees, Math. Comput. Model. 17 (1993) 85–88. CrossrefGoogle Scholar
    • 13. S. Y. Hsieh and T. H. Shen, Edge-bipancyclicity of a hypercube with faulty vertices and edges, Discrete Appl. Math. 156 (2008) 1802–1808. CrossrefGoogle Scholar
    • 14. M. Kobeissi and M. Mollard, Spanning graphs of hypercubes: Starlike and double starlike trees, Discrete Math. 244 (2002) 231–239. CrossrefGoogle Scholar
    • 15. H. F. Law, Note spanning tree congestion of the hypercube, Discrete Math. 309 (2009) 6644–6648. Crossref, ISIGoogle Scholar
    • 16. J. Li, D. Liu and J. Yuan, Pancyclicity of k-ary n-cube networks with faulty vertices and edges, Discrete Appl. Math. 160 (2012) 231–238. Crossref, ISIGoogle Scholar
    • 17. J. Li, S. Wang, D. Liu and S. Lin, Edge-bipancyclicity of the k-ary n-cubes with faulty nodes and edges, Inform. Sci. 181 (2011) 2260–2267. Crossref, ISIGoogle Scholar
    • 18. T. J. Lin, S. Y. Hsieh and S. T. Juan, Embedding cycles and paths in product networks and their applications to multiprocessor systems, J. IEEE Trans. Parallel Distrib. Syst. 23 (2012) 1081–1089. Crossref, ISIGoogle Scholar
    • 19. S. Lin, S. Wang and C. Li, Panconnectivity and edge-pancyclicity of k-ary n-cubes with faulty elements, Discrete Appl. Math. 159 (2011) 212–223. CrossrefGoogle Scholar
    • 20. S. A. Mane and B. N. Waphare, Regular connected bipancyclic spanning subgraphs of hypercubes, Comput. Math. Appl. 62 (2011) 3551–3554. CrossrefGoogle Scholar
    • 21. M. Ramras, Regular subgraphs of hypercubes, Ars Combin. 52 (1999) 21–32. Google Scholar
    • 22. L. M. Shih, C. F. Chiang, L. H. Hsu and J. J. M. Tan, Strong Menger connectivity with conditional faults on the class of hypercube-like networks, Inform. Process. Lett. 106 (2008) 64–69. Crossref, ISIGoogle Scholar
    • 23. S. Spacapan, Connectivity of Cartesian product of graphs, Appl. Math. Lett. 21 (2008) 682–685. CrossrefGoogle Scholar
    • 24. I. A. Stewart and Y. Xiang, Embedding long paths in k-ary n-cubes with faulty nodes and links, IEEE Trans. Parallel Distrib. Syst. 19 (2008) 1071–1085. Google Scholar
    • 25. J. Yuan, A. Liu, H. Wu and J. Li, Panconnectivity of n-dimensional torus networks with faulty vertices and edges, Discrete Appl. Math. 161 (2013) 404–423. CrossrefGoogle Scholar