×
Park, Jung-Heum; Ihm, Insung

Many-to-many two-disjoint path covers in cylindrical and toroidal grids. (English) Zbl 1311.05092

Discrete Appl. Math. 185, 168-191 (2015).
Summary: A many-to-many \(k\)-disjoint path cover of a graph joining two disjoint vertex sets \(S\) and \(T\) of equal size \(k\) is a set of \(k\) vertex-disjoint paths between \(S\) and \(T\) that altogether cover every vertex of the graph. The many-to-many \(k\)-disjoint path cover is classified as paired if each source in \(S\) is further required to be paired with a specific sink in \(T\), or unpaired otherwise. In this paper, we first establish a necessary and sufficient condition for a bipartite cylindrical grid to have a paired many-to-many \(2\)-disjoint path cover joining \(S\) and \(T\). Based on this characterization, we then prove that, provided the set \(S \cup T\) contains the equal numbers of vertices from different parts of the bipartition, the bipartite cylindrical grid always has an unpaired many-to-many \(2\)-disjoint path cover. Additionally, we show that such balanced vertex sets also guarantee the existence of a paired many-to-many \(2\)-disjoint path cover for any bipartite toroidal grid even if an arbitrary edge is removed.

Cited in 2 Reviews
Cited in 16 Documents

MSC:

05C38 Paths and cycles

Keywords:

disjoint path; path cover; path partition; square grid; lattice graph; cylindrical grid

Software:

IDonSquareGridR2
Cite Review PDF
Full Text: DOI

References:

[1] Arkin, E. M.; Fekete, S. P.; Islam, K.; Meijer, H.; Mitchell, J. S.B.; Núñez-Rodríguez, Y.; Polishchuk, V.; Rappaport, D.; Xiao, H., Not being (super)thin or solid is hard: a study of grid Hamiltonicity, Comput. Geom., 42, 6-7, 582-605 (2009) · Zbl 1193.05105
[2] Asdre, K.; Nikolopoulos, S. D., The 1-fixed-endpoint path cover problem is polynomial on interval graphs, Algorithmica, 58, 3, 679-710 (2010) · Zbl 1200.05212
[3] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer · Zbl 1134.05001
[4] Caha, R.; Koubek, V., Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets, J. Graph Theory, 51, 2, 137-169 (2006) · Zbl 1084.05041
[5] Chen, X.-B., Many-to-many disjoint paths in faulty hypercubes, Inform. Sci., 179, 18, 3110-3115 (2009) · Zbl 1193.68050
[6] Chen, X.-B., Paired many-to-many disjoint path covers of hypercubes with faulty edges, Inform. Process. Lett., 112, 3, 61-66 (2012) · Zbl 1233.68028
[7] Chen, X.-B., Paired many-to-many disjoint path covers of the hypercubes, Inform. Sci., 236, 218-223 (2013) · Zbl 1284.05274
[8] Chen, C. C.; Quimpo, N. F., On strongly Hamiltonian abelian group graphs, (Proc. Australian Conference on Combinatorial Mathematics. Proc. Australian Conference on Combinatorial Mathematics, Lecture Notes in Mathematics, vol. #884 (1980)), 23-34 · Zbl 0468.05055
[9] Chvátalová, J., Optimal labelling of a product of two paths, Discrete Math., 11, 3, 249-253 (1975) · Zbl 0299.05113
[10] Desjarlais, M.; Molina, R., Counting spanning trees in grid graphs, Congr. Numer., 145, 177-185 (2000) · Zbl 0976.05032
[11] Dvořák, T.; Gregor, P., Hamiltonian paths with prescribed edges in hypercubes, Discrete Math., 307, 1982-1998 (2007) · Zbl 1119.05060
[12] Dvořák, T.; Gregor, P., Partitions of faulty hypercubes into paths with prescribed endvertices, SIAM J. Discrete Math., 22, 4, 1448-1461 (2008) · Zbl 1187.05056
[13] Ellis, J.; Warren, R., Lower bounds on the pathwidth of some grid-like graphs, Discrete Appl. Math., 156, 5, 545-555 (2008) · Zbl 1137.05069
[15] Gordon, V. S.; Orlovich, Y. L.; Werner, F., Hamiltonian properties of triangular grid graphs, Discrete Math., 308, 24, 6166-6188 (2008) · Zbl 1158.05040
[16] Gregor, P.; Dvořák, T., Path partitions of hypercubes, Inform. Process. Lett., 108, 6, 402-406 (2008) · Zbl 1191.68037
[17] Itai, A.; Papadimitriou, C. H.; Szwarcfiters, J. L., Hamilton paths in grid graphs, SIAM J. Comput., 11, 4, 676-686 (1982) · Zbl 0506.05043
[18] Jo, S.; Park, J.-H.; Chwa, K. Y., Paired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphs, Inform. Sci., 242, 103-112 (2013) · Zbl 1337.68210
[19] Jo, S.; Park, J.-H.; Chwa, K. Y., Paired many-to-many disjoint path covers in faulty hypercubes, Theoret. Comput. Sci., 513, 1-24 (2013) · Zbl 1352.68195
[20] Junnila, V., New lower bound for 2-identifying code in the square grid, Discrete Appl. Math., 161, 13-14, 2042-2051 (2013) · Zbl 1286.05137
[21] Kim, S.-Y.; Lee, J.-H.; Park, J.-H., Disjoint path covers in recursive circulants \(G(2^m, 4)\) with faulty elements, Theoret. Comput. Sci., 412, 35, 4636-4649 (2011) · Zbl 1223.68083
[23] Kim, H.-D.; Park, J.-H., Many-to-many disjoint path covers in two-dimensional bipartite tori with a single vertex fault, J. KIISE, 39, 5, 333-342 (2012)
[24] Kim, S.-Y.; Park, J.-H., Paired many-to-many disjoint path covers in recursive circulants \(G(2^m, 4)\), IEEE Trans. Comput., 62, 12, 2468-2475 (2013) · Zbl 1372.68211
[25] Lai, P.-L.; Hsu, H.-C., The two-equal-disjoint path cover problem of matching composition network, Inform. Process. Lett., 107, 1, 18-23 (2008) · Zbl 1186.68025
[26] Laihonen, T., On robust identification in the square and king grids, Discrete Appl. Math., 154, 17, 2499-2510 (2006) · Zbl 1104.93019
[27] Liu, D.; Li, J., Many-to-many \(n\)-disjoint path covers in \(n\)-dimensional hypercubes, Inform. Process. Lett., 110, 14-15, 580-584 (2010) · Zbl 1234.68020
[30] Makino, K., 2-disjoint path covers in mesh-torus, Publ. Res. Inst. Math. Sci., Kyoto Univ., 1489, 181-187 (2006)
[31] Munkres, J. R., Topology (2000), Prentice-Hall, Inc. · Zbl 0107.17201
[32] Ntafos, S. C.; Hakimi, S. L., On path cover problems in digraphs and applications to program testing, IEEE Trans. Softw. Eng., 5, 5, 520-529 (1979) · Zbl 0412.68052
[33] Park, J.-H., Many-to-many disjoint path covers in two-dimensional tori, J. KIISE, 38, 1, 42-48 (2011)
[34] Park, J.-H.; Ihm, I., Single-source three-disjoint path covers in cubes of connected graphs, Inform. Process. Lett., 113, 14-16, 527-532 (2013) · Zbl 1285.05106
[35] Park, J.-H.; Ihm, I., Disjoint path covers in cubes of connected graphs, Discrete Math., 325, 65-73 (2014) · Zbl 1288.05145
[37] 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)
[38] Park, J.-H.; Kim, H.-C.; Lim, H.-S., Many-to-many disjoint path covers in the presence of faulty elements, IEEE Trans. Comput., 58, 4, 528-540 (2009) · Zbl 1368.68090
[39] Pikhurko, O.; Wojciechowski, J., Edge-bandwidth of grids and tori, Theoret. Comput. Sci., 369, 1-3, 35-43 (2006) · Zbl 1110.68113
[41] 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) · Zbl 1223.68086
[44] Zhang, S.; Wang, S., Many-to-many disjoint path covers in \(k\)-ary \(n\)-cubes, Theoret. Comput. Sci., 491, 103-118 (2013) · Zbl 1277.68040
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.