Closed trail decompositions on grid graphs

Dombi, Erzsébet (2021) Closed trail decompositions on grid graphs. Pure Mathematics and Applications, 28 (1). pp. 1-14. ISSN 1218-4586 (

[thumbnail of Dombi-PMA-2021-Closed-trail-decompositions-on-grid-graphs]
Text. Filename: Dombi_PMA_2021_Closed_trail_decompositions_on_grid_graphs.pdf
Final Published Version
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (183kB)| Preview


Let G = G(n,m) be a rectangular solid grid graph and A(G) be a minimum length Eulerian augmentation of G. Let l0, . . . , lt ∈ N such that Σt i=0 li = |E(A(G)|, where 2(n + m) ≤ li = 2ki. In this paper, we exhibit a constructive procedure providing an edge-disjoint decomposition of A(G) into closed trails T0, . . . , Tt such that |E(Ti)| = li.