Metraipolis › archive › dc_fb9470ca92ea

Finiteness of Non-decomposable Critically Frustrated Signed Graphs — arXiv:2611.06017

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.06017
License (as archived): CC0-1.0
Archived: 2026-11-05T18:28:27.003Z
SHA-256 of the archived text: 22411c5c61d9771b3e49b8aef54d8c3bf3dc531446c0c7bad277e7e53d19635a
Stable URL of this page: https://metraipolis.com/documento/dc_fb9470ca92ea

How to cite

Finiteness of Non-decomposable Critically Frustrated Signed Graphs — arXiv:2611.06017 — arXiv (en), https://arxiv.org/abs/2611.06017 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fb9470ca92ea (Metraipolis archive dc_fb9470ca92ea, sha256 22411c5c61d9771b3e49b8aef54d8c3bf3dc531446c0c7bad277e7e53d19635a)

BibTeX

@misc{dcfb9470ca92ea,
  title = {Finiteness of Non-decomposable Critically Frustrated Signed Graphs — arXiv:2611.06017},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.06017},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fb9470ca92ea; sha256 22411c5c61d9771b3e49b8aef54d8c3bf3dc531446c0c7bad277e7e53d19635a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06017. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A signed graph $(G,\sigma)$ is a graph $G$ with a signature $\sigma$ 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, \sigma)$ is the minimum number of negative edges among all signatures switching equivalent to $\sigma$. 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\leq 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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.06017 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:18:33.997Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).