J Austral Math Soc Ser A 50 pp248--257, 1991.

Operations Preserving the Pfaffian Property of a Graph

C. H. C. Little and F. Rendl

Abstract

Pfaffian graphs are those which can be orientated so that the 1-factors have equal sign, as calculated according to the prescription of Kasteleyn. We consider various operations on graphs and examine their effect on the Pfaffian property. We show that the study of Pfaffian graphs may be reduced to the case of subcubic graphs (graphs in which no vertex has degree greater than 3) or bricks (3-connected bicritical graphs).

1980 AMS Subject Classification (1985 Revision): 05C70

Browse the article

Authors

C. H. C. Little

Massey University, Palmerston North, New Zealand.

F. Rendl

Technische Universität Graz, Kopearnikusgasse 24, A-8010 Graz, Austria.