Finiteness of Non-decomposable Critically Frustrated Signed Graphs
Abstract
A signed graph (G,σ) is a graph G with a signature σ labeling each edge with a positive or negative sign. Two signatures of G are switching equivalent if one is obtained from the other by sequentially changing the signs of all edges in an edge-cut. The frustration index of a signed graph $(G, σ)$ is the minimum number of negative edges among all signatures switching equivalent to σ. A signed graph is critically k-frustrated if it has frustration index k, and the removal of any edge decreases its frustration index. A critically k-frustrated signed graph is prime if it is irreducible and contains no two edge-disjoint negative cycles. Steffen and Naserasr et al. asked if there are only finitely many prime critically k-frustrated signed graphs for any positive integer k. The cases k≤ 3 were proved to be true by Cappello et al., and later, the cases k=4 and $5$ were verified by Z. Wang. In this paper, the author proves the conjecture by a topological argument.
Related
BibTeX
@misc{wang2026finiteness,
title = {{Finiteness of Non-decomposable Critically Frustrated Signed Graphs}},
author = {Zhiqian Wang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06017},
eprint = {2611.06017},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06017},
}
RIS
TY - UNPB
TI - Finiteness of Non-decomposable Critically Frustrated Signed Graphs
AU - Zhiqian Wang
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06017
UR - https://arxiv.org/abs/2611.06017
AB - A signed graph (G,σ) is a graph G with a signature σ labeling each edge with a positive or negative sign. Two signatures of G are switching equivalent if one is obtained from the other by sequentially changing the signs of all edges in an edge-cut. The frustration index of a signed graph $(G, σ)$ is the minimum number of negative edges among all signatures switching equivalent to σ. A signed graph is critically k-frustrated if it has frustration index k, and the removal of any edge decreases its frustration index. A critically k-frustrated signed graph is prime if it is irreducible and contains no two edge-disjoint negative cycles. Steffen and Naserasr et al. asked if there are only finitely many prime critically k-frustrated signed graphs for any positive integer k. The cases k≤ 3 were proved to be true by Cappello et al., and later, the cases k=4 and $5$ were verified by Z. Wang. In this paper, the author proves the conjecture by a topological argument.
ER -