Locally grid graphs: Classification and Tutte uniqueness (Q1810656)

A 4-regular connected graph \(G\) is said to be locally grid if for every of its vertices \(x\) there exists an ordering \(x_1,x_2,x_3,x_4\) of its neighbours and four different vertices \(y_1,y_2,y_3,y_4\) such that \(N(x_i) \cap N(x_{i+1}) = \{x,y_i\}, N(x) \cap N(x_{i+2}) = \{x\}\) (indices taken modulo 4, \(N(z)\) denotes the neighbourhood of \(z\)) and there are no more adjacencies among \(\{x,x_1,\dots,x_4,y_1,\dots,y_4\}\) than those described by this condition; in other words, around each vertex of a locally grid graph is a \(3 \times 3\) grid. In the first part of the paper, the authors give the complete classification of locally grid graphs, showing that each locally grid graph belongs exactly to one of three specified families of graphs embeddable in the torus or in the Klein bottle. The second part deals with Tutte polynomials of toroidal grids \(C_p \times C_q\). It is proved that the graph \(C_p \times C_q\) is Tutte-unique for \(p,q \geq 6\) (that means, this if \(C_p \times C_q\) and \(H\) have the same Tutte polynomial, then they are isomorphic).