ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 25 (2025) #P2.05
https://doi.org/10.26493/1855-3974.3023.c45
(Also available at http://amc-journal.eu)
Upper embeddability of graphs and products of
transpositions associated with edges*
Shuhei Tsujie †
Department of Mathematics, Hokkaido University of Education,
Asahikawa, Hokkaido 070-8621, Japan
Ryo Uchiumi
Department of Mathematics, Graduate School of Science, Osaka University,
Toyonaka, Osaka 560-0043, Japan
Received 4 December 2022, accepted 12 April 2024, published online 13 March 2025
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 counterexample 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.
Math. Subj. Class. (2020): 05C25, 05C10, 57M15
*The authors wish to thank Professor Sachiko Saito for her valuable comments about topics of topology. The
authors would also like to express their deepest appreciation to the anonymous referee for careful reading and
pointing out a deficiency in a proof.
†Corresponding author.
E-mail addresses: tsujie.shuhei@a.hokkyodai.ac.jp (Shuhei Tsujie), uchiumi.ryou.1xu@ecs.osaka-u.ac.jp
(Ryo Uchiumi)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 25 (2025) #P2.05
https://doi.org/10.26493/1855-3974.3023.c45
(Dostopno tudi na http://amc-journal.eu)
Zgornja vložljivost grafov in produkti
transpozicij, pridruženih povezavam*
Shuhei Tsujie †
Department of Mathematics, Hokkaido University of Education,
Asahikawa, Hokkaido 070-8621, Japan
Ryo Uchiumi
Department of Mathematics, Graduate School of Science, Osaka University,
Toyonaka, Osaka 560-0043, Japan
Prejeto 4. decembra 2022, sprejeto 12. aprila 2024, objavljeno na spletu 13. marca 2025
Povzetek
V danem grafu vsaki povezavi pridružimo transpozicijo, ki zamenja krajišči. Če določi-
mo linearno ureditev na množici povezav, dobimo permutacijo točk grafa. Dénes je dokazal,
da je ta permutacija polna ciklična permutacija za vsako linearno ureditev, če in samo če je
graf drevo.
V tem članku karakterizramo grafe, ki imajo linearno ureditev, za katero je pridružena
permutacija polna ciklična permutacija v smislu grafovskih vložitev. Poleg tega podamo
protiprimer za Edenino vprašanje o ureditvi povezav, katere pridružena permutacija je iden-
titeta.
Ključne besede: Popolna ciklična permutacijska ureditev, zgornje vložljiv graf, 2-celična vložitev,
rotacijski sistem.
Math. Subj. Class. (2020): 05C25, 05C10, 57M15
*Avtorji se zahvaljujejo profesorici Sachiko Saito za njene dragocene komentarje o topoloških temah. Radi
bi izrazili globoko hvaležnost tudi neznanemu recenzentu za natančno branje in opozorilo na pomanjkljivost v
dokazu.
†Kontaktni avtor.
E-poštna naslova: tsujie.shuhei@a.hokkyodai.ac.jp (Shuhei Tsujie), uchiumi.ryou.1xu@ecs.osaka-u.ac.jp
(Ryo Uchiumi)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/