The Open UniversitySkip to content
 

On the minimal nonzero distance between triangular embeddings of a complete graph

Grannell, M.J.; Griggs, T.S.; Korzhik, V.P. and Siran, Jozef (2003). On the minimal nonzero distance between triangular embeddings of a complete graph. Discrete Mathematics, 269(1-3) pp. 149–160.

DOI (Digital Object Identifier) Link: http://dx.doi.org/10.1016/S0012-365X(02)00751-3
Google Scholar: Look up in Google Scholar

Abstract

Given two triangular embeddings f and f′ of a complete graph K and given a bijection : V(K)→V(K), denote by M() the set of faces (x,y,z) of f such that ((x),(y),(z)) is not a face of f′. The distance between f and f′ is the minimal value of |M()| as ranges over all bijections between the vertices of K. We consider the minimal nonzero distance between two triangular embeddings f and f′ of a complete graph. We show that 4 is the minimal nonzero distance in the case when f and f′ are both nonorientable, and that 6 is the minimal nonzero distance in each of the cases when f and f′ are orientable, and when f is orientable and f′ is nonorientable.

Item Type: Journal Article
ISSN: 0012-365X
Extra Information: Some of the symbols may not have transferred correctly into this bibliographic record and/or abstract.
Keywords: Topological embedding; Complete graph
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Item ID: 2901
Depositing User: Terry Griggs
Date Deposited: 20 Jun 2006
Last Modified: 02 Dec 2010 19:48
URI: http://oro.open.ac.uk/id/eprint/2901
Share this page:

Altmetrics

Scopus Citations

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk