Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Constructing tri-CISTs in shuffle-cubes

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

Let \({\mathcal {T}}=\{T_1,T_2,\ldots ,T_k\}\) be a set of \(k\geqslant 2\) spanning trees in a graph G. The k spanning trees are called completely independent spanning trees (CISTs for short) if the paths joining every pair of vertices x and y in any two trees have neither vertex nor edge in common except for x and y. Particularly, \({\mathcal {T}}\) is called a dual-CIST (resp. tri-CIST) provided \(k=2\) (resp. \(k=3\)). From an algorithmic point of view, the problem of finding a dual-CIST in a given graph is known to be NP-hard. For data transmission applications in reliable networks, the existence of a dual-CIST can provide a configuration of fault-tolerant routing called protection routing. The presence of a tri-CIST can enhance the dependability of transmission and carry out secure message distribution for confidentiality. Recently, the construction of a dual-CIST has been proposed in a shuffle-cube \(SQ_n\), which is an innovative hypercube-variant network that possesses both short diameter and connectivity advantages. This paper uses the CIST-partition technique to construct a tri-CIST of \(SQ_6\), and shows that the diameters of three CISTs are 22, 22, and 13. Then, by the hierarchical structure of \(SQ_n\), we propose a recursive algorithm for constructing a tri-CIST for high-dimensional shuffle-cubes. When \(n\geqslant 10\), the diameters of \(T_i\), \(i=1,2,3\), we constructed for \(SQ_n\) are as follows: \(2n+11\), \(2n+9\), and \(2n+1\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Notes

  1. The searching algorithm is implemented by a C program running in a computer with 3.40 GHz Intel® Core™ i7-3770 CPU and 8 GB RAM under the Linux operating system, which takes about 105 h for searching a feasible tri-CIST partition of \(SQ_6\).

References

  • Anantapantula S, Melekian C, Cheng E (2018) Matching preclusion for the shuffle-cubes. Parallel Process Lett 28(3):1850012

    Article  MathSciNet  MATH  Google Scholar 

  • Araki T (2014) Dirac’s condition for completely independent spanning trees. J Graph Theory 77(3):171–179

    Article  MathSciNet  MATH  Google Scholar 

  • Chang H-Y, Wang H-L, Yang J-S, Chang J-M (2015) A note on the degree condition of completely independent spanning trees. IEICE Trans Fundam E98–A(10):2191–2193

    Article  Google Scholar 

  • Chang J-M, Chang H-Y, Wang H-L, Pai K-J, Yang J-S (2017) Completely independent spanning trees on 4-regular chordal rings. IEICE Trans Fundam E100–A(9):1932–1935

    Article  Google Scholar 

  • Chang Y-H, Pai K-J, Hsu C-C, Yang J-S, Chang J-M (2021) Constructing dual-CISTs of folded divide-and-swap cubes. Theor Comput Sci 856:75–87

    Article  MathSciNet  MATH  Google Scholar 

  • Chen G, Cheng B, Wang D (2021a) Constructing completely independent spanning trees in data center network based on augmented cube. IEEE Trans Parallel Distrib Syst 32(3):665–673

  • Chen Y-H, Tang S-M, Pai K-J, Chang J-M (2021b) Constructing dual-CISTs with short diameters using a generic adjustment scheme on bicubes. Theor Comput Sci 878–879:102–112

  • Cheng B, Wang D, Fan J (2017) Constructing completely independent spanning trees in crossed cubes. Discrete Appl Math 219:100–109

    Article  MathSciNet  MATH  Google Scholar 

  • Darties B, Gastineau N, Togni O (2017) Completely independent spanning trees in some regular graphs. Discrete Appl Math 217(2):163–174

    Article  MathSciNet  MATH  Google Scholar 

  • Ding T, Li P, Xu M (2020) The component (edge) connectivity of shuffle-cubes. Theor Comput Sci 835:108–119

    Article  MathSciNet  MATH  Google Scholar 

  • Fan J, Lin X (2005) The \(t/k\)-diagnosability of the BC graphs. IEEE Trans Comput 54(2):176–184

    Article  Google Scholar 

  • Fan G, Hong Y, Liu Q (2014) Ore’s condition for completely independent spanning trees. Discrete Appl Math 177:95–100

    Article  MathSciNet  MATH  Google Scholar 

  • Hasunuma T (2001) Completely independent spanning trees in the underlying graph of a line digraph. Discrete Math 234(1–3):149–157

    Article  MathSciNet  MATH  Google Scholar 

  • Hasunuma T (2002) Completely independent spanning trees in maximal planar graphs. In: Proceedings of the 28th graph-theoretic concepts computer science (WG2002), lecture notes in computer science, vol 2573, Springer, Cham, pp 235–245

  • Hasunuma T (2016) Minimum degree conditions and optimal graphs for completely independent spanning trees. In: Proceedings of 26th international workshop on combinatorial algorithms (IWOCA 2016), lecture notes in computer science, vol 9538, Springer, Cham, pp 260–273

  • Hasunuma T, Morisaka C (2012) Completely independent spanning trees in torus networks. Networks 60(1):59–69

    Article  MathSciNet  MATH  Google Scholar 

  • Hong X, Liu Q (2016) Degree condition for completely independent spanning trees. Inf Process Lett 116(10):644–648

    Article  MathSciNet  MATH  Google Scholar 

  • Hong X, Zhang H (2020) A Hamilton sufficient condition for completely independent spanning tree. Discrete Appl Math 279:183–187

    Article  MathSciNet  MATH  Google Scholar 

  • Kwong K-W, Gao L, Guérin R, Zhang Z-L (2011) On the feasibility and efficacy of protection routing in IP networks. IEEE/ACM Trans Netw 19(5):1543–1556

    Article  Google Scholar 

  • Li T-K, Tan JM, Hsu L-H, Sung TY (2001) The shuffle-cubes and their generalization. Inf Process Lett 77(1):35–41

    Article  MathSciNet  MATH  Google Scholar 

  • Li T-K, Tan JM, Hsu L-H (2002) Fault hamiltonicity of the shuffle-cubes. In: Proceedings of 19th workshop on combinatorial mathematics and computation theory, Kaohsiung, Taiwan, pp 110–119

  • Li J, Lin L, Huang Y, Yu H, Chen R (2019) The \((t, k)\)-diagnosability of shuffle-cubes under PMC model. Int J Comput Math Comput Syst Theor 4(2):111–126

    Article  MathSciNet  Google Scholar 

  • Lin L, Xu L, Zhou S (2015) Conditional diagnosability and strong diagnosability of shuffle-cubes under the comparison model. Int J Comput Math 92(2):230–249

    Article  MathSciNet  MATH  Google Scholar 

  • Mane SA, Kandekar SA, Waphare BN (2018) Constructing spanning trees in augmented cubes. J Parallel Distrib Comput 122:188–194

    Article  Google Scholar 

  • Matsushita M, Otachi Y, Araki T (2015) Completely independent spanning trees in (partial) \(k\)-trees. Discuss Math Graph Theory 35(3):427–437

    Article  MathSciNet  MATH  Google Scholar 

  • Pai K-J, Chang J-M (2016) Constructing two completely independent spanning trees in hypercube-variant networks. Theor Comput Sci 652:28–37

    Article  MathSciNet  MATH  Google Scholar 

  • Pai K-J, Chang J-M (2019a) Improving the diameters of completely independent spanning trees in locally twisted cubes. Inf Process Lett 141:22–24

  • Pai K-J, Chang J-M (2019b) Dual-CISTs: configuring a protection routing on some Cayley networks. IEEE/ACM Trans Netw 27(3):1112–1123

  • Pai K-J, Yang J-S, Yao S-C, Tang S-M, Chang J-M (2014) Completely independent spanning trees on some interconnection networks. IEICE Trans Inf Syst E97–D(9):2514–2517

    Article  Google Scholar 

  • Pai K-J, Chang R-S, Wu R-Y, Chang J-M (2019) A two-stages tree-searching algorithm for finding three completely independent spanning trees. Theor Comput Sci 784:65–74

    Article  MathSciNet  MATH  Google Scholar 

  • Pai K-J, Chang R-S, Chang J-M (2020a) A protection routing with secure mechanism in Möbius cubes. J Parallel Distrib Comput 140:1–12

  • Pai K-J, Chang R-S, Chang J-M (2020b) A well-equalized 3-CIST partition of alternating group graphs. Inf Process Lett 155:105874

  • Pai K-J, Chang R-S, Wu R-Y, Chang J-M (2020c) Three completely independent spanning trees of crossed cubes with application to secure-potection routing. Inf Sci 541:516–530

  • Pai K-J, Chang R-S, Chang J-M (2021) Constructing dual-CISTs of pancake graphs and performance assessment of protection routings on some Cayley networks. J Supercomput 77(1):990–1014

    Article  Google Scholar 

  • Péterfalvi F (2012) Two counterexamples on completely independent spanning trees. Discrete Math 312(4):808–810

    Article  MathSciNet  MATH  Google Scholar 

  • Qin X-W, Hao R-X (2021) Reliability analysis based on the dual-CIST in shuffle-cubes. Appl Math Comput 397:125900

    MathSciNet  MATH  Google Scholar 

  • Qin X-W, Hao R-X, Chang J-M (2019) Constructing dual-CISTs of DCell data center networks. Appl Math Comput 362:124546

    MathSciNet  MATH  Google Scholar 

  • Qin X-W, Hao R-X, Chang J-M (2020a) The existence of completely independent spanning trees for some compound graphs. IEEE Trans Parallel Distrib Syst 31(1):201–210

  • Qin X-W, Hao R-X, Pai K-J, Chang J-M (2020b) Comments on A Hamilton sufficient condition for completely independent spanning tree. Discrete Appl Math 283:730–733

  • Tapolcai J (2013) Sufficient conditions for protection routing in IP networks. Optim Lett 7(4):723–730

    Article  MathSciNet  MATH  Google Scholar 

  • Wang Y, Wang S, Wang Z (2017) The 1-good-neighbor diagnosability of shuffle-cubes. Int J New Technol Res 3(8):66–73

    Google Scholar 

  • Xu J-M, Xu M, Zhu Q (2005) The super connectivity of shuffle-cubes. Inf Process Lett 96(4):123–127

    Article  MathSciNet  MATH  Google Scholar 

  • Xu M, Hu X, Shang S (2010) The conditional diagnosability of shuffle-cubes. J Syst Sci Complex 23(1):81–90

    Article  MathSciNet  MATH  Google Scholar 

  • Yang Y-X, Pai K-J, Chang R-S, Chang J-M (2019) Constructing two completely independent spanning trees in balanced hypercubes. IEICE Tran Inf Syst E102–D(12):2409–2412

    Article  Google Scholar 

Download references

Acknowledgements

This research was supported by the Ministry of Science and Technology of Taiwan under Grant MOST110-2221-E-141-004 (J.-M. Chang).

Author information

Authors and Affiliations

  1. Institute of Information and Decision Sciences, National Taipei University of Business, Taipei, 10051, Taiwan

    Yu-Han Chen, Hsin-Jung Lin & Jou-Ming Chang

  2. Department of Industrial Engineering and Management, Ming Chi University of Technology, New Taipei City, 243303, Taiwan

    Kung-Jui Pai

Authors
  1. Yu-Han Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kung-Jui Pai
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hsin-Jung Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jou-Ming Chang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jou-Ming Chang.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chen, YH., Pai, KJ., Lin, HJ. et al. Constructing tri-CISTs in shuffle-cubes. J Comb Optim 44, 3194–3211 (2022). https://doi.org/10.1007/s10878-022-00863-0

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-022-00863-0

Keywords

Search

Navigation