J Austral Math Soc Ser A 47 pp391--398, 1989.

Graphs Associated with Triangulations of Lattice Polygons

Duane DeTemple and Jack M. Robertson

Abstract

Two graphs, the edge crossing graph E and the triangle graph T are associated with a simple lattice polygon. The maximal independent sets of vertices of E and T correspond to the triangulations of the polygon into fundamental triangles. Properties of E and T are derived including a formula for the size of the maximal independent sets in E and T. It is shown that T is a factor graph of edge-disjoint 4-cycles, which gives corresponding geometric information, and is a partition graph as recently defined by the authors and F. Harary.

1980 AMS Subject Classification (1985 Revision): 05C99, 51M05, 52A43

Browse the article

Authors

Duane DeTemple

Jack M. Robertson

Department of Pure and Applied Mathematics, Washington State University, Pullman, Washington 99164-2930, U.S.A.