Upper Embeddability of Graphs and Products of Transpositions Associated with Edges

arXiv2211.05422MaRDI QIDQ6507015FDOQ6507015

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'enes 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.

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Relations of low-dimensional topology with graph theory (57M15)

This page was built for publication: Upper Embeddability of Graphs and Products of Transpositions Associated with Edges

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