Geodesic
On the theory of Pfaffian orientations. II: \(T\)-joins, \(k\)-cuts, and duality of enumeration
The electronic journal of combinatorics, Tome 6 (1999)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/1439
Classification : 05A15, 05C30
Mots-clés : generating function, perfect matching, Pfaffian, \(T\)-join, \(k\)-cut 
@article{10_37236_1439,
     author = {Anna Galluccio and Martin Loebl},
     title = {On the theory of {Pfaffian} orientations. {II:} {\(T\)-joins,} \(k\)-cuts, and duality of enumeration},
     journal = {The electronic journal of combinatorics},
     year = {1999},
     volume = {6},
     doi = {10.37236/1439},
     zbl = {0909.05006},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1439/}
}
TY  - JOUR
AU  - Anna Galluccio
AU  - Martin Loebl
TI  - On the theory of Pfaffian orientations. II: \(T\)-joins, \(k\)-cuts, and duality of enumeration
JO  - The electronic journal of combinatorics
PY  - 1999
VL  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1439/
DO  - 10.37236/1439
ID  - 10_37236_1439
ER  - 
%0 Journal Article
%A Anna Galluccio
%A Martin Loebl
%T On the theory of Pfaffian orientations. II: \(T\)-joins, \(k\)-cuts, and duality of enumeration
%J The electronic journal of combinatorics
%D 1999
%V 6
%U http://geodesic.mathdoc.fr/articles/10.37236/1439/
%R 10.37236/1439
%F 10_37236_1439
Anna Galluccio; Martin Loebl. On the theory of Pfaffian orientations. II: \(T\)-joins, \(k\)-cuts, and duality of enumeration. The electronic journal of combinatorics, Tome 6 (1999). doi: 10.37236/1439

Cité par Sources :