Tutte uniqueness of locally grid graphs

Morfismos,Vol.8,No.1,2004,pp.35–55 Tutte uniqueness of locally grid graphs ∗ D. Garijo A. M´arquez M.P. Revuelta Abstract Agraphissaidtobelocallygridifthestructurearoundeachof its vertices is a 3 ×3grid.Asafollowupoftheresearchinitiated in [4] and [3] we prove that most locally grid graphs are uniquely determined by their Tutte polynomial. 2000 Mathematics Subject Classification: 05C75, 05C10. Keywords and phrases: Locally grid graph; Tutte polynomial. 1Introduction Given a graph G,theTuttepolynomialofGis a two-variable polynomial T(G;x, y), which contains considerable information on G[1]. A graph Gis said to be Tutte unique if T(G;x, y)=T(H;x, y)impliesG∼ =H for every other graph H.InSection2weprovethat,locallygridgraphs are Tutte unique. Given a fixed graph H,aconnectedgraphGis said to be locally Hif for every vertex xthe subgraph induced on the set of neighbors of xis isomorphic to H.Forexample,ifPis the Petersen graph, then there are three locally Pgraphs [2]. The locally grid condition is slightly different since it involves not only a vertex and its neighbors, but also four vertices at distance two. From now on, all graphs considered have no isolated vertices. We first recall some definitions and results about locally grid graphs from [4]. ∗Invited article.PartiallysupportedbyprojectsBFM2001-2474-ORIandPAI FQM-164. This work is part of the first author’s Ph.D. thesis writen at the University of Sevilla. 35 36 D. Garijo, A. M´arquez and M.P. Revuelta Let N(x)bethesetofneighborsofavertexx.Wesaythata 4−regular connected graph Gis a locally grid graph if for each vertex x there exists an ordering x1,x 2,x 3,x 4of N(x)andfourdifferentvertices y1,y 2,y 3,y 4,suchthat,takingtheindicesmodulo4, N(xi)∩N(xi+1)={x, yi} N(xi)∩N(xi+2)={x} and there are no more adjacencies among {x, x1,...,x 4,y 1,...,y 4}than those required by these conditions (Figure 1). Figure 1: Locally Grid Structure Locally grid graphs are simple, two-connected, triangle-free, and each vertex belongs to exactly four cycles of length 4. Let H=Pp×Pqbe the p×qgrid, where Plis a path with lvertices. Label the vertices of Hwith the elements of the abelian group Zp×Zq in the natural way. Vertices of degree four already have the locally grid property, hence we have to add edges between vertices of degree two and three in order to obtain a locally grid graph. A complete classification of locally grid graphs is given in [4], and they fall into the following families. In all the Figures, the vertices of the graph are represented by dots and two points with the same label correspond to points that are identified in the surface. The Torus Tδ p,q with p≥5, 0 ≤δ≤p/2, δ+q≥5ifq≥4, δ+q≥6ifq=2,3or4≤δ<p/2withδ(=p/3,p/4ifq=1. (Figure 2a) E(Tδ p,q)=E(H)∪{{(i, 0),(i+δ, q −1)},0≤i≤p−1} ∪{{(0,j),(p−1,j)},0≤j≤q−1}. For δ=0weobtainthetoroidalgridCp×Cq,inthiscasewewillwrite Tp,q.Wecanassumethatδ≤p/2. The Klein Bottle K1 p,q with p≥5, podd, q≥5. (Figure 2b) E(K1 p,q)=E(H)∪{{(j, 0),(p−j−1,q−1)},0≤j≤p−1} ∪{{(0,j),(p−1,j)},0≤j≤q−1}. Tutte uniqueness of locally grid graphs 37 1 2 3 4 5 6 7 8 9 10 11 12 6 7 8 9 10 11 12 5 4 3 2 1 a) 1 2 3 4 5 6 7 8 9 10 11 12 6 7 8 9 10 12 11 5 4 3 2 1 b) Figure 2: a) T2 7,5b) K1 7,5 The Klein Bottle K0 p,q with p≥6, peven, q≥4(Figure3a). E(K0 p,q)=E(H)∪{{(j, 0),(p−j−1,q−1)},0≤j≤p−1} ∪{{(0,j),(p−1,j)},0≤j≤q−1}. The Klein Bottle K2 p,q with p≥6, peven, q≥5(Figure3b). E(K2 p,q)=E(H)∪{{(j, 0),(p−j, q −1)},0≤j≤p−1} ∪{{(0,j),(p−1,j)},0≤j≤q−1}. 1 2 3 4 5 6 7 8 9 10 11 9 8 7 6 11 10 5 4 3 2 1 a) 1 2 3 4 5 6 7 8 9 10 11 10 9 8 7 6 11 5 4 3 2 1 b) Figure 3: a) K0 6,5b) K2 6,5 The graphs Sp,q with p≥3andq≥6. (Figure 4). If p≤q 38 D. Garijo, A. M´arquez and M.P. Revuelta E(Sp,q)=E(H)∪{{(j, 0),(p−j, q −p+j)},0≤j≤p−1} ∪{{(0,i),(i, q −1)},0≤i≤p−1} ∪{{(0,i),(p−1,i−p)},p≤i≤q−1}. If q≤p E(Sp,q)=E(H)∪{{(j, 0),(0,q−1−j)},0≤j≤q−1} ∪{{(p−1−i, q −1),(p−1,i)},0≤i≤q−1} ∪{{(i, q −1),(i+q,0)},0≤i≤p−q−1}. 13 12 11 10 9 13 12 11 10 9 6 7 8 1 2 3 4 5 10 10 9 8 7 6 9 8 7 6 6 7 8 9 10 11 12 13 6 7 8 9 10 5 4 3 2 1 11 12 13 1 2 3 4 5 1 2 3 4 5 6 7 8 b) a) Figure 4: a) S5,8b) S8,5 Theorem 1.1 [4] If Gis a locally grid graph with Nvertices, then exactly one of the following holds: a) G∼ =Tδ p,q with pq =N,p≥5,δ≤p/2and δ+q≥5if q≥4or δ+q≥6if q=2,3or 4≤δ<p/2,δ(=p/3,p/4if q=1. Tutte uniqueness of locally grid graphs 39 b) G∼ =Ki p,q with pq =N,p≥5,i≡p(mod 2) for i∈{0,1,2}and q≥4+,i/2-. c) G∼ =Sp,q with pq =N,p≥3and q≥6. 2TutteUniqueness Let G=(V,E)beagraphwithvertexsetVand edge set E.Therank of a subset A⊆Eis defined by r(A)=|A|−k(A), where k(A)isthe number of connected components of the spanning subgraph (V,A). The rank-size generating polynomial is defined as: R(G;x, y)= ! A⊆E xr(A)y|A| The coefficient of xiyjin R(G;x, y)isthenumberofspanningsubgraphs in Gwith rank iand jedges. This polynomial contains exactly the same information about Gas the Tutte polynomial, which is given by: T(G;x, y)= ! A⊆E (x−1)r(E)−r(A)(y−1)|A|−r(A) hence, the Tutte polynomial tells us for every iand jthe number of edgesets in Gwith rank iand size j.Thisfactisgoingtobeessentialinorder to prove the Tutte uniqueness of locally grid graphs. Given a locally grid graph G,weshowthatforeverylocallygridgraphHdifferent from Gand with |V(G)|=|V(H)|there is at least one coefficient of the rank-size generating polynomial in which both graphs differ. Let Sbe the surface in which a locally grid graph Gis embedded, that is, Sis a torus or a Klein bottle [4]. Given two cycles Cand C# of G,wesaythatCis locally homotopic to C#if there exists a cycle of length four, say H,withC∩Hconnected and C#is obtained from Cby replacing C−(C∩H)withH−(C∩H). A homotopy is a sequence of local homotopies. A cycle of Gis called essential if it is not homotopic to a cycle of length four. Let lGbe the minimum length of an essential cycle of G.Note that lGis invariant under isomorphism. The number of essential cycles of length lGcontributes to the coefficient alG−1,lGof R(G;x, y), which counts the number of edges sets with rank lG−1andsizelG. In order to show the Tutte uniqueness of locally grid graphs we are going to use the following results proved in [4]: 40 D. Garijo, A. M´arquez and M.P. Revuelta Lemma 2.1 [4] Given two graphs Gand G#,ifGis locally grid and T(G;x, y)=T(G#;x, y)then G#is locally grid. Lemma 2.2 [4] Let G,G#be a pair of locally grid graphs with pq vertices then: a) lG(=lG"implies T(G;x, y)(=T(G#;x, y). b) If lG=lG"but Gand G#do not have the same number of shortest essential cycles, then T(G;x, y)(=T(G#;x, y). The process we are going to follow is to pairwise compare all the graphs given in the classification theorem of locally grid graphs. In those cases for which the minimum length of essential cycles or the number of cycles of this minimum length are different we have that both graphs are not Tutte equivalent, thus the relevance of the following result. Lemma 2.3 If Gis a locally grid graph with pq vertices, then the length lGof the shortest essential cycles and the number of these cycles are given in the following table: G lGnumber of essential cycles Tp,q min{p, q} q 2p p if p<q if p=q if p>q Tδ p,q min{p, q +δ} q q+p"q+δ−1 δ# p"q+δ−1 δ# if p<q+δ if p=q+δ if p>q+δ K0 p,q min{p, q +1} q 5q 4q if p<q+1 if p=q+1 if p>q+1 K1 p,q min{p, q} q q+1 1 if p<q if p=q if p>q K2 p,q min{p, q} q q+2 2 if p<q if p=q if p>q Sp,q min{2p, q} 2p$p−1 j=0 "q−1 j# q(q−p)"2p−1 p# 2q if p≤q≤2p if 2p≤q if q≤p Tutte uniqueness of locally grid graphs 41 Proof: The cases Tp,q,Tδ p,q and Ki p,q are proved in [4], where it is also shown that lSp,q =min(2p, q)andthatifq≤pthe number of shortest essential cycles is 2q.Hence,weareonlyleftwithtwocasesinwhich we are given lower bounds on the number of essential cycles of length lSp,q .Weareinterestedincalculatingtheexactnumber. Locally grid graphs with pq vertices are constructed by adding edges to the p×qgrid. These edges are called exterior edges. Essential cycles of shortest length are obtained by joining the two ends of an exterior edge by a path contained in the grid p×q.InSp,q we distinguish two cases. Case 1 If 2p≤q,everyexterioredgeoftheform{(0,i),(p−1,i−p)} determines "2p−1 p#essential cycles of length 2p.Wehaveq−pedges of this kind and each of them can use up to qdifferent vertices, therefore the number of essential cycles of length 2pis q(q−p)"2p−1 p#. Case 2 If p≤q≤2p,{(0,i),(i, q −1)}and {(i, 0),(p−1,q−p+i)} with 0 ≤i≤p−1generate"q i#essential cycles of length q.These edges can use up to pdifferent vertices, hence the number of essential cycles of length qis 2p$p−1 j=0 "q−1 j#.! Theorem 2.4 Let p, q ≥6verify the following conditions: a) p"q+δ−1 δ#(=2 nfor n∈N. b) pq (=p#q#for all p#,q#≥6with p=q+δ=q#+δ#<p #and q+p"p−1 δ#=p#"p−1 δ##. Then Tδ p,q is Tutte unique for all δ≤p/2. Proof: Let p, q ≥6andGbe a graph with T(G;x, y)=T(Tδ p,q,x,y). By Lemma 2.1, Gis a locally grid graph, hence Ghas to be isomorphic to exactly one of the following graphs: Tp",q",Tδ" p",q",Ki p",q",Sp",q".Weprove that Gis isomorphic to Tδ" p",q"with p=p#,q=q#and δ=δ#assuming that Gis isomorphic to each one of the previous graphs and obtaining acontradictioninallthecasesexceptintheaforementionedcase. In [4] Tp,q was shown to be Tutte unique, thus we can consider δ>0and Gnot isomorphic to Tp",q". 42 D. Garijo, A. M´arquez and M.P. Revuelta Case 1 Suppose G∼ =K0 p",q".ByLemma2.2,lTδ p,q =lK0 p",q"and the number of shortest essential cycles has to be the same in both graphs. Case 1.1 lTδ p,q =p,lK0 p",q"=p#with p<q+δand p#<q #+1. As a result of Lemma 2.2, p=p#and q=q#.Ouraimistoprove that the number of edge sets with rank qand size q+1isdifferentfor each graph. This would lead to a contradiction since this number is the coefficient of xqyq+1 in the rank-size generating polynomial. If Tδ p,q has kessential cycles of length q(δ>1) or k+pq (δ=1), then K0 p,q would have k+4qsuch cycles. Therefore if we can show that there exits a bijection between edge sets with rank qand size q+1that are not essential cycles, we would have proved what we want. For every rwith 0 ≤r≤q−2denotebyErthe set {((i, r),(i, r + 1)) ; 0 ≤i≤p−1}.LetAbe an edge set that is not an essential cycle with rank qand size q+1inTδ p,q.Defines(A)asmin{r∈[0,q−2] ; A∩Er=∅}.IfA⊂E(Tδ p,q)theminimumalwaysexits. Foreveryrwith 0≤r≤q−2wedefinethebijection,ϕrbetween {A⊆E(Tδ p,q)|r(A)= q,|A|=q+1,s(A)=r}and {A⊆E(K0 p,q)|r(A)=q,|A|=q+1,s(A)= r}as follows: If A⊂E(Tδ p,q), ϕr(A)=∪{ψ(((i, j),(i#,j#))); ((i, j),(i#,j#)) ∈A} where ψ((h, k)) =        (h, ) k)if j#=q−1,j =0 (h, k)if j, j#∈[0,r] () h, ) k)ifr+1≤j, j#≤q−1 with h=(i, j), k=(i#,j#), ) h=(p−1−i+δ, j)and) k=(p−1−i#+δ, j#). Case 1.2 lTδ p,q =p,lK0 p",q"=p#=q#+1withp<q+δor lTδ p,q = q+δ<p,lK0 p",q"=p#with p#<q #+1. The contradiction in these two cases is produced due to the equality of shortest essential cycles, number of these cycles and number of vertices on each graph. Case 1.3 lTδ p,q =p,lK0 p",q"=q#+1withp<q+δand q#+1<p #. To obtain a contradiction, we are going to prove that there are more edge-sets with rank q#+2 and size q#+3inTδ p,q than in K0 p,q.Basically, we are going to follow the same procedure that was developed in [4]. The previous sets can be classified into three groups: 1.- Normal edge-sets (they are edge-sets that do not contain any essential cycle). Tutte uniqueness of locally grid graphs 43 2.- Sets containing an essential cycle of length q#+1andtwoother edges (Figure 5a). 3.- Essential cycles of length q#+3(Figures5band6). a) b) A A AA B B Figure 5: a) A set of edges in K0 p",q"containing an essential cycle of length q#+1 andtwo other edges. b)Essential cycles of length q#+3in Tδ p,q. A A A A Figure 6: Essential cycles of length q#+3inK0 p",q" (1) By Corollary 16 of [4] we know that Tδ p,q and K0 p",q"have the same number of normal edge-sets with rank q#+2andsizeq#+3that do not contain a cycle of length four. We are going to prove that the number of normal edge-sets with rank q#+2andsizeq#+3containing acycleoflengthfourisgreaterinTδ p,q than in K0 p",q". Again by Corollary 16 of [4], the number of edge-sets with rank q#+1andsizeq#+2containing acycle of lengthfouristhesamein both graphs, call it sq"+1.Addoneedgetoeachofthesesetsinorder to obtain a set with rank q#+2andsizeq#+3. Thissetcanbeoneof the following types depending on which edge we are adding: (a) A normal edge set with rank q#+2. (b) A normal edge set containing two non essential cycles and having rank q#+1. (c) An edge set containing an essential cycle of length q#+1anda non essential cycle of length four. Let A(G), B(G)andC(G)(whereGis either Tδ p,q or K0 p",q"), the number of edge-sets in Gthat belong to the groups A, B and C respec- 50 D. Garijo, A. M´arquez and M.P. Revuelta We will get a contradiction if we prove that "q#−1 δ#<2 p"−1 ! j=0 "q#−1 j#. q#≤2p#⇒[(q#−1)/2] ≤p#−1 then ∃j0∈[0,p #−1],"q#−1 [(q#−1)/2]#"q#−1 j0# "q#−1 δ#≤"q#−1 [(q#−1)/2] #<2 p"−1 ! j=0 "q#−1 j#.! Theorem 2.5 K0 p,q is Tutte unique for all p, q ≥6. Proof: Let p, q ≥6andGagraphwithT(G;x, y)=T(K0 p,q;x, y). Due to Lemma 2.1 and Theorem 2.4, Ghas to be isomorphic to exactly one of the following graphs: Ki p",q",Sp",q".WearegoingtoprovethatGis isomorphic to K0 p",q"with p=p#,q=q#. Suppose Gisomorphic to K0 p",q"then lTδ p,q =lK0 p",q"and the number of shortest essential cycles has to be the same in both graphs. We just have to study the case in which lK0 p,q =p<q+1,lK0 p",q"=q#+1with p#>q #+1. Thisis sobecause, if lK0 p,q =q+1<pand lK0 p",q"=p# with p#<q #+1thereasoningwouldbeanalogousandinthesecasesit is easy to verify that the number of vertices and the length of shortest essential cycles can not coincide in both graphs. If lK0 p,q =p<q+1, lK0 p",q"=q#+1with p#>q #+1we can show that the number of edge-sets with rank q#+2andsizeq#+3isdifferentin K0 p,q and K0 p",q".Weomittheproofbecauseitusesthesamearguments as those in case 1.3. Suppose G∼ =K1 p",q".Sincepis even and p#odd, all the cases in which the length of shortest essential cycles in K0 p,q is pand in K1 p",q"is p#are proved. By Lemma 2.3 we know that the number of shortest essential cycles in K0 p,q is always bigger than one, hence we obtain a contradiction in all those cases in which the number of shortest essential cycles in K1 p",q" is one. Therefore we just have to study two cases: lK0 p,q =q+1<p, lK1 p",q"=p#<q #and lK0 p,q =q+1<p,lK1 p",q"=p#=q#.Inthefirst Tutte uniqueness of locally grid graphs 51 case we obtain a contradiction by proving that the number of edge-sets with rank p#+1andsize p#+2isdifferent in each graph (following the same reasoning as in case 1.3 of Theorem 2.4). In the second case we show that if p#=q#=q+1, pq =p#q#,pare even and p#is odd it must then be the case that q#is even. By Lemmas 2.2 and 2.3, T(K0 p,q;x, y)(=T(K2 p",q";x, y)ifp#>q #,thereforeGis not isomorphic to K2 p",q".Followingthesamereasoningasincase1.1ofTheorem2.4 we show that it cannot be that lK0 p,q =p<q+1andlK2 p",q"=p#<q #. We just specify the bijection between {A⊆E(K0 p,q)|r(A)=q,|A|= q+1,s(A)=r}and {A⊆E(K2 p",q")|r(A)=q,|A|=q+1,s(A)=r}. If A⊂A(K0 p,q), ϕr(A)=∪{ψ(((i, j),(i#,j#))); ((i, j),(i#,j#)) ∈A} where ψ((h, k)) =        (h, ) k)if j#=q−1,j =0 (h, k)if j, j#∈[0,r] () h, ) k)ifr+1≤j, j#≤q−1 with h=(i, j), k=(i#,j#), ) h=(i+1,j)and) k=(i#+1,j#). On the other hand, we prove (as in case 1.3 of Theorem 2.4) that if lK0 p,q =q+1<pand lK2 p",q"=p#<q #the number of edge-sets of rank p#+1andsizep#+2isdifferentforeachgraph. The other four cases obtained by considering the possible combinations of the lengths of shortest essential cycles in K0 p,q and K2 p",q",are not possible since the length of shortest essential cycles, the number of these cycles and the number of vertices cannot coincide in both graphs. Finally, suppose G≃Sp",q". Case 1 If lK0 p,q =p<q+1,lSp",q"=q#with p#≤q#≤2p#we obtain acontradictionasfollows: p<q+1⇒p#≤q#<p #+1⇒p#=q#⇒p=q=p#=q#. q≥2q"−1=2 q−1. Case 2 lK0 p,q =p<q+1andlSp",q"=q#≤p#. As we did in case 1.3 of Theorem 2.4 we show that there are different number of edge-sets with rank q#+1andsizeq#+2inK0 p,q and Sp",q", hence these graphs do not have the same Tutte polynomial. Case 3 lK0 p,q =p=q+1andlSp",q"=2p#≤q#. 52 D. Garijo, A. M´arquez and M.P. Revuelta 2p#=p=q+1thenq#=2q.Since5q=q#(q#−p#)"2p#−1 p##we will obtain a contradiction if we prove that 5q<q #(q#−p#). q#(q#−p#)=2q(2q−(p/2)) = 4q2−pq =4q2−q(q+1)=q(3q−1) >q5 Case 4 lK0 p,q =q+1<pand lSp",q"=2p#≤q#. 2p#=q+1. 4q=q#(p#−q#)"2p#−1 p##≥2p#2"2p#−1 p##> 8p#>8p#−4=4(2p#−1) = 4q. Similarly as in the comparisons between K0 p,q and K2 p",q",therestof the cases cannot occur because the length of shortest essential cycles, the number of these cycles and the number of vertices do not coincide in both graphs given that q≥6. ! Theorem 2.6 The graph K1 p,q is Tutte unique for all p, q ≥6. Proof: The argument of this proof is basically the same as those followed in Theorems 2.4 and 2.5. Because of the Tutte uniqueness of Tδ p,q and K0 p,q we only have to prove that T(G;x, y)(=T(K1 p,q;x, y)withG∈ {K1 p",q"(except if p=p#and q=q#), K2 p",q",S p",q"}.Ineverycaseweare going to suppose that T(G;x, y)=T(K1 p,q;x, y)andwewillobtaina contradiction. Case 1 If G≃K1 p",q"it is easy to prove that the length of shortest essential cycles, the number of these cycles and the number of vertices only coincide if p=p#and q=q#. Case 2 If G≃K2 p",q",byLemmas2.2and2.3wegetacontradiction in all those cases for which the number of shortest essential cycles in K1 p,q is one or the number of shortest essential cycles in K2 p",q"is two. In the other cases a contradiction is reached because pis odd and p#is even. Case 3 If G≃Sp",q"we can consider p≤qbecause if p>qthe number of shortest essential cycles in K1 p,q is one and p, q ≥6. If lK1 p,q =p<qand lSp",q"=2p#≤q#or lSp",q"=q#with p#≤q#≤2p#, by Lemmas 2.2 and 2.3 it is easy to obtain a contradiction. The same is true if lK1 p,q =p=qand lSp",q"=q#with q#≤p#or lSp",q"=q#with p#≤q#≤2p#. If lK1 p,q =p<qand lSp",q"=q#≤p#we prove (as in previous cases) that there are different number of edge-sets with rank q#+1and Tutte uniqueness of locally grid graphs 53 size q#+2 in both graphs, hence they can not have the same Tutte polynomial. If lK1 p,q =p=qand lSp",q"=2p#≤q#,2p#=p=qthen q#=2q therefore q+1=q#(q#−p#)"2p#−1 p##=2q(q#−p#)"2p#−1 p##>q+1.! Theorem 2.7 The graph K2 p,q is Tutte unique for p, q ≥6. Proof: Due to Theorems 2.4, 2.5 and 2.6 we have to prove that T(G;x, y) (=T(K2 p,q;x, y)withG∈{K2 p",q"(except if p=p#and q=q#), Sp",q"} and pq =p#q#. By Lemmas 2.2 and 2.3, T(K2 p",q";x, y)(=T(K2 p,q;x, y)ifp(=p#and q(=q#because the length of shortest essential cycles, the number of these cycles and the number of vertices only coincide if p=p#and q=q#. If G≃Sp",q"we can assume that p≤qotherwise if q<p,K2 p,q has two shortest essential cycles and by Lemma 2.2 we obtain a contradiction. Case 1 If lK2 p,q =p<qand lSp",q"=q#≤p#we prove as in previous cases that the number of edge-sets with rank q#+1andsizeq#+2 is different in both graphs. Hence these two graphs cannot have the same Tutte polynomial, therefore we get a contradiction and Gcan not be isomorphic to Sp",q". Case 2 If lK2 p,q =p=qand lSp",q"=2p#≤q#then 2p#=p=qand q#=2qhence q+2=q#(q#−p#)"2p#−1 p##=2q(q#−p#)"2p#−1 p##>q+2. In the other four cases we obtain a contradiction because the length of shortest essential cycles, the number of these cycles and the number of vertices cannot coincide in both graphs. ! Theorem 2.8 The graph Sp,q is Tutte unique for p, q ≥6and 2q(= p#"q#+δ−1 δ#for all p#,q#with p#q#=pq and δ>0. Proof: Suppose that Sp,q is not Tutte unique. Then, by Theorems 2.4, 2.5, 2.6, 2.7 and Lemma 2.2 Sp,q is isomorphic to Sp",q"with p#(=p, q#(=qand pq =p#q#. 54 D. Garijo, A. M´arquez and M.P. Revuelta Case 1 If lSp,q =2p≤qand lSp",q"=q#with p#≤q#≤2p#,by Lemma 2.2 q#=2pand q=2p#then: q(q−p)"2p−1 p#=2p#(2p#−(q#/2))"q#−1 q#/2# >(2p#−(q#/2))"q#−1 q#/2#≥(2p#−p#)"q#−1 q#/2# =p#"q#−1 q#/2#> p"−1 ! j=0 "q#−1 j#. Hence, the number of shortest essential cycles is different in each graph and by Lemma 2.2 we have that Sp,q is not isomorphic to Sp",q". Case 2 If lSp,q =2p≤qand lSp",q"=q#≤p#then 2p=q#and q=2p#. 2q"=2 2p=2 2p−1 ! j=0 "2p−1 j#<2·2p"2p−1 p# ≤q"2p−1 p#<q(q−p)"2p−1 p#. We obtain a contradiction to the assumption that the number of shortest essential cycles is equal in both graphs. The other three cases are analogous to the previous ones. ! 3 Concluding Remarks We have shown that locally grid graphs are Tutte unique for p, q ≥6, but our techniques do not apply to p=3,4,5. An interesting open problem is to prove that the number p#"q#+δ−1 δ#is not a power of two. This would give a more general result about the Tutte uniqueness of Tδ p,q and Sp,q. Acknowledgement We are very grateful to I. Gitler of CINVESTAV-I.P.N. for carefully reviewing the manuscript and for making useful suggestions. Tutte uniqueness of locally grid graphs 55 D. Garijo Department of Applied Math., University of Sevilla, Avenida Reina Mercedes S/N, Sevilla C. P. 41012, Espa˜na. [email protected] A. M´arquez Department of Applied Math., University of Sevilla, Avenida Reina Mercedes S/N, Sevilla C. P. 41012, Espa˜na alma[email protected] M. P. Revuelta Department of Applied Math., University of Sevilla, Avenida Reina Mercedes S/N, Sevilla C. P. 41012, Espa˜na pasto[email protected] References [1] Brylawsky T.; Oxley J., The Tutte polynomial and its applications, Matroid Applications, Cambridge University Press, Cambridge, 1992. [2] Hall J.I., Locally Petersen graphs,J.GraphTheory,4(1980), 173- 187. [3] M´arquez de Mier A.; Noy M., On graphs determined by their Tutte polynomials,GraphsCombin.,20 (2004), 105-119. [4] M´arquez de Mier A.; Noy M.; Revuelta M.P., Locally grid graphs: Classification and Tutte uniqueness,Discr.Math.,266 (2003), 327-352. [5] Thomassen C., Tilings of the Torus and the Klein Bottle and vertex-transitive graphs on a fixed surface,Trans.Amer.Math. Soc., 323 (1991), 605-635.