トップページ - 横浜国立大学学術情報リポジトリ

全文

(1)POLYNOMIAL INVARIANTS OF EMBEDDINGS OF GRAPHS ON CLOSED SURFACES Seiya NEGAMI Department of Mathematics, Faculty of Education. Yokohama National University 156 Tokiwadai, Hodogaya-Ku, Yokohama 240, Japan Email: [email protected]. 1. Introduction The author has shown in [1] that the following formulas determine a well-defined polynomialf< G)= .f( G;t, x,y ) with three variables t, x,y for each graph G.. (i) f(Kn)=t" (n >- 1).. (ii) f(G)=xf(G(e)+yf(Gme) foranyedgeeEE(G). Here G-e and eve are the graphs obtained from G by deleting and contracting an edge eE E (G ), respectively. In particular if e is a loop, then (1/fe = G-e . Thus, f(G )=. (x +y >f(Gme) for a loop e.Moreover,f< G)= (x +ty >f( Gfe) for a cut edge e. As is shown in [1],this polynomial f<G), called the Negamipolynomial here, gives us various combinatorial informations. For example, f( G) expands to. .f<G)=E tto(G-Y)xlE(G)-YlylYl YCE(G) where to(G) stands for the number of components of G.This implies that the coefficient oftjx iy IE(G)1-iin f(G) is equal to the number of those spanning subgraphs of G that. have precisely i edges and J' components. (Oxley has proved in [2] that the,Negami polynomial is nearly equivalent to the Tutte polynomial.). In the same paper [1],the author has defined another polynomialf"(G) =f'"(G;t, x, y ), called the dualpolynomial, as one that satisfies the following conditions:. (i) .f'ts(Kn)=tn(n21).. (ii) f*(G)=(x+ty>IC"(G-e) ifeEE(G)isaloop. (iii).f'(G)=(x+y)f*(Gfe) ifeEE(G)isacutedge. (iv)f'"(G)=xf"(Grme)+yf*(Gfe)ifeEE(G)isneitheraloopnoracutedge..

(2) Seiya NEGAMI. 2. This polynomial .IP"(G) expands as follows.. f"(G)=tca(G)2 tB(GeX)xlXlylE(G)-Xl XCE(G) Here B(G) denotes the Betti number or the cycle rank of G and is equal to 1E(G)l -. 1V(G)1 + w(G). Comparing the expansions off(G) and of f"(G), we have. tca(G)'lV(G)lf<G;t,ty,x)=f'k･(G;t,x,y) Although f"(G) can be determined by the only combinatorial structure of (Z it is related to the embeddings of planar graphs on the sphere.. THEOREM 1. Let G be a connected planar graph embedded on the sphere with dual G". 71hen:. f*(G)-f(G*).. This duality does not hold for graphs on other surfaces. Our purpose in this paper is to. reform the dual polynomial f"(G) so that this duality holds on any closed surface. Our. new polynomial h*(G), called the dual polynomial of G, is associated with a 2-cell embedding of a graph G on a closed surface F2･and we deform not only a graph G but also the surface F2 together to make recursive formuls for h*(G). (See the next section. for the precise definition of h"(G).) For this dual polYnomial h*(G), we have the following fact as we want.. ' THEOREM 2. Let G be a graph 2-cell embedded on a closed sui:face with dual G". 71hen:. h*(G)=f(G"). In particular when a graph is embedded on the sphere, h*(G) coincides with f*(G),. and hence Theorem 2 includes Theorem 1 as a special case. Moreover, we shall characterize the case when h*(G)=f"(G), as follows:. THEROEM 3. Let G be a graph 2-cell embedded on a closed sumbce F2. 71hen f*(G)= h"(G) ifand only ifeach component of F2 is homeomorphic to the sphere.. Suppose that G can be obtained as the union of two graphs H and K with only two. vertices u and v in common. Split G into H and K at lu,vland identify u and v in H with v and u in K, respectively. This deformation is called turning around two. vertices.(If u is isolated in K, then turning around (u,vl can be regarded as arrangement of blocks.) According to Whitney [6], two graphs are said to be 2isomorphic if they can be transformed into each other by a finite sequence of turning around two vertices, splitting or joining at one vertex and adding or deleting isolated. points. He showed that two graphs are 2'isomorphic if and only if there is a bijection.

(3) POLYNOMIAL INVARIANTS OF EMBEDDINGS OF GRAPHS ON CLOSED SURFACES. 3. between their edge sets which induces a bijection between the collections of their cycles. In today's terminology, his results can be rephrased that two graphs are 2isomorphic if and only if their cycle matroids are isomorphic. (See Section 3 for cycle matroids.). The author has proved in [1] that if G and G' are 2-isomorphic and have the same. number of components, then f(G)=f(G'), as an application of &71itting Formula for f(G ). Thus, roughly speaking, the Negami polynomial f(G) is a matroid invarinat. Our dual polynomial h"(G) also is a kind of a matroid invariant, but the matroid is not the. cycle matroid of G. We shall define a matroid associated with a 2-cell embedding of G,. called the boundary matroid of G, and show that 2-cell embeddings of graphs with isomorphic boundary matroids have the same dual polynomial in Section 3.. 2. Dualpolynomials Let G be a graph with a fixed 2-cell embedding on a closed surface F2. When G is. disconnected, also F2 is disconnected and each component of F2contains one component of G so that each face is a 2'cell. We keep any graph to be 2-cell embedded on a surface and forbid any deformation which destroys this rule. For example, we shall. not delete any cut edge eEE(O to get G-e. If we did, then G-e would have an annular region as its face.. e. ,. t t t t. 1 1. ,. .. .. "le bl". Figure 1: Shrinking a 2'sided loop on a surface. Let G'e be the embedded graph obtained from G by shrinking an edge eEE(G) to a point on the surface F2 when e has two distinct end points. When e is a loop and has an. annular neighborhood on F2 (such a loop is called a 2-sided loop), then we pinch the surface by shrinking e and split it at the resulting singularity to get G 'e (Figure 1). In. other words, cut open F2 along a loop e and cap off the resulting two boundary components with two 2-cells. This deformation separates F2 or cuts a handle of F2, according to whether or not splitting at the end point of e disconnects G.In this case, G 'e is not embedded on F2 and is not isomorphic to G/e as a graph. When e is a loop lying along the center line of a M6bius band (called a 1-sided loqp),. then shrinking of e to a point does not make any singularity of the surface. It only eliminates one cross cap from Fa and G 'e is 2-cell embedded there. To see this, cut open. F2 along the 1-sided loop e. Then I72 will have one hole and we can recover F2 by.

(4) Seiya NEGAMI. 4. ----. tt. tt tt. : , ss. e. ss. ss. ---.. s -d-------s. st s st ss1 st tt tl 1-: tl t t1 t" ts t ts t ts t --t---t tst st -t. -- -s. .. Figure 2 : Sh rinking a 1-sided loop on a surface identifying the antipodal pairs of pointsalong the resulting boundary. Shrinking the 1sided loop e shrinks this hole to a point, not changing the remaining part. (See Figure 2.) For example, if a loop e is an essential simple closed curve on the projective plane,. then shrinking of e deforms the projective plane into the sphere.. Using these two deformations G-e and G'e, we define the dualpolynomial h*(G) for G as such a one that satisfies the following three conditions. Here we think of Kh as. the union of n isolated points embedded on n spheres one by one.. (i) h*(Kn)=tn(n>-1). (ii) h"(G)=(x+y)h"(G'e)ifeEE(G)isincidenttoonlyoneface. (iii) h*(G)=xh*(G-e)+yh"(G'e)ifeEE(G)isincidenttotwodistinctfaces. Each edge eEE(G) looks incident to two faces locally, but those faces might be identical. In that case, deleting the edge e yields an annular region, which we forbid. That is the reason why G-e does not appear in (ii). It is not trivial that this definition. determines a unique polynomial for G. Our proof of Theorem 2 will show not only the duality but also the well-definedness of h*(G).. The following two formulas are what we are naturally anxious about and can be easily shown from the definition of h"(G).. THEOREM 4. ifagraph Gsplits into two disy'oinggraphs K and H; then. h*(G)=h*(K)h*(H). Proof. Use induction on1E(G)1. By (i), it is clear if lE(G)1 = O. Suppose that 1E(G)1>O. and that H has at least one edge eEE(H ). Then G -e =KU(H-e) and G'e= KU (H'e ). If e is incident to only one face, by (ii) and our induction hypothesis,. h"(G) = (x +y)h"(KU (H'e )) = (x +y)h"(K)h'(H'e ) = h" (K) × (x +y)h*(H'e ). =h*(K)h*(H).

(5) POLYNOMIAL INVARIANTS OF EMBEDDINGS OF GRAPHS ON CLOSED SURFACES. 5. If e is incident to two distinct faces, by (iii) and our induction hypothesi,s,. h"(G)=xh*(KU(H-e))+yh*(KU(H'e)) =xh*(K)h*(Hme)+yh*(K)h*(H'e) =h"(K)(xh*(H-e)+yh"(H'e)). =h*(K)h*(H) THEOREM5. lfeEE(G)isaloopboundingafaceofG,then h"(G) = (x +ty)h"(G 'e). Proof. Since e bounds a face, e is incident to two distinct faces and hence we can use (iii). Observe that G'e consists of G -e and Ki on the sphere. By Theorem4 and (iii),. h*(G)=xIi"(G "e) +ylfk(G -e)lik (Ki). Substitute h*(Ki)=t. If an edge e of G has two distinct ends, then contraction of e induces deletion of. the edge e" ofthe dual G" which crosses e at apoint. (Such an edge e* is said to be dual to e .) To make this duality hold for any loop, shrinking of edges is defined as above.. Observe the following lemma, adding G" to the pictures of Figures 1 and 2.. LEMMA6. Let G beagraph2-cellembeddedonaclosedsudece F2withdual G*and let eEE(G) and e* EE(G") be etdges qf G and qf G" dual to each other. 77zen. (G 'e )"= G -e". lf e is incident to two distinctfaces, then. (G -e )"= G"/e*. Proof of 71heorem 2. Let G be a graph 2'cell embedded on a closed surface I7a. We use. induction onIE(G)1. WhenIE(G)1 =O and IV(G)1 = n, then G must be equivalent to Kh embedded on n spheres and so is its dual G*.Thus, h*(G)=tn =f(G") by (i). Choose any edge eEE(G) and let e* EE(G ") be its dual edge. If e is incident to two distinct faces, then by our induction hypothesis and (iii), we have. f< G*) = xf(G"le ") + y f( G" -e"). =xh*(Gme)+yh*(G'e) = h*(G )..

(6) Seiya NEGAMI. 6. If both sides of e are incident to a single face, then e* is a loop incident to the vertex of G* in'the face. By our induction hypothesis and (ii),. f( G*) = (x+y )tf(G* -e"). = (x+g)h*(G'e). =h*(G ). i Proof of 71heorem 3. Let degtf(G*) and degtf"(G) denote the maximum degrees of f(G) andf"(G)in t.From the expansions of f(G) and of f*(G ), we can conclude the following formulas.. deg,f"(G)= B(G>+ to(G), deg,f(G*)= 1V(G")l Thus, if f*(G)= h(G)=f(G"), then the Euler number x(F2) can be given as follows:. x(F2)=1V(G)j-IE(G)1+1V(G*)1. -1V(G)I-IE(G)1+(B(G)+to(G)) -l V(G)1-IE(G)i+(IE(G)1-iV(G)1+2tu(G)) =2 ca (G) This implies that F2 is the union of w(G) spheres since the only sphere has Euler number 2, and the necessity follows.. '. If G is embedded on the sphere, then f'k(G)=f<G")=h*(G) by Theorems 1 and 2.. Thus, the sufficiency is clear. i 3. Boundary matroids Let G be a graph and c(G) the collection of all the cycles of G.Here we regard any cycle as a set of edges. Then C = C(G) satisfies the following two conditions, called. s} : the axioms ofcircuits. il. (i) C,=i=C,EC= C,(ZC, (ii) Ci=t C2Ec, eECinC2 t iC3Ec, C3CCiUC2-lel The matroid over E(G) with C (G) the collection of circuits is called the cycle matroid of. G and is denoted by M(G). (See [4] for general theory of matroids.) Let C*(G)be the collection of all the cocycles of G, that is, those cutsets that are minimal with respect to inclusion. Here a cutset is a set of edges, denoted by [S,S ],. which consists of all the edges joining S to S for a nonempty subset SCV(G) with nonempty complement S.A cut set [S,Slof G is a cocycle if and only if both S and S induce connected subgraphs in G.Then C *(G) also satisfies the axioms of circuits. The matroid over E(G) with C "(G) the collection of circuits is called the cocycle matroid of G. and is denoted by M"(G). The cocycle matroid M"(G) is the dual matroid of M(G)..

(7) POLYNOMIAL INVARIANTS OF EMBEDDINGS OF GRAPHS ON CLOSED SURFACES. 7. M*(G) = M(G)* Let G be a graph 2-cell embedded on a closed surface F2. A subset B of E(G) can be regarded naturally as an element of the 1-dimensional Z2'homology group Hi(F2; Z2) if B. induces a subgraph<B>in G each of whose vertex has even degree. Such a nonempty subset B of E(G) is called a boundary of G or of F2 if B is null'homologous on F2, that is,. [B]= O G Hi (F2;Z2), where [B]stands for the Z2'homology class of B in F2.. A nonempty subset B of E(G) is a boundary if and only if one can assign black or white to each region of<B>so that any two regions sharing an edge in B get different colors. (The reader unfamiliar to Z2-homology groups can use this as the definition of. boundaries.) Notice that the subgraph <B > may not be 2-cell embedded on F2 and may not be connected. Let B (G) be the collection of those boundaries of G that are minimal with respect to inclusion. Then B (G) satisfies"the axiom of circuits"; (i) is clear by the minimality of boundaries in B (G) and (ii) follows from the fact that. [BABr]= [B]+ [B']= O+O= OE H, (F2;Z,). for any two boundaries B and B', where BAB'= BUB' -BnB' is the symmetric difference of B and B'. We denote by B(G) the matroid over E(G) with B (G) the collection of circuits and call B(G) the boundaiy matroid of G.. For example, the set of edges which appear only once in the boundary walk of a face of G is a boundary if it is not empty. In particular if a face is bounded by a cycle, the cycle. belongs to B (G). Suppose that there exist n disjoint cycles placed on the torus in parallel so that each cycle cuts a handle of the torus. The set of edges on these n cycles, say B, is. a boundary if and only if and only if n is even in this case. Moreover, B belongs to B (G). if and only if n= 2. Note that the boundary matroid B (G ) of G depends on the embedding of G. THEOREM 7. Let G he a graph 2-cell embedded on a closed sudece with dual G". 77ien the boundary matroid B(G) of G is isomorphic to the cocycle matroid M"(G*) ojC G* via the natural bijection between E(G) and E(G*).. Proof Let ￠: E(G )->E(G") be the natural bijection which maps each edge e E E(G) to. its dual edge e"EE(G"). Let B be a boundary of G and SC V(G") the set of vertices which are contained in the black regions of B. Then ￠ (B)= [S, S ] and it is a cutset of G".. Conversely, let S C V(G") be a nonempty subset of V(G") with nonempty complement and paint each face of G with black or white according to whether or not it contains a vertex in S. Then B = ￠-i([S, S ]) is the set of edges which are incident to both black and. white faces and each region of B contains only black faces or only white faces of G. This implies that B is a boundary of G..

(8) Seiya NEGAMI. 8. IfBEB(G) is a minimal boundary of G, then ￠(B) is acocycle; otherwise, a proper subset B'of B would be mapped to a cocycle C EC "(G*) contained in ￠ (B) and. B' = ￠-i(C) would be a boundary of G by the above arguments, contrary to the minimality of B. Thus, ￠ induces an injection ￠:B(G) .C *(G*). Similary, for any coeycle CG c *( G*),. ￠-i(C)isaminimalboundaryofG.Therefore,￠:B(G).C*(G*)isabijection. COROLLARY 8. Let Gi and G2 be graphs 2-cell embedded on closed sudeces with duals Gi" and (I2", respectively. ff B(Gi)!fB(G),then M(Gi") !!!fM(G2").. Proof By the duality of cycle and cocycle matroids, M"(Gi*) or M*(G*) if and only if. M(Gi") 2I M( G2*). Thus, the corollary follows from Theorem 7. The following corollary shows that B(G) is a natural extension of M<G") in a sense.. COROLLARY 9. Let G he a connected graph embedded on the sphere with dual G*. 77zen:. B(G)= M( G) Proof In general, if a connected graph G is embedded on the sphere, then M(G) ! M*(G") via the natural bijection between edge sets. Thus, the corollary follows from. A closed curve is essential on a closed surface F2 if it does not bound any 2-cell in F2.. An embedding of G on 7, not homeomorphic to the sphere, is said to be n-representative if any essential closed curve on F2 which meets G in only vertices passes through at least. n vertices, according to the terminology in [3]. Two embedded graphs Gi and G2 on. surfaces Fi and F22,respectively, are said to be equivalent here if there is a homeomorphism h:Ff . Fi such that h(Gi)= Gz. Whitney showed in [5] that if the. cycle matroids of two 3-connected graphs are isomorphic, then the graphs are isomorphic. The following theorem on the boundary matroids corresponds to this fact:. THEOREM 10. Let Gi and G2 be 3-connected 3-representative graphs embedded on closed suifaces. lfB(Gi)2IB(G2), then their embeddings are equivalent.. Proof First observe that G is 3-connected and 3-representative if and only if so is G*. If. B(Gi)!B(G2), then M(Gi")!fM(G2*) by Corollary 8. By Whitney's result, the bijection ￠:(E (Gi"), C(Gi*)) . (E (G2*), (C(G2*)) induces a unique isomorphism between Gi' and G2" since they are 3-connected. In particular, the set of edges incident to each vertex of. Gi corresponds to a cycle of Gi" .This implies that ￠ induces a bijection between V(Gi). and V(G2), preserving the rotations around corresponding vertices. Therefore, not only. GiandG2areisomorphicasgraphsbutalsotheirembeddingsareequivalent. -.

(9) POLYNOMIAL INVARIANTS OF EMBEDDINGS OF GRAPHS ON CLOSED SURFACES. 9. The following is an easy consequence from the above arguments and is our goal in this section; our dual polynomial h"(G) is a boundary-matroid invariant for 2-cell embedded graphs on closed surfaces.. THEOREM 11. Let Gi and G2 be connectedgraphs 2-cell embeddedon closed sudeces. if B(Gi)2!B(G2), then h*(Gi) = h"(Gz).. '. Proof If B(Gi)2fB(G2), then M(Gi")!-!:M(G2*) and hence f(Gi*) = f(G2*)sincef(G) is a matroid invariant. By Theorem 2, we have. h*(G,)=f(G,*)= f(G2*)= h*(G2) i 4. Embeddings with the same dual polynomials Let G be a graph 2-cell embedded on a closed surface F2. Choose a subsurface E2 in pt. with one or two boundary components so that its boundary 0E2 meets G in at most two. vertices u, v E V(G) and that each component of0E2 contains at least one of these vertices. If there is such a subsurface E2 of jF2, then G splits into two subgraphs H and B. which contain only u and v in common and B=GnE2. Let h:E2- E2 be any autohomeomorphism on E2 with u and v fixed. Then HUh(B) is a new embedding of G on F2. This modification of an embedding is called a partial reversion around u and v and a local reversion if E2 is a 2'cell.. Now let E2 be a subsurface of F2 with connected boundary 0E2 so that 0E2 meets G in only one vertex u E V(G). Then G splits into two graphs B and H with B= GAE2 and B A H = (u l. Cut off E2 from F2 and cap off the resulting boundary with a 2-cell. Remove a. 2'cell from another corner at u and cap off the hole with E2 so that H and B are joined at. u. Then we get another embedding of G on a new surface homeomorphic to F2. This relocation of B (or E2) is called a partialJ'ump of B around u and a localjump if E2 is a 2' cell. Note that a partial jump can be realized as an iteration of partial reversions.. THEOREM12. LetGbeagraph2-cellembeddedonaclosedsumbceF2andGianother embedding obtainedfrom G by a partial reversion or a partialjump. 71hen h"(G) = h*(Gi).. Proof If G and Gi can be transformed into each other by a partial reversion or a partial. jump, then their duals G" and Gi" are 2-isomorphic and have the same number of. components.Thus,wehavef(G*)=f(Gi*)andhenceh*(G)=h"(Gi)byTheorem2. Any deformation of a 2'cell embedding of a graph which induces turning around two vertices of the dual on the surface preserves the dual polynomial h*(G) in general. On the sphere, such a deformation is nothing but a local reversion. On the other surfaces, turning around two vertices for the dual G* does not induce a partical reversion of the.

(10) 10 Seiya NEGAMI original graph G in general. We can conclude only that if G* admits turning around two. vertices u", v* E V(G*), then the two faces of G corresponding to u* and v* separate. G into two edge-disjoint subgraphs H and B, which may have two or more vertices in common. Observe that such a deformation of G" deforms G into a graph not isomorphic to G in most of cases except when it induces a partial reversion or a partial jump. Is there. another deformation of a 2-cell embedding of a graph which preserves both the dual polynomial h'(G) and the isomorphism type of G?. References [1] S. Negami, Polynomial invariants of graphs, Trans. Amer. Math. Soc. 299 (1987),. 601-622. [2] J.G. Oxley, A note on Negami's polynomial invariants for graphs, Discrete Math. 76 (1989), 279-281. [3] N. Robertson and R. Vitray, Representativity of surface embeddings, in: Algorithms. and Combinatorics 9, B. Korte, L. Lovasz, H.J. Pr6mel and A. Schrijver (Eds.), "Paths, Flows, and VLSI-Layout", Springer-Verlag, 1990, 293-328. [4] D.J.A. Welsh, "Matroid theory", London, New York, San Francisco, Academic Press (1976). [5] H. Whitney, Non-separable and planar graphs, Trans. Amer. Math. Soc. 34 (1932),. 339-362. [6] H. Whitney, 2-isomorphic graphs, Amer. J. Math. 55 (1933), 245-254..

(11)