Distance Between α-Orientations of Plane Graphs by Facial Cycle Reversals  

作　　者：Wei Juan ZHANG Jian Guo QIAN Fu Ji ZHANG 

机构地区：[1]School of Mathematical Sciences, Xiamen University [2]School of Mathematical Sciences, Xinjiang Normal University

出　　处：《Acta Mathematica Sinica,English Series》2019年第4期569-576,共8页数学学报（英文版）

基　　金：Supported by National Natural Science Foundation of China(Grant Nos.11471273 and 11561058)

摘　　要：Cycle reversal had been shown as a powerful method to deal with the relation among orientations of a graph since it preserves the out-degree of each vertex and the connectivity of the orientations. A facial cycle reversal on an orientation of a plane graph is an operation that reverses all the directions of the edges of a directed facial cycle. An orientation of a graph is called an α-orientation if each vertex admits a prescribed out-degree. In this paper, we give an explicit formula for the minimum number of the facial cycle reversals needed to transform one α-orientation into another for plane graphs.Cycle reversal had been shown as a powerful method to deal with the relation among orientations of a graph since it preserves the out-degree of each vertex and the connectivity of the orientations. A facial cycle reversal on an orientation of a plane graph is an operation that reverses all the directions of the edges of a directed facial cycle. An orientation of a graph is called an α-orientation if each vertex admits a prescribed out-degree. In this paper, we give an explicit formula for the minimum number of the facial cycle reversals needed to transform one α-orientation into another for plane graphs.

关 键 词：α-Orientation FACIAL CYCLE REVERSAL DISTANCE plane graph 

分 类 号：O157.5[理学—数学]