<abstract xmlns="http://www.w3.org/1999/xhtml">

Let <italic>G</italic> = <italic>G</italic>(<italic>n, m</italic>) be a rectangular solid grid graph and 𝒜(<italic>G</italic>) be a minimum length Eulerian augmentation of <italic>G</italic>. Let <italic>l</italic>0, . . ., <italic>lt</italic> ∈ ℕ such that ∑t<italic>i</italic>=0 <italic>li</italic> = <italic>|E</italic>(𝒜(<italic>G</italic>)<italic>|,</italic> where 2(<italic>n</italic> + <italic>m</italic>) <italic>≤ li</italic> = 2<italic>ki</italic>. In this paper, we exhibit a constructive procedure providing an edge-disjoint decomposition of 𝒜 (<italic>G</italic>) into closed trails <italic>T</italic>0, . . ., <italic>Tt</italic> such that <italic>|E</italic>(<italic>Ti</italic>)<italic>|</italic> = <italic>li</italic>.
</abstract>

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

Closed trail decompositions on grid graphs

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Closed trail decompositions on grid graphs"}

Let G = G(n, m) be a rectangular solid grid graph and 𝒜(G) be a minimum length Eulerian augmentation of G. Let l0, . . ., lt ∈ ℕ such that ∑ti=0 li =...

Closed trail decompositions on grid graphs

Publié en ligne: 17 août 2022

Pages: 71 - 84

Reçu: 05 févr. 2021

DOI: https://doi.org/10.1515/puma-2015-0040

Mots clés
closed trail, graph decomposition, grid graphs

© 2022 Erzsébet Dombi, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Closed trail decompositions on grid graphs

Publié en ligne: 17 août 2022

Pages: 71 - 84

Reçu: 05 févr. 2021

DOI: https://doi.org/10.1515/puma-2015-0040

Mots clésclosed trail, graph decomposition, grid graphs

© 2022 Erzsébet Dombi, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
closed trail, graph decomposition, grid graphs