ALL GENERALIZED PETERSEN GRAPHS ARE UNIT-DISTANCE GRAPHS

作者：Zitnik Arjana^*; Horvat Boris; Pisanski Tomaz

来源：Journal of the Korean Mathematical Society, 2012, 49(3): 475-491.

DOI：10.4134/JKMS.2012.49.3.475

• unit-distance graph
• I-graph
• generalized Petersen graph
• graph representation
• degenerate representation
• graph isomorphism

In 1950 a class of generalized Petersen graphs was introduced by Coxeter and around 1970 popularized by Frucht, Graver and Watkins. The family of I-graphs mentioned in 1988 by Bouwer et al. represents a slight further albeit important generalization of the renowned Petersen graph. We show that each I-graph I(n, j, k) admits a unit-distance representation in the Euclidean plane. This implies that each generalized Petersen graph admits a unit-distance representation in the Euclidean plane. In particular, we show that every I-graph (n, j, k) has an isomorphic I-graph that admits a unit-distance representation in the Euclidean plane with a n-fold rotational symmetry, with the exception of the families I(n, j, j) and I(12m, m, 5m), m %26gt;= 1. We also provide unit-distance representations for these graphs.

• 出版日期2012-5