1.
Upper embeddability of graphs and products of transpositions associated with edgesShuhei Tsujie,
Ryo Uchiumi, 2025, original scientific article
Abstract: Given a graph, we associate each edge with the transposition which exchanges the endvertices. Fixing a linear order on the edge set, we obtain a permutation of the vertices. Dénes proved that the permutation is a full cyclic permutation for any linear order if and only if the graph is a tree.
In this article, we characterize graphs having a linear order such that the associated permutation is a full cyclic permutation in terms of graph embeddings. Moreover, we give a counter example for Eden's question about an edge ordering whose associated permutation is the identity.
Keywords: full cyclic permutation ordering, upper-embeddable graph, 2-cell embedding, rotation system
Published in RUP: 21.10.2025; Views: 546; Downloads: 3
Full text (324,31 KB)
