On the maximal distance between triangular embeddings of a complete graph.

DOI10.1016/J.JCTB.2005.09.006MaRDI QIDQ2490841zbMATH OpenOpenAlexFDO

Authors Vladimir P. Korzhik

Publication date 18 May 2006

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2005.09.006

zbMATH Keywords

complete graphnonisomorphic embeddingstopological embeddingstriangular embedding

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Review text

The distance \(d(f,f')\) between two triangular imbeddings \(f\) and \(f'\) of a fixed complete graph is the minimum number \(t\) such that one can replace \(t\) faces in \(f\) with \(t\) new faces to obtain a triangular imbedding isomorphic to \(f'\). Of interest is the determination of the maximum value of this distance, as \(f\) and \(f'\) vary over all triangular imbeddings of a fixed complete graph. A simple calculation shows that \(T(s)=(4s+1)(12s+4)\) is the number of faces in a triangular imbedding of \(K_{12s+4}\). The author shows that, if \(s\geq 9\) and \(4s+1\) is prime and 2 is a primitive root modulo \((4s+1)\), then there are nonorientable triangular imbeddings \(f\) and \(f'\) of \(K_{12s+4}\) such that \(d(f,f')\geq (1/2)T(s)-O(s)\).

Recommendations

• On the minimal nonzero distance between triangular embeddings of a complete graph.
• A lower bound for the number of triangular embeddings of some complete graphs and complete regular tripartite graphs
• On the number of triangular embeddings of complete graphs and complete tripartite graphs
• A new approach to constructing exponentially many nonisomorphic nonorientable triangular embeddings of complete graphs
• Triangular embeddings of complete graphs (neighborly maps) with 12 and 13 vertices

Cites work

• Exponential families of non-isomorphic triangulations of complete graphs
• Exponential families of nonisomorphic nonorientable genus embeddings of complete graphs
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 3756556 (Why is no real title available?)
• scientific article; zbMATH DE number 3450230 (Why is no real title available?)
• On the minimal nonzero distance between triangular embeddings of a complete graph.
• On the number of nonisomorphic orientable regular embeddings of complete graphs
• Recursive constructions for triangulations

Cited in

(1)

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

This page was built for publication: On the maximal distance between triangular embeddings of a complete graph.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2490841)