论文标题
图形的上部嵌入性和与边缘相关的换位的产物
Upper Embeddability of Graphs and Products of Transpositions Associated with Edges
论文作者
论文摘要
给定图，我们将每个边缘与交换端动的换位相关联。将线性订单固定在边缘集合，我们获得顶点的排列。 Dénes证明，当且仅当图形是树时，当且仅当图形时，置换是任何线性顺序的完整循环排列。 在本文中，我们表征具有线性顺序的图形，以使相关的置换在图嵌入方面是完整的循环排列。此外，我们为伊甸园的问题提供了一个反示例，该问题关于边缘订购的相关排列是身份。
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.
