论文标题
在具有规定的禁止面部电路的表面图的同源方向上翻转
Flips on homologous orientations of surface graphs with prescribed forbidden facial circuits
论文作者
论文摘要
令$ g $为嵌入在可定向表面上的图。给定$ g $的面部电路的$ {\ cal c} $作为禁止的班级，我们给出了足够的条件，因为$α$ - 方向（带有处方的$ g $的方向）可以通过一系列在非固定循环上的范围来转换为另一个插件，并为exputition提供了一个expient的数量。我们还通过定义有向图$ {\ bf d}（{\ cal c}）$来考虑所有$α$方向之间的连接，即$ {\ cal c} $ - 禁止翻转图。我们表明，如果$ {\ cal c} \ not = \ emptySet $，则$ {\ bf d}（{\ cal c}）$具有$ | o（g，{\ cal c}）| $组件，每个零件是分布式lattice lattice latte latte latte latte lattice latte的封面图，$ | o（g，c c c cal cal）除$ {\ cal c} $中的逆时针面电路。如果$ {\ cal c} = \ emptySet $，则$ {\ bf d}的每个组件（{\ cal c}）$都很强地连接。这概括了Felsner和Propp的相应结果，即$ {\ cal C} $由单个面部电路组成。
Let $G$ be a graph embedded on an orientable surface. Given a class ${\cal C}$ of facial circuits of $G$ as a forbidden class, we give a sufficient-necessary condition for that an $α$-orientation (orientation with prescribed out-degrees) of $G$ can be transformed into another by a sequence of flips on non-forbidden circuits and further give an explicit formula for the minimum number of such flips. We also consider the connection among all $α$-orientations by defining a directed graph ${\bf D}({\cal C})$, namely the ${\cal C}$-forbidden flip graph. We show that if ${\cal C}\not=\emptyset$, then ${\bf D}({\cal C})$ has exactly $|O(G,{\cal C})|$ components, each of which is the cover graph of a distributive lattice, where $|O(G,{\cal C})|$ is the number of the $α$-orientations that has no counterclockwise facial circuit other than that in ${\cal C}$. If ${\cal C}=\emptyset$, then every component of ${\bf D}({\cal C})$ is strongly connected. This generalizes the corresponding results of Felsner and Propp for the case that ${\cal C}$ consists of a single facial circuit.
