Euler tours and a game with dominoes (Q1356489): Difference between revisions

Let \(G\) be an Eulerian graph and \(\{E_0,E_1\}\) a partition of its edge set \(E\) with \(|E_0|=|E_1|\). An \((E_0,E_1)\)-domino sequence in \(G\) is a sequence \(T_0,T_1,\dots,T_m\) of trails of \(G\) such that (i) \(T_0\) consists of a single vertex and \(T_m\) is an Euler tour of \(G\), (ii) for \(j=1,\dots,m\), \(T_j\) is obtained from \(T_{j-1}\) by adding an edge \(e_j\), where \(e_j\) is incident with the initial vertex or the terminal vertex of \(T_{j-1}\), and \(e_j\in E_0\) iff \(j\) is odd. The graph obtained from the complete graph \(K_n\) by adding a single loop at each vertex is denoted by \(K_n'\). The edge set of \(K_n'\) represents a set of \(\left(\begin{smallmatrix} n+1\\ 2\end{smallmatrix}\right)\) dominoes (usually \(n=7\)). A string of dominoes, formed according to the standard rules of Domino, corresponds to a trail in \(K_n'\), and a friedly game of Domino corresponds to the problem to construct an \((E_0,E_1)\)-domino sequence in \(K_n'\) for given \(E_0\), \(E_1\). The authors prove the following main theorem: Let \(G\) be an Eulerian graph on \(n\geq 2\) vertices with no loops such that its underlying simple graph is complete. For any partition \(\{E_0,E_1\}\) of the edge set \(E\) of \(G\), there are matchings \(M_i\) in \(G(E_i)\), \(i=0,1\), such that \((G(E_i)- M_i)+ M_{1-i}\) has an open Euler trail, \(i=0,1\). (For \(A\subseteq E\), \(G(A)\) denotes the subgraph of \(G\) the vertices of which are the endvertices of the edges of \(A\) and the edge set is \(A\).) Using this result, the following assertion is proved which solves a problem posed by González-Acuña and Urrutia: if \(n\equiv 3\pmod 4\) for any \((E_0,E_1)\)-partition of the edge set of \(K_n'\), there exists an \((E_0,E_1)\)-domino sequence in \(K_n'\).