Closed trail decompositions on grid graphs

Dombi, Erzsébet

doi:10.1515/puma-2015-0040

Abstract

Let G = G(n, m) be a rectangular solid grid graph and 𝒜(G) be a minimum length Eulerian augmentation of G. Let l₀, . . ., l_t ∈ ℕ such that ∑^t_i₌₀ l_i = |E(𝒜(G)|, where 2(n + m) ≤ l_i = 2k_i. In this paper, we exhibit a constructive procedure providing an edge-disjoint decomposition of 𝒜 (G) into closed trails T₀, . . ., T_t such that |E(T_i)| = l_i.

References

[1] P.N. Balister: Packing circuit into KN . Combin. Probab. Comput. 10 (2001), 463–499. Zbl 1113.05309, MR1869841, DOI 10.1017/s0963548301004771
Open DOI Search in Google Scholar Back to article
[2] E. J. Billington, N. J. Cavenagh: Decomposing complete tripartite graphs into closed trails of arbitrary lengths. Czech. Math. J. 57 (2007), 523–551. Zbl 1174.05100, MR2337613, DOI 10.1007/s10587-007-0096-y
Open DOI Search in Google Scholar Back to article
[3] A. Burgess, M. Šajna: Closed trail decompositions of complete equipartite graphs. J. Combin. Des. 17 (2009), 374–403. Zbl 1222.05209, MR2547673, DOI 10.1002/jcd.20228
Open DOI Search in Google Scholar Back to article
[4] S. Cichacz, M. Horňak: Decomposition of bipartite graphs into closed trails. Czech. Math. J. 59 (2009), 129–144. Zbl 1224.05402, MR2486620, DOI: 10.1007/s10587-009-0009-3
Open DOI Search in Google Scholar Back to article
[5] S. Cichacz, J.Przybyło, M. Woźniak: Decomposition of pseudographs into closed trails of even sizes. Discrete Math. (309) (2009), 4903–4908. Zbl 1218.05123, MR2531635, DOI 10.1016/j.disc.2008.04.024
Open DOI Search in Google Scholar Back to article
[6] M. Horňak, Z. Kocková: On complete tripartite graphs arbitrarily decomposable into closed trails. Tatra Mt. Math. Publ. 36 (2007), 71–107. Zbl 1174.05073, MR2378742
Search in Google Scholar Back to article
[7] M. Horňak, M. Woźniak: Decomposition of complete bipartite even graphs into closed trails. Czech. Math. J. 53 (2003), 127–134. Zbl 1010.05054, MR1962004, DOI: 10.1023/A:1022931710349
Open DOI Search in Google Scholar Back to article
[8] C. H. Papadimitriou, M. Sideri: The bisection width of grid graphs. Math. Systems Theory 29 (1996), 97-110. Zbl 0839.68976, MR168793, DOI: 10.1007/BF01305310
Open DOI Search in Google Scholar Back to article
[9] P. Paulraja, S. Sampath Kumar: Closed trail decompositions of come classes of regular graphs. Discrete Math. 312 (2012), 1353–1366. Zbl 1237.05169, MR28859918, DOI: 10.1016/j.disc.2011.12.015
Open DOI Search in Google Scholar Back to article
[10] H. Shi, P. Gader, H. Li: Parallel mesh algorithms for grid graph shortest paths with application to separation to touching chromosomes. J. of Supercomput. 12, (1998) 69–83. Zbl 0896.68074, DOI: 10.1023/A:1007929410673
Open DOI Search in Google Scholar Back to article
[11] B. R. Smith: Decomposing complete equipartite graphs into closed trails of length k. Graphs Combin. 26 (2010), 133–140. Zbl 1231.05218, MR2606624, DOI 10.1007/s00373-010-0899-8
Open DOI Search in Google Scholar Back to article

Closed trail decompositions on grid graphs

Abstract

Paradigm

My account