Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: On the Theory Of Pfaffian Orientations. II. T -joins, k-Cuts, and Duality of Enumeration. | On the Theory Of Pfaffian Orientations. II. T-joins k-Cuts and Duality of Enumeration. Anna Galluccio Istituto di Analisi dei Sistemi ed Informatica - CNR viale Manzoni 30 00185 Roma ITALY galluccio@ yMartin Loebl Department of Applied Mathematics Charles University Malostranske n. 25 118 00 Praha 1 CZECH REPUBLIC loebl@ Received February 18 1998 Accepted May 22 1998. Abstract This is a continuation of our paper A Theory of Pfaffian Orientations I Perfect Matchings and Permanents . We present a new combinatorial way to compute the generating functions of T-joins and k-cuts of graphs. As a consequence we show that the computational problem to find the maximum weight of an edge-cut is polynomially solvable for the instances G w where G is a graph embedded on an arbitrary fixed orientable surface and the weight function w has only a bounded number of different values. We also survey the related results concerning a duality of the Tutte polynomial and present an application for the weight enumerator of a binary code. In a continuation of this paper which is in preparation we present an application to the Ising problem of three-dimensional crystal structures. Mathematical Reviews Subject Numbers 05B35 05C15 05A15 Supported by NATO-CNR Fellowship y Supported by DONET GACR 0194 and GAUK 194 1 THE ELECTRONIC .JOURNAL OF COmBINATORICS 6 1999 R7 1 1 Introduction This is a continuation of our paper A Theory of Pfaffian Orientations I Perfect Matchings and Permanents . We present a new combinatorial way to compute the generating functions of T-joins and k-cuts of graphs. A graph is a pair G V E where V is a set and E is a set of unordered pairs of elements of V. The elements of V are called vertices and those of E are called edges. If e xy is an edge then X y are called endvertices of e. In this paper V will always be finite G V E will always be a graph and xe will be a variable associated with each edge e of G. We let X xe e 2 E denote the .
