Generalized Duke's theorem for signed Graphs
Abstract
Duke's interpolation theorem states that the orientable genera of a connected graph form an integer interval, and Stahl established the corresponding result for nonorientable embeddings. In 1991, Širáň showed that this interpolation property fails for signed graph embeddings: the Euler-genus spectrum of a signed graph may contain gaps. He subsequently asked whether all such gaps must occur at the lower end of the spectrum. In this paper, we establish a characterization of the Euler-genus spectrum of a connected signed graph. We prove that, for each parity class, the Euler genera form a step-two interval. Moreover, whenever both parity classes are nonempty, their maximum elements differ by one. As an consequence, if two consecutive integers k and k+1 belong to the Euler-genus spectrum, then every integer from k to the maximum Euler-genus also belongs to the spectrum, thereby answering Širáň's question affirmatively. Our proof uses the pre-signed graph representation of signed embeddings together with ordered adjacent-exchange operations and a matching interpretation of face numbers.
Related
- Nadler Theorem on Generalized Metric Spaces with Weighted Graphs
- Hadwiger's classification theorem on the sphere via signed orthoscheme decompositions
- Vizing's theorem for signed multigraphs
- Turán-type extremal problems for unbalanced signed graphs
- Modulo k-orientations of highly edge-connected signed graphs
BibTeX
@misc{chen2026generalized,
title = {{Generalized Duke's theorem for signed Graphs}},
author = {Yichao Chen and Yan Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.27628},
eprint = {2609.27628},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27628},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Generalized Duke's theorem for signed Graphs
AU - Yichao Chen
AU - Yan Yang
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.27628
UR - https://arxiv.org/abs/2609.27628
AB - Duke's interpolation theorem states that the orientable genera of a connected graph form an integer interval, and Stahl established the corresponding result for nonorientable embeddings. In 1991, Širáň showed that this interpolation property fails for signed graph embeddings: the Euler-genus spectrum of a signed graph may contain gaps. He subsequently asked whether all such gaps must occur at the lower end of the spectrum. In this paper, we establish a characterization of the Euler-genus spectrum of a connected signed graph. We prove that, for each parity class, the Euler genera form a step-two interval. Moreover, whenever both parity classes are nonempty, their maximum elements differ by one. As an consequence, if two consecutive integers k and k+1 belong to the Euler-genus spectrum, then every integer from k to the maximum Euler-genus also belongs to the spectrum, thereby answering Širáň's question affirmatively. Our proof uses the pre-signed graph representation of signed embeddings together with ordered adjacent-exchange operations and a matching interpretation of face numbers.
ER -