1.
Upper embeddability of graphs and products of transpositions associated with edgesShuhei Tsujie,
Ryo Uchiumi, 2025, izvirni znanstveni članek
Opis: 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.
Ključne besede: full cyclic permutation ordering, upper-embeddable graph, 2-cell embedding, rotation system
Objavljeno v RUP: 21.10.2025; Ogledov: 534; Prenosov: 2
Celotno besedilo (324,31 KB)
