Flips on homologous orientations of surface graphs with prescribed forbidden facial cycles

Weijuan Zhang and Jianguo Qian

Applied Mathematics and Computation, 2023, vol. 444, issue C

Abstract: Let G be a graph embedded on an orientable surface. Given a class C of facial cycles of G as a forbidden class, we give a sufficient and necessary condition such that an α-orientation (orientation with prescribed out-degrees) of G can be transformed into another by a sequence of flips on non-forbidden cycles and further give an explicit formula for the minimum number of such flips.

Keywords: Surface graph; Orientation; Flip; Homology (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300322008487
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:444:y:2023:i:c:s0096300322008487

DOI: 10.1016/j.amc.2022.127780

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().