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: https://doi.org/10.1016/S0012-365X(02)00751-3

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.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI