Hexagonal Tilings: Tutte Uniqueness

Hexagonal Tilings: Tutte Uniqueness D. Garijo ∗ , A. M´arquez ∗, M.P. Revuelta ∗ Abstract We develop the necessary machinery in order to prove that hexagonal tilings are uniquely determined by their Tutte polynomial, showing as an example how to apply this technique to the toroidal hexagonal tiling. 1 Introduction The main result in this paper has to do with graphs determined by their Tutte polynomial. This is a two variable polynomial T(G;x, y) associated with any graph G, which contains interesting information about G. For instance, T(G; 2,0) is the number of acyclic orientations of Gand T(G;x, 0) with x < 0 is the chromatic polynomial associated with G. As a natural extension of the concept of chromatically unique graph, the notion of Tutte unique graph was studied in [9]. A graph Gis said to be Tutte unique if T(G;x, y) = T(H;x, y) implies G∼ =Hfor any other graph H. A common topic in the study of this invariant is the search of large families of Tutte unique graphs. In 2003, Garijo, M´arquez, Mier, Noy, Revuelta [7],[8] present locally grid graphs as the first large family of graphs uniquely determined by their Tutte polynomial. In this paper we prove that the toroidal hexagonal tilings also satisfy this uniqueness property. The technique developed here can also be applied to the rest of hexagonal tilings and their dual graphs, the locally C6graphs. The main motivation for this study is the search of a generalization to locally plane graphs of the well known relationship existing between the Tutte polynomials of plane graphs and their duals [13]. A hexagonal tiling, H, is defined as a connected cubic graph of girth 6, having a collection of 6-cycles, C, such that every 2−path is contained in precisely one cycle of C(2−path condition). A hexagonal tiling is simple (that is, without loops and multiple edges) and every vertex belongs to exactly three hexagons (cycles of length 6)(Figure 1). Every hexagon of the tiling is called a cell. Figure 1: Hexagonal structure around x Let G= (V, E) be a graph with vertex set Vand edge set E. The rank of a subset A⊆Eis r(A) = |A| − k(A), where k(A) is the number of connected components of the spanning subgraph (V, A). The Tutte polynomial is defined as follows: T(G;x, y) = X A⊆E (x−1)r(E)−r(A)(y−1)|A|−r(A) ∗Dep. Matem´atica Aplicada I. Universidad de Sevilla. Avda. Reina Mercedes s/n. 41012 Sevilla (Spain). {dgarijo,almar,pastora}@us.es T(G;x, y) contains exactly the same information about Gas the rank-size generating polynomial which is defined as: R(G;x, y) = X A⊆E xr(A)y|A| The coefficient of xiyjin R(G;x, y) is the number of spanning subgraphs in Gwith rank iand jedges, hence the Tutte polynomial tell us for every iand jthe number of edges-sets in Gwith rank iand size j. The main strategy in the paper is the following. We first recall some definitions and results from [5, 12], such as, the classification theorem of hexagonal tilings. In Section 3, we show that these graphs are locally orientable, using the relationship existing between hexagonal tilings and locally grid graphs [5]. The local orientation of these graphs allows us to count edge-sets and it is one of the basic tools used to prove the Tutte uniqueness results. Thus, as an example, in Section 5 we apply the technique developed to show that for every hexagonal tiling Hnot isomorphic to Hk,m,0 with 2k(m+ 1) vertices there is at least one coefficient of the rank-size generating polynomial in which both graphs differ. 2 Preliminary Results In this section we state the classification theorem of hexagonal tilings proved in [5]. There exits an extensive literature on this topic. See for instance the works done by Altshuler [1, 2], Fisk [3, 4] and Negami [10, 11]. In [5], following up the line of research given by Thomassen [12], we add two new families to the classification theorem given in [12] proving that with these families we exhaust all the cases. Theorem 2.1. [5] If Gis a hexagonal tiling with Nvertices, then one and only one of the following holds: A) G≃Hk,m,r with N= 2k(m+ 1),0≤r≤ ⌊k/2⌋,m≥2,k≥3. If m= 1 then k > 3 and ⌊k/2⌋ ≥ r≥2. If m= 0 then k > 3and 3≤r≤k B) G≃Hk,m,a with N= 2k(m+ 1),m≥2,k≥3. C) G≃Hk,m,b with N= 2k(m+ 1),keven, modd, m≥3,k≥4. D) G≃Hk,m,c with N= 2k(m+ 1),m≥1,keven, k≥6. E) G≃Hk,m,f with N= 2k(m+ 2),kodd, m≥0,k≥7. F) G≃Hk,m,g with N= 2(m+ 1)(k+ 2),k≥m+ 1,m≥3. G) G≃Hk,m,h with N= 2(m+ 1)(k+ 1),k < m −1,k≥2. Some examples of hexagonal tilings are given in Figures 2, 3, 4 and 5. The parameters kand mfix, respectively, the height and the breath of the structures, called hexagonal wall of length k and breath m(Figures 2, 3, 4) and hexagonal ladder of length kand breath m(Figure 5), in which it is added edges to construct the different families of hexagonal tilings (see [5]). Given two cycles Cand C′in a hexagonal tiling G, we say that Cis locally homotopic to C′if there exists a cell, H, with C∩Hconnected and C′is obtained from Cby replacing C∩Hwith H−(C∩H). A homotopy is a sequence of local homotopies. A cycle in Gis called essential if it is not homotopic to a cell. Otherwise it is called contractible. This definition is equivalent to the one given for a graph embedded in a surface [6]. Let lGbe the minimum length of the essential cycles of G,lGis invariant under isomorphism. An edge-set contained in a hexagonal tiling is called a normal edge-set if it does not contain any essential cycle. 2 Figure 2: a) H5,5,r b) H5,4,a c) H6,5,b Figure 3: a) H6,4,c b) Embedding of H6,4,c in the Klein bottle There are two different ways of pasting together jladders each one containing ihexagons, from which we obtain two structures, called the ladder i×jand the displaced ladder i×j, shown in Figure 6. Note that the number of shortest paths between xand yor between xand zin a ladder i×jor in a displaced ladder i×jis i+j jand the length of these paths is 2(i+j)−1. Every hexagonal tiling is obtained by adding edges to a hexagonal wall or to a hexagonal ladder (except for Hk,m,h, in which we have also added two vertices) [5]. These edges are called exterior edges and every essential cycle must contains at least one of these edges ( the edges {(0,2k+m),(0,2k+m−1)}and {(m−k−1,3k+ 2),(m−k−1,3k+ 1)}in Hk,m,h are not considered exterior edges). 3 Figure 4: a) H7,4,f b) Embedding of H7,4,f in the Klein bottle Figure 5: a) H7,4,g b) H6,4,h 3 Local Orientability of Hexagonal Tilings In this section we prove that hexagonal tilings are locally orientable. This fact allow us to count edge-sets and it is the tool to distinguish at least one coefficient of the Tutte polynomials associated to two non isomorphic hexagonal tilings. We first recall a minor relationship existing between hexagonal tilings and locally grid graphs (see [5]). We say that a 4−regular, connected graph Gis a locally grid graph if for every vertex xthere exists an ordering x1, x2, x3, x4of N(x) and four different vertices y1, y2, y3, y4, such that, taking the indices modulo 4, N(xi)∩N(xi+1) = {x, yi} N(xi)∩N(xi+2) = {x} and there are no more adjacencies among {x, x1,...,x4, y1,...,y4}than those required by this condition (Figure 7). Every locally grid graph is a minor of a hexagonal tiling and in [5] it was proved that there exits a biyective minor relationship preserved by duality between hexagonal tilings with the same 4 Figure 6: a) Displaced ladder 4 ×2 b) Ladder 4 ×2 Figure 7: Locally Grid Structure chromatic number and locally grid graphs. A perfect matching Pis selected in each one of the families given in the classification theorem of hexagonal tilings, except in one case, Hk,m,f in which the set of selected edges is not a matching. Pcontains two edges of each hexagon. In Hk,m,f there are k−1 hexagons in which we select four edges pairwise incident. A locally grid graph is obtained by contracting the edges of this matching, and deleting parallel edges if necessary. There are just two cases in which parallel edges must be deleted, Hk,m,f and Hk,m,h. These perfect matchings and the set of edges of Hk,m,f verify that if we have two hexagonal tilings with the same chromatic number, the result of the contraction of their perfect matchings (or the selected edges in Hk,m,f ) are two locally grid graphs belonging to different families. This condition is going to be essential in the search of a generalization, for these families, of the relationship existing between the Tutte polynomial of a plane graph and its dual [13]. In [8] it was proved that locally grid graphs are locally orientable. Given a vertex vof a locally grid graph G, two edges incident with vare said to be adjacent if there is a square containing them both; otherwise they are called opposite. An orientation at a vertex vconsists of labeling the four edges incident with vbijectively with the labels N,S,E,Win such a way that the edges labelled Nand Sare opposite, and so are the ones labelled as Eand W. Lemma 3.1. Hexagonal tilings are locally orientable. Proof. Let Hbe a hexagonal tiling. By Theorem 2.1, His isomorphic to one of the following graphs: Hk,m,r,Hk,m,a,Hk,m,b,Hk,m,c,Hk,m,h,Hk,m,g,Hk,m,f . Suppose first that His not isomorphic to Hk,m,f . For every vertex v∈V(H) there is exactly one edge of the perfect matching Pincident with v, call it {v, v′}. Consider the union of the local structures of vand v′, labeling the other two edges incident with vas e1and e2and the other two edges incident with v′as e3and e4. Contract all the edges of Pbelonging to this union, deleting parallel edges if necessary. As it is shown in Figure 8a we obtain a grid 3 ×3, hence we can label the edges e1,e2,e3and e4bijectively with the labels N,S,E,Wfollowing the criterion established for the locally grid graphs. The edge {v, v′}is considered opposite to the unique edge incident with vand belonging to the perfect matching, P′, formed by the edges {(i, l)(i, l + 1)}, 0 ≤i≤m not belonging to P. If His isomorphic to Hk,m,f , then there are either one or two edges belonging to Pand incident with v. If vdoes not belong to a hexagon that has more than two edges of P, we follow the same process as in the previous case. Suppose, now, that vis a vertex belonging to one of the hexagons that contains four edges belonging to P. We consider two cases: 5 Figure 8: a) Local orientation at v∈V(H) not isomorphic to Hk,m,f b) Local orientation at v∈V(Hk,m,f ) (1) There are two edges of Pincident with v, call them {v, v′}and {v, v′′}. The union of the hexagonal structures of v,v′and v′′ is composed by five hexagons. Label the unique edge incident with vand not belonging to Pas e1. The edge incident with v′′ not belonging to Pand sharing an hexagon with e1is labelled e2. Finally, the edges incident with v′no belonging to Pare labelled e3and e4. Contracting all the edges of Pbelonging to this union and deleting parallel edges, we also obtain a grid 3 ×3 and we can label the edges incident with v,v′and v′′ bijectively with the labels N,S,E,W(Figure 8b). {v, v′}and {v, v′′}are considered opposite to the unique edge incident with v′and v′′ respectively, belonging to P′. (2) There is one edge of Pincident with v, call it {v, v′}. There has to be one edge, different from {v, v′}, incident with v′and belonging to P, call it {v′, v′′}. The union of the hexagonal structures of vand v′′ is composed by five hexagons. The two edges incident with vnot belonging to Pare labelled e1and e2. The unique edge incident with v′not belonging to Pis labelled e3, and the edge incident with v′′ not belonging to Por to the hexagon that contains four edges of P, is labelled e4. Contracting all the edges of Pbelonging to this union and deleting parallel edges, we also obtain a grid 3 ×3 and we can label the edges incident with v,v′and v′′ bijectively with the labels N,S,E,W.{v, v′}and {v′, v′′}are considered opposite to the edges incident with v and v′′ respectively, belonging to the hexagon that contains four edges of P. The previous proof give us a definition of adjacent and opposite edges for hexagonal tilings. Two edges incident with a vertex vand no belonging to Pare called adjacent or opposite if they are so in the locally grid structure resulting from applying the operations explained above. Two edges incident with vand belonging to Pare always opposite. By the orientation (v, v′, e, f) we mean that vis the origin vertex, {v, v′} ∈ P,eis the unique edge incident with vand opposite to the other two edges incident with v. This edge never belongs 6 to Pand it is labelled E. Finally, fis an edge incident with vand labelled N. The orientation (v, v′, v′′, e, f) means that vis the origin vertex, {v, v′},{v, v′′} ∈ P,eis the unique edge incident with vand opposite to the other two edges incident with v, and fis an edge incident with v labelled N. We will denote both cases as (v, v′, e, f). If α∈ {N, S, E, W}, we denote α−1the label opposite to α. If we fix an orientation at v∈V(H) (vis the origin vertex) then every vertex uadjacent to vis unambiguously oriented, because the orientation at vinduces an orientation at u: if {u, v}is labelled αfrom v, it is labelled α−1from u. If tzyxvw is a hexagon and {x, v},{w, v}are labelled βand αfrom vrespectively, then {x, y}is β from x,{z, y}is αfrom y,{z, t}is β−1from zand {t, w}is β−1from t. We also can translate the orientation at vto all the vertices of a path beginning at v, but two different paths joining vand ucan induce different orientation at u. This does not happen if the union of these two paths is a contractible cycle. In fact, we can transform one path into the other one using three elementary transitions and their inverse: if e,f,g,h,i,jare the edges of a hexagon ordered cyclically, we can change e,f,g,h,iby j;e,f,g,hby i,jand e,f,gby h,i,jand these operations do not change the orientation at the endpoint. Let Abe a connected normal edge set in a hexagonal tiling H. Fixed an orientation at a vertex v∈V(A), then all the vertices in V(A) are unambiguously oriented. Every path in Acan be described as a sequence of the labels {N, S, E, W}(Figure 9a). This allow us to assign coordinates to every vertex in V(A): vhas coordinates (0,0) and u∈V(A) has coordinates (i, j) if in one path in Ajoining vto u(taking into account that the orientation at the endpoint induced by different paths joining vto udoes not change), iis the number of labels Eminus the number of labels W and jis the number of labels Nminus the number of labels S. Lemma 3.2. Let Abe a connected normal edge set in a hexagonal tiling Hwith |A| ≤ lH+ 3, then different vertices in V(A)have different coordinates. Proof. First, we are going to prove that with a fixed orientation (v, v′, e, f) no vertex except the origin can have coordinates (0,0). Suppose that there exists x∈V(A) such that xhas coordinates (0,0), then there exits a path Rjoining vto xwith as many labels Nas labels Sand as many labels Eas labels W. We are going to show that x=vby induction on the length of this path. If |R|= 6 and vis the origin vertex, the first labels of Rcan be: NN,NW,E,SS, or SW and using the elementary transitions described previously, we can change these labels by ENNW, SWNN,NNESS,ESSW and NW SS respectively. To obtain as many labels Nas labels Sand as many labels Eas labels Wit must be that v=x. We assume that every path R(not a cycle) with |R|< n does not have as many labels Nas labels Sand as many labels Eas labels Wand we prove the result for |R|=n. Suppose that there exits a path Rjoining vand x, not a cycle, with |R|=nand having as many labels Nas those labelled Sand as many Eas W, then there exits a subsequence labelled β(α−1)lβαsβ−1(α−1)mβ−1or βαlβαsβ−1αmβ−1(or other analogous subsequence). In the first case we can change this subsequence by αs−l−mkeeping the orientation at the endpoint. Analogously, in the second case the subsequence can be changed by αs+l+m. In any case, the change gives rise to a new path R′joining vand xwith |R′|< n, in a new connected edge set A′. This set is also a normal edge set because |A′| ≤ |A| − 4≤lH−1. By hypothesis, R′does not have as many labels Nas Sand Eas W, hence neither does Rand we obtain a contradiction. Given two different vertices, uand win V(A), we consider the paths Ruand Rwjoining uto v and wto vrespectively. Since Ais connected, there is a path Rw∪Rjoining vto uand keeping the orientation at u. Hence, it is easy to prove that uand wcan not have the same coordinates. From now on, and unless otherwise stated, we consider that all normal edge-sets have at most lH+ 3 elements. 7 4 Counting Edge-Sets The aim of this section is to find a system which allow us to count edge-sets in order to prove that there is at least one coefficient of the rank-size generating polynomial in which two non isomorphic hexagonal tilings differ. Our first step is to codify the edge-sets of a hexagonal tiling. Let L∞be the infinite plane square lattice, that is, the infinite graph having as vertices Z×Zand in which (i, j) is joined to (i−1, j),(i+1, j),(i, j−1),(i, j+1). We delete the edges {(i, 2j),(i−1,2j)} if ieven and {(i, 2j+ 1),(i+ 1,2j+ 1)}if iodd, obtaining a infinite plane hexagonal tiling H∞. Let Ω be the group of graph automorphisms of H∞. This group is generated by translations, symmetries and rotations of the plane that map vertices to vertices. Let Σ(H∞) be the set of all finite connected edge-sets of H∞. An equivalence relation is defined in Σ(H∞) as follows: B1∼B2⇔ ∃σ∈Ω, σ(B1) = B2 If Λ is a set of representatives of Σ(H∞)/∼such that every B∈Λ contains the vertex (0,0), then Λ covers all the possible shapes that a normal edge-set could have. We are going to define a set Γ of words over the alphabet {N, S, E, W }that represents all edgesets of Σ(H∞)/∼. Label {(0,0),(0,1)}as N,{(0,0),(1,0)}as E,{(0,1),(−1,1)}from (0,1) as Wand {(0,0),(−1,0)}as S. For every B∈Λ there is a sequence γBover the the alphabet {N, S, E, W}such that beginning at (0,0) and following the instructions given by γBthe unique edges covered are those of B. Note that one edge can be covered more than once and that the sequence γBis not unique (Figure 9a). Since every sequence over the alphabet {N, S, E, W}can not represent a set of Λ (for instance, a sequence with two consecutive labels E) we are going to establish some restrictions on this alphabet: (1) No sequence begins with the label W. (2) There are no two consecutive labels E(analogously W). (3) If a sequence begins with a label N(analogously S), there must be an odd number of labels Nand Sbefore having a label W; and an even number if the label is E. Hence, there are an odd number of labels Nand Sbetween two labels Wand an even number between two labels E. (4) If a sequence begins with a label E, there are an odd number of labels Nand Sbetween two labels Eand an even number between two labels W. Call Γ the set of words over the alphabet {N, S, E, W}verifying the three previous conditions. These restrictions do not modify the fact that every B∈Λ has a word γBassociated. Conversely, given γ∈Γ there exits B∈Λ, such that γ=γB. It will be denoted B(γ). The next step is to assign one word from Γ to each normal connected edge-set of a hexagonal tiling, H. Fix an orientation (v, v′, e, f) at H, being v∈V(H) the origin vertex. Following the code given by γfrom vwith orientation (v, v′, e, f), an edge set AH(γ, v, v′, e, f) is obtained, called the instance of γin Hand we call (v, v′, e, f) an orientation of the instance. An instance of γcan have different orientations associated to it, the number of them depends only on the symmetries of B(γ) and it is called sym(γ). The length of γis the number of labels N,S,E,Wthat give rise to γ. Lemma 4.1. Let Hbe a hexagonal tiling and γ∈Γ. If r(B(γ)) = lH−1and |B(γ)| ≤ lH, then AH(γ, v, v′, e, f)is a normal edge-set and it has the same rank and size as B(γ). Proof. We are going to prove this result by induction on the length of γ. If γhas length equal to one, the result is trivial. Let γ′be the word resulting from removing the last label from γ. By hypothesis AH(γ′, v, v′, e, f) is normal and it has the same rank and size as B(γ′). When we add the last label of γto γ′, there are three possibilities on B(γ′): (1) We are adding one edge between two vertices belonging to B(γ′) (2) We are adding an isthmus. (3) We do not add any edge. 8 (1) Let x′be the last vertex of AH(γ′, v, v′, e, f) covered by γ′. Since AH(γ′, v, v′, e, f) is normal all the vertices of AH(γ′, v, v′, e, f) are unambiguously oriented. Let cbe the added edge. This edge is labelled αfrom x′following the orientation (v, v′, e, f). Suppose that AH(γ, v, v′, e, f) is not a normal edge-set, then when we have added the edge cwe have created an essential cycle. Since |B(γ)| ≤ lH,AH(γ, v, v′, e, f) has to be an essential cycle. B(γ) contains at least one cycle because it has been obtained joining two vertices of B(γ′). Hence γcontains a subword that can be β(α−1)sβ−1αs,β(α−1)sβ(α−1)tβ−1αrβ−1,β(α−1)sβ(α−1)tβ−1(α−1)rβ−1(or other analogous cases to the last ones) (Figure 9b). We change these subwords by β(α−1)s−2β−1αs−2, (α−1)t+s−r, (α−1)t+s+rrespectively. Figure 9: a) A path described using two different sequence over {N, S, E, W}, the first one is ENENNW SNESESS and the second one is ENENESSNNWNWS b) The marked path labelled as abab(a−1)6b−1ab−1is changed by (a−1)3 In any case, a word γ∗is obtained of length smaller than the length of γ, hence AH(γ∗, v, v′, e, f) is a normal edge-set and contains a cycle. If we consider the simply connected region determined by AH(γ∗, v, v′, e, f) and we add, depending on the case, one hexagon or two columns of hexagons, a simply connected region is obtained which is determined by γ. Since AH(γ, v, v′, e, f) is an essential cycle, at least one vertex of the added hexagons belongs to AH(γ∗, v, v′, e, f). Therefore, AH(γ, v, v′, e, f) has at least two cycles and we obtain a contradiction. The equality of ranks and sizes remains to be proved. By hypothesis of induction r(AH(γ′, v, v′, e, f)) = r(B(γ′)) and |AH(γ′, v, v′, e, f)|=|B(γ′)|. Furthermore |B(γ)|=|B(γ′)|+ 1 and r(B(γ)) = r(B(γ′)). Since AH(γ, v, v′, e, f) is normal, r(AH(γ, v, v′, e, f)) = r(AH(γ′, v, v′, e, f)) and |AH(γ, v, v′, e, f)|= |AH(γ′, v, v′, e, f)|+ 1. (2) and (3) The second case is easier than the previous one. Using a similar reasoning we obtain that if AH(γ, v, v′, e, f) is not a normal edge-set, then it is an essential cycle. But an essential cycle only could be created joining two vertices belonging to B(γ′). The equality of ranks and sizes is proved as in case (1). The third case is trivial because if we do not add any edge, AH(γ, v, v′, e, f) = AH(γ′, v, v′, e, f). Lemma 4.2. Let A⊆E(H)be a connected normal edge-set. Fixed an orientation (v, v′, e, f) with v∈V(A), there exits a unique edge-set B⊆E(H∞)and a unique graph isomorphism ϕ:V(A)→V(B)such that: (1) ϕ(v) = (0,0). (2) If the edge {x, y} ∈ Ais labelled αfrom x, then {ϕ(x), ϕ(y)}is labelled αfrom ϕ(x) according to the orientation ((0,0),{(0,0),(1,0)},{(0,0),(0,1)}. Proof. Fixed an orientation (v, v′, e, f) with v∈V(A), we can assign coordinates to the vertices 9 (3) In Hk,m,0, every essential cycle of length 2kplus three edges has rank 2k+ 2 (Figure 10a), but in Hk′,m′,a there are essential cycles in which if we add three edges we obtain sets with rank 2k+ 1 (Figure 10b). By hypothesis, both graphs have the same number of shortest essential cycles therefore the number of edge-sets in this case is greater in Hk,m,0than in Hk′,m′,a. Cases 5 and 6 If G∼ =Hk′,m′,b with k < m+1 and k′> m′+1 or G∼ =Hk′,m′,h with k < m+1 we use the same arguments as those in the previous case to prove that Hk,m,0has more edge-sets with rank 2k+ 2 and size 2k+ 3 than Hk′,m′,b and Hk′,m′,h. 6 Concluding Remarks We have proved that the toroidal hexagonal tiling, Hk,m,0is Tutte unique. Since the results given in Sections 3 and 4 are proved for all hexagonal tilings, it seems that all hexagonal tilings are Tutte unique. To verify this, we would have to do all cross-checkings between any two of these graphs as was done in Section 5. This study has been done for locally grid graphs in [7]. The technique developed in this paper can also be applied to locally C6graphs. This would follow from the local orientation existing in these graphs, based on the minor relationship described in [5] between locally grid graphs and locally C6graphs. References [1] A. Altshuler, Hamiltonian Circuits in some maps on the torus, Discret Math. 1(1972), 299314. [2] A. Altshuler, Construction and enumeration of regular maps on the torus, Discret Math. 4(1973), 201-217. [3] S. Fisk, Geometric coloring theory, Advances in Math. 24(1977), 298-340. [4] S. Fisk, Variations on coloring, surfaces and higher dimensional manifolds , Advances in Math. 25(1977), 226-266. [5] D. Garijo, I. Gitler, A. M´arquez and M.P. Revuelta, Hexagonal tilings and Locally C6graphs, Preprint, 2004. [6] D. Garijo, Polinomio de Tutte de Teselaciones Regulares, Thesis (2004). [7] D. Garijo, A. M´arquez and M.P. Revuelta, Tutte Uniqueness of Locally Grid Graphs, Ars Combinatoria (to appear) (2005). [8] A. M´arquez, A. de Mier, M. Noy, M.P. Revuelta, Locally grid graphs:classification and Tutte uniqueness, Discr. Math. 266 (2003), 327-352. [9] A. de Mier, M. Noy, On graphs determined by their Tutte polynomials, Graphs Combin. 20 (2004), no.1, 105-119. [10] S. Negami, Uniqueness and faithfulness of embedding of toroidal graphs, Discrete Math. 44(1983), no.2, 161-180. [11] S. Negami, Classification of 6-regular Klein bottle graphs, Res. Rep. Inf. Sci. T.I.T.A-96 (1984). [12] C. Thomassen, Tilings of the Torus and the Klein Bottle and vertex-transitive graphs on a fixed surface, Trans. Amer. Math. Soc. 323(1991), no.2, 605-635. [13] W.T. Tutte Graph Theory, Addison Wesley, California (1984). 16