Understanding chicken walks on \(n \times n\) grid: Hamiltonian paths, discrete dynamics, and rectifiable paths.

*(English)*Zbl 1330.92137Summary: Understanding animal movements and modeling the routes they travel can be essential in studies of pathogen transmission dynamics. Pathogen biology is also of crucial importance, defining the manner in which infectious agents are transmitted. In this article, we investigate animal movement with relevance to pathogen transmission by physical rather than airborne contact, using the domestic chicken and its protozoan parasite Eimeria as an example. We have obtained a configuration for the maximum possible distance that a chicken can walk through straight and nonoverlapping paths (defined in this paper) on square grid graphs. We have obtained preliminary results for such walks which can be practically adopted and tested as a foundation to improve understanding of nonairborne pathogen transmission. Linking individual nonoverlapping walks within a grid-delineated area can be used to support modeling of the frequently repetitive, overlapping walks characteristic of the domestic chicken, providing a framework to model fecal deposition and subsequent parasite dissemination by fecal/host contact. We also pose an open problem on multiple walks on finite grid graphs. These results grew from biological insights and have potential applications.

##### MSC:

92D50 | Animal behavior |

92D30 | Epidemiology |

05C81 | Random walks on graphs |

05C90 | Applications of graph theory |

##### References:

[1] | Veterinary Parasitology (2007) |

[2] | Chapman, Review of coccidiosis research, Advances in Parasitology 83 pp 93– (2013) |

[3] | Dalloul, Poultry coccidiosis: recent advancements in control measures and vaccine development, Expert Review of Vaccines 5 pp 143– (2006) |

[4] | Velkers, Oocyst output and transmission rates during successive infections with Eimeria acervulina in experimental broiler flocks, Veterinary Parasitology 187 pp 63– (2012) |

[5] | Shirley, The biology of avian Eimeria with an emphasis on their control by vaccination, Advances in Parasitology 60 pp 285– (2005) |

[6] | Williams, Anticoccidial vaccination of broiler chickens in various management programmes: relationship between oocyst accumulation in litter and the development of protective immunity, Veterinary Research Communications 24 pp 309– (2000) |

[7] | Williams, Epidemiological aspects of the use of live anticoccidial vaccines for chickens, International Journal for Parasitology 28 pp 1089– (1998) |

[8] | Blake, Genetic mapping identifies novel highly protective antigens for an apicomplexan parasite, PLoS Pathogens 7 pp e1001279– (2011) |

[9] | Itai, Hamilton paths in grid graphs, SIAM Journal on Computing 11 (4) pp 676– (1982) · Zbl 0506.05043 |

[10] | Zamfirescu, Hamiltonian properties of grid graphs, SIAM Journal on Discrete Mathematics 5 (4) pp 564– (1992) · Zbl 0770.05073 |

[11] | Keshavarz-Kohjerdi, Hamiltonian paths in some classes of grid graphs, Journal of Applied Mathematics 2012 pp Article ID 4750– (2012) · Zbl 1245.05081 |

[12] | Kwong, A matrix method for counting Hamiltonian cycles on grid graphs, European Journal of Combinatorics 15 (3) pp 277– (1994) · Zbl 0798.05032 |

[13] | Thompson, Hamiltonian tours and paths in rectangular Lattice graphs, Mathematics Magazine 50 (3) pp 147– (1977) · Zbl 0357.05054 |

[14] | Nash-Williams, Infinite graphs-a survey, Journal Combinatorial Theory 3 pp 286– (1967) · Zbl 0153.25801 |

[15] | Nash-Williams, Reconstruction of infinite graphs, Discrete Mathematics 95 pp 221– (1991) · Zbl 0759.05066 |

[16] | Bondy, Reconstructing infinite graphs, Pacific Journal of Mathematics 52 pp 331– (1974) · Zbl 0295.05125 |

[17] | Diestel, Graph Theory (2000) |

[18] | Harel, Hamiltonian paths in infinite graphs, Israel Journal of Mathematics 76 (3) pp 317– (1991) · Zbl 0756.05073 |

[19] | Rödl, Dirac-type conditions for Hamiltonian paths and cycles in 3-uniform hypergraphs, Advances in Mathematics 3 pp 1225– (2011) · Zbl 1220.05083 |

[20] | Bellman, Dynamic programming treatment of the travelling salesman problem, Journal of the ACM 9 pp 61– (1962) · Zbl 0106.14102 |

[21] | Rubin, A search procedure for Hamilton paths and circuits, Journal of the ACM 21 (4) pp 576– (1974) · Zbl 0293.05140 |

[22] | Ore, Note on Hamilton circuits, American Mathematical Monthly 67 pp 55– (1960) · Zbl 0089.39505 |

[23] | Newman, A problem in graph theory, American Mathematics Monthly 65 pp 611– (1958) · Zbl 0082.37903 |

[24] | Kronk, A note on k-path Hamiltonian graphs, Journal of Combinatorial Theory 7 pp 104– (1969) · Zbl 0179.29105 |

[25] | Ajtai, The longest path in a random graph, Combinatorica 1 (1) pp 1– (1981) · Zbl 0489.05052 |

[26] | Pittel, A random graph with a subcritical number of edges, Transactions of American Mathematical Society 309 (1) pp 51– (1988) · Zbl 0658.05062 |

[27] | Krivelevich, Longest cycles in sparse random digraphs, Random Structures & Algorithms 43 (1) pp 1– (2013) · Zbl 1270.05050 |

[28] | Karger, On approximating the longest path in a graph, Algorithmica 18 (1) pp 82– (1997) · Zbl 0876.68083 |

[29] | Feder, Approximating the longest cycle problem in sparse graphs, SIAM Journal on Computing 31 (5) pp 1596– (2002) · Zbl 1041.68069 |

[30] | Zhang, Approximating the longest paths in grid graphs, Theoretical Computer Science 412 (39) pp 5340– (2011) · Zbl 1222.68089 |

[31] | Keshavarz-Kohjerdi, A linear-time algorithm for the longest path problem in rectangular grid graphs, Discrete Applied Mathematics 160 (3) pp 210– (2012) · Zbl 1237.05115 |

[32] | Keshavarz-Kohjerdi, An efficient parallel algorithm for the longest path problem in meshes, Journal of Supercomputing 65 pp 723– (2013) |

[33] | Fernandez de la Vega, Trees in sparse random graphs, Journal of Combinatorial Theory Series B 45 (1) pp 77– (1988) · Zbl 0662.05050 |

[34] | Krivelevich, Embedding spanning trees in random graphs, SIAM Journal of Discrete Mathematics 24 (4) pp 1495– (2010) · Zbl 1221.05283 |

[35] | Chou, On the complexity of finding paths in a two-dimensional domain. II. Piecewise straight-line paths, Electronic Notes in Theoretical Computer Science 120 pp 45– (2005) |

[36] | Henrici, Applied and Computational Complex Analysis (1986) · Zbl 0578.30001 |

[37] | Cesari, Rectifiable curves and the Weierstrass integral, American Mathematical Monthly 67 (7) pp 485– (1958) · Zbl 0083.32702 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.