Edge-Simple Circuits through 10 Ordered Vertices in Square Grids

摘要

A circuit in a simple undirected graph G - (V, E) is a sequence of vertices {v_1, v_2, ..., v_(k+1)} such that v_1 = v_(k+1) and {v_i, v_(i+i) ∈ E for i = 1, ..., k. A circuit C is said to be edge-simple if no edge of G is used twice in C. In this article we study the following problem: which is the largest integer k such that, given any subset of k ordered vertices of an infinite square grid, there exists an edge-simple circuit visiting the k vertices in the prescribed order? We prove that k = 10. To this end, we first provide a counterexample implying that k < 11. To show that k ≥ 10, we introduce a methodology, based on the notion of core graph, to reduce drastically the number of possible vertex configurations, and then we test each one of the resulting configurations with an ILP solver.