Abstract
We propose a new definition to describe the characteristics of a graph. A graph G is strong \(k^*\)-connected if there is a \(r^{*}\)-container between any two distinct vertices u and v of G with \(r \le \min \{ deg(u), deg(v), k\}\). The strong spanning connectivity of graph G, \(s\kappa (G)\), is the maximal value of G satisfies (a) G is strong \(s\kappa (G)^{*}\)-connected and (b) \(s\kappa (G) \le \varDelta (G)\) where \(\varDelta (G)\) is the maximal degree of G. Similarly, strong spanning laceability of bipartite graph G, is denoted by \(s\kappa ^{L}(G)\). A mesh with m rows and n columns is denoted by \(M_{m,n}\). Let m be any even integer and n be any integer. In this paper, we show that \(s\kappa ^{L}(M_{m,n})=3\) if \(\min \{m, n\} \ge 4\).
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
Asdre, K., Nikolopoulos, S.D.: The 1-fixed-end point path cover problem is polynomial on interval graphs. Algorithmica 58(3), 679–710 (2010)
Chang, C.-H., Lin, C.-K., Huang, H.-M., Hsu, L.-H.: The super laceability of the hypercubes. Inf. Process. Lett. 92, 15–21 (2004)
Day, K., Al-Ayyoub, A.E.: Fault diameter of \(k\)-ary \(n\)-cube networks. IEEE Trans. Parallel Distrib. Syst. 8(9), 903–907 (1997)
Hsu, L.-H., Lin, C.-K.: Graph theory and interconnection networks. CRC Press, New York (2008)
Hsu, D.F.: On container width and length in graphs, groups, and networks. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E77–A(4), 668–680 (1994)
Itali, A., Papadimitrion, C.H., Czwacfiter, J.L.: Hamiltonian paths in grid graphs. SIAM J. Comput. 11(4), 676–686 (1982)
Lai, C.-N.: Optimal construction of all shortest node-disjoint paths in hypercubes with applications. IEEE Trans. Parallel Distrib. Syst. 23(6), 1129–1134 (2012)
Lai, C.-N.: Two conditions for reducing the maximal length of node-disjoint paths in hypercubes. Theoret. Comput. Sci. 418, 82–91 (2012)
Lai, C.-N.: An efficient construction of one-to-many node-disjoint paths in folded hypercubes. J. Parallel Distrib. Syst. 74(4), 2310–2316 (2014)
Lai, C.-N.: Constructing all shortest node-disjoint paths in torus networks. J. Parallel Distrib. Syst. 75, 123–132 (2015)
Li, J., Liu, D., Yang, Y., Yuan, J.: One-to-one disjoint path covers on multi-dimensional tori. Int. J. Comput. Math. 92(6), 1114–1123 (2014)
Lin, C.-K., Huang, H.-M., Hsu, L.-H.: The super connectivity of the pancake graphs and the super laceability of the star graphs. Theoret. Comput. Sci. 339(2–3), 257–271 (2005)
Lin, C.-K., Tan, J.J.M., Hsu, D.F., Hsu, L.-H.: On the spanning connectivity and spanning laceability of hypercube-like networks. Theoret. Comput. Sci. 381(1–3), 218–229 (2007)
Liu, C., Yarvis, M., Conner, W.S., Guo, X.: Guaranteed on-demand discovery of node-disjoint paths in Ad hoc networks. Comput. Commun. 30(14–15), 2917–2930 (2007)
McHugh, J.A.M.: Algorithmic graph theory. Prentice-Hall, Englewood Cliffs (1990)
Ntafos, S.C., Hakimi, S.L.: On path cover problems in digraphs and applications to program testing. IEEE Trans. Software Eng. 5(5), 520–529 (1979)
Park, J.-H., Kim, H.-C., Lim, H.-S.: Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements. IEEE Trans. Parallel Distrib. Syst. 17(3), 227–240 (2006)
Park, J.-H., Ihm, I.: Single-source three-disjoint path covers in cubes of connected graphs. Inf. Process. Lett. 113(14–16), 527–532 (2013)
Shih, Y.-K., Kao, S.-S.: One-to-one disjoint path covers on \(k\)-ary \(n\)-cubes. Theoret. Comput. Sci. 412(35), 4513–4530 (2011)
Wu, R.-Y., Chen, G.-H., Kuo, Y.-L., Chang, G.J.: Node-disjoint paths in hierarchical hypercube networks. Inf. Sci. 177(19), 4200–4207 (2007)
Xiang, Y., Stewart, I.A.: One-to-many node-disjoint paths in (\(n\), \(k\))-star graphs. Discrete Appl. Math. 158, 62–70 (2010)
Acknowledgments
This work is supported by National Natural Science Foundation of China (No.61572337, No.61572340).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Du, M., Fan, J., Han, Y., Lin, CK. (2015). One-to-One Disjoint Path Covers on Mesh. In: Wang, G., Zomaya, A., Martinez, G., Li, K. (eds) Algorithms and Architectures for Parallel Processing. ICA3PP 2015. Lecture Notes in Computer Science(), vol 9529. Springer, Cham. https://doi.org/10.1007/978-3-319-27122-4_29
Download citation
DOI: https://doi.org/10.1007/978-3-319-27122-4_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-27121-7
Online ISBN: 978-3-319-27122-4
eBook Packages: Computer ScienceComputer Science (R0)