Premium
Triangular embeddings of complete graphs (neighborly maps) with 12 and 13 vertices
Author(s) -
Ellingham M. N.,
Stephens Chris
Publication year - 2005
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.20048
Subject(s) - combinatorics , mathematics , simple (philosophy) , flexibility (engineering) , upper and lower bounds , order (exchange) , discrete mathematics , mathematical analysis , philosophy , statistics , epistemology , finance , economics
In this paper, we describe the generation of all nonorientable triangular embeddings of the complete graphs K 12 and K 13 . (The 59 nonisomorphic orientable triangular embeddings of K 12 were found in 1996 by Altshuler, Bokowski, and Schuchert, and K 13 has no orientable triangular embeddings.) There are 182,200 nonisomorphic nonorientable triangular embeddings for K 12 , and 243,088,286 for K 13 . Triangular embeddings of complete graphs are also known as neighborly maps and are a type of twofold triple system. We also use methods of Wilson to provide an upper bound on the number of simple twofold triple systems of order n , and thereby on the number of triangular embeddings of K n . We mention an application of our results to flexibility of embedded graphs. © 2005 Wiley Periodicals, Inc. J Combin Designs