×

One-to-one disjoint path covers on \(k\)-ary \(n\)-cubes. (English) Zbl 1223.68086

Summary: The \(k\)-ary \(n\)-cube, \(Q^k_n\), is one of the most popular interconnection networks. Let \(n\geq 2\) and \(k\geq 3\). It is known that \(Q^k_n\) is a nonbipartite (resp. bipartite) graph when \(k\) is odd (resp. even). In this paper we prove that there exist \(r\) vertex disjoint paths \(\{P_{i}\mid 0\leq i\leq r - 1\}\) between any two distinct vertices \(u\) and \(v\) of \(Q^k_n\) when \(k\) is odd, and there exist \(r\) vertex disjoint paths \(\{R_{i}\mid 0\leq i\leq r - 1\}\) between any pair of vertices \(w\) and \(b\) from different partite sets of \(Q^k_n\) when \(k\) is even, such that \(\bigcup^{r-1}_{i=0}P_i\) or \(\bigcup^{r-1}_{i=0}R_i\) covers all vertices of \(Q^k_n\) for \(1\leq r\leq 2n\). In other words, we construct the one-to-one \(r\)-disjoint path cover of \(Q^k_n\) for any \(r\) with \(1\leq r\leq 2n\). The result is optimal since any vertex in \(Q^k_n\) has exactly \(2n\) neighbors.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68M10 Network design and communication in computer systems
05C65 Hypergraphs
Full Text: DOI

References:

[1] E. Anderson, J. Brooks, C. Grassl, S. Scott, Performance of the Cray T3E Multiprocessor, in: Proceedings of the 1997 ACM/IEEE Conference on Supercomputing, SC’97, 1997, pp. 1-17.; E. Anderson, J. Brooks, C. Grassl, S. Scott, Performance of the Cray T3E Multiprocessor, in: Proceedings of the 1997 ACM/IEEE Conference on Supercomputing, SC’97, 1997, pp. 1-17.
[2] Bondy, J. A.; Murty, U. S.R., Graph Theoery with Applications (1980), North-Holland: North-Holland New York · Zbl 1134.05001
[3] S. Borkar, et al. iWarp: an integrated solution to high-speed parallel computing, in: Proceedings of the 1988 ACM/IEEE Conference on Supercomputing, SC’88, 1988, pp. 330-339.; S. Borkar, et al. iWarp: an integrated solution to high-speed parallel computing, in: Proceedings of the 1988 ACM/IEEE Conference on Supercomputing, SC’88, 1988, pp. 330-339.
[4] Bose, B.; Broeg, B.; Kwon, Y.; Ashir, Y., Lee distance and topological properties of \(k\)-ary \(n\)-cubes, IEEE Transactions on Computers, 44, 1021-1030 (1995) · Zbl 1054.68510
[5] Chen, X.-B., Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs, Information Processing Letters, 110, 203-205 (2010) · Zbl 1197.05115
[6] Day, K.; Al-Ayyoub, A. E., Fault diameter of \(k\)-ary \(n\)-cube networks, IEEE Transactions on Parallel and Distributed Systems, 8, 903-907 (1997)
[7] Fink, J., Perfect matchings extend to hamilton cycles in hypercubes, Journal of Combinatorial Theory, Series B, 97, 1074-1076 (2007) · Zbl 1126.05080
[8] Fu, J.-S.; Chen, G.-H.; Duh, D.-R., Node-disjoint paths and related problems on hierarchical cubic networks, Networks, 40, 142-154 (2002) · Zbl 1064.68012
[9] Gomes, T.; Craveirinha, J.; Jorge, L., An effective algorithm for obtaining the minimal cost pair of disjoint paths with dual arc costs, Computers & Operations Research, 36, 1670-1682 (2009) · Zbl 1177.90071
[10] Harary, F.; Hayes, J. P.; Wu, H.-J., A survey of the theory of the hypercube graphs, Computer Mathematics with Applications, 15, 277-289 (1988) · Zbl 0645.05061
[11] Hsieh, S.-H.; Lin, T.-L., Panconnectivity and edge-pancyclicity of \(k\)-ary \(n\)-cubes, Networks, 54, 1-11 (2009) · Zbl 1205.05126
[12] Hsieh, S.-H.; Lin, T.-L.; Huang, H.-L., Panconnectivity and edge-pancyclicity of 3-ary \(n\)-cubes, The Journal of Supercomputing, 42, 225-233 (2007)
[13] Hsu, H.-C.; Lin, C.-K.; Huang, H.-M.; Hsu, L.-H., The spanning connectivity of the \((n, k)\)-star graphs, International Journal of Foundations of Computer Science, 17, 415-434 (2006) · Zbl 1103.68097
[14] Huang, C.-H., Strongly hamiltonian laceability of the even \(k\)-ary \(n\)-cube, Computers and Electrical Engineering, 35, 659-663 (2009) · Zbl 1187.68109
[15] Kao, S.-S.; Hsu, K.-M.; Hsu, L.-H., Cubic planar hamiltonian graphs of various types, Discrete Mathematics, 306, 1364-1389 (2006) · Zbl 1096.05033
[16] Kao, S.-S.; Hsu, H.-C.; Hsu, L.-H., Globally bi-\(3{}^\ast \)-connected graphs, Discrete Mathematics, 309, 1931-1946 (2009) · Zbl 1184.05076
[17] R.E. Kessler, J.L. Schwarzmeier, CRAY T3D: a new dimension for cray research, in: Proceedings of 38th Internationl Computer Conference, COMPCON’93, 1993, pp. 176-182.; R.E. Kessler, J.L. Schwarzmeier, CRAY T3D: a new dimension for cray research, in: Proceedings of 38th Internationl Computer Conference, COMPCON’93, 1993, pp. 176-182.
[18] Kobeissi, M.; Mollard, M., Disjoint cycles and spanning graphs of hypercubes, Discrete Mathematics, 288, 73-87 (2004) · Zbl 1057.05049
[19] Lin, C.-K.; Huang, H.-M.; Tan, Jimmy J. M.; Hsu, L.-H., On Spanning Connected Graphs, Discrete Mathematics, 308, 1330-1333 (2008) · Zbl 1134.05045
[20] Lin, C.-K.; Tan, Jimmy J. M.; Hsu, L.-H., On the spanning connectively and spanning laceability of hypercube-like networks, Theoretical Computer Science, 381, 218-229 (2007) · Zbl 1206.05060
[21] Liu, C.; Yarvis, M.; Conner, W. S.; Guo, X., Guaranteed on-demand discovery of node-disjoint paths in Ad Hoc networks, Computer Communications, 30, 2917-2930 (2007)
[22] M.D. Noakes, D.A. Wallach, W.J. Dally, The J-machine multicomputer: an architectural evaluation, in: Proceedings of the 20th Annual International Symposium on Computer Architecture, ISCA’93, 1993, pp. 224-235.; M.D. Noakes, D.A. Wallach, W.J. Dally, The J-machine multicomputer: an architectural evaluation, in: Proceedings of the 20th Annual International Symposium on Computer Architecture, ISCA’93, 1993, pp. 224-235.
[23] Ntafos, S. C.; Hakimi, S. L., On path cover problems in digraphs and applications to program testing, IEEE Transactions on Software Engineering, 5, 520-529 (1979) · Zbl 0412.68052
[24] Ore, O., Hamiltonian connected graphs, Journal de Mathématiques Pures et Appliquées, 42, 21-27 (1963) · Zbl 0106.37103
[25] Park, J.-H.; Kim, H.-C.; Lim, H.-S., Many-to-many path covers in the presence of faulty elements, IEEE Transactions on Computers, 58, 528-540 (2009) · Zbl 1368.68090
[26] Stewart, I. A.; Xiang, Y., Bipanconnectivity and bipancyclicity in \(k\)-ary \(n\)-cubes, IEEE Transactions on Parallel and Distributed Systems, 20, 25-33 (2009)
[27] Stewart, I. A.; Xiang, Y., Embedding long Paths in \(k\)-ary \(n\)-cubes with faulty nodes and links, IEEE Transactions on Parallel and Distributed Systems, 19, 1071-1085 (2008)
[28] Sun, C.-M.; Lin, C.-K.; Huang, H.-M.; Hsu, L.-H., Mutually independent hamiltonian paths and cycles in hypercubes, Journal of Interconnection Networks, 7, 235-255 (2006)
[29] Tsai, C.-H., Cycles embedding in hypercubes with node failures, Information Processing Letters, 102, 242-246 (2007) · Zbl 1184.68054
[30] Tsai, C.-H., Linear array and ring embeddings in conditional faulty hypercubes, Theoretical Computer Science, 314, 431-443 (2004) · Zbl 1072.68082
[31] D. Wang, T. An, M. Pan, K. Wang, S. Qu, Hamiltonian-like properies of \(kn\); D. Wang, T. An, M. Pan, K. Wang, S. Qu, Hamiltonian-like properies of \(kn\)
[32] Wu, R.-Y.; Chen, G.-H.; Kuo, Y.-L.; Chang, G. J., Node-disjoint paths in hierarchical hypercube networks, Information Sciences, 177, 4200-4207 (2007) · Zbl 1126.68016
[33] Yang, M.-C.; Tan, Jimmy J. M.; Hsu, L.-H., Hamiltonian circuit and linear array embeddings in faulty \(k\)-ary \(n\)-cubes, Journal of Parallel and Distributed Computing, 67, 362-368 (2007) · Zbl 1115.68032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.