No CrossRef data available.
Article contents
A short proof of a recent theorem of G. Szekeres
Published online by Cambridge University Press: 09 April 2009
Extract
The purpose of this note is to apply the work of Kasteleyn (1967) on the enumeration of I-factors of a graph to derive a quick proof of a theorem of Szekeres (1973). In the following, G is understood to be a finite, directed graph. If u, v are adjacent vertices of G, we denote by (u, v) an edge of G directed from u to v. Let{f1, f2,…, fm} be a set of 1-factors of G, and for all i write where n is half the number of vertices of G. (Here we regard a 1-factor as a set of edges). Then Kasteleyn associates with fi a plus sign if ui1vi1ui2vi2…uinvin is an even permutation of u11v11u12v12…u1nv1n, and a minus sign otherwise. The symmetric difference of two 1-factors is a collection of circuits, called alternating circuits. An alternating circuit of G is said to be clockwise even if the number of its edges that are directed in agreement with the clockwise sense is even; otherwise it is clockwise odd. Since the length of any alternating circuit is even, these definitions are not dependent on the sense designated as clockwise. It follows from the work of Kasteleyn that two given 1-factors in a directed graph agree in sign if and only if the number of clockwise even alternating circuits in their symmetric difference is even.
- Type
- Research Article
- Information
- Copyright
- Copyright © Australian Mathematical Society 1976