Frustration-critical signed graphs

Abstract

A signed graph $(G,\Sigma )$ is a graph $G$ together with a set $\Sigma \subseteq E(G)$ of negative edges. A circuit is positive if the product of the signs of its edges is positive. A signed graph $(G,\Sigma )$ is balanced if all its circuits are positive. The frustration index $l(G,\Sigma )$ is the minimum cardinality of a set $E\subseteq E(G)$ such that $(G-E,\Sigma -E)$ is balanced, and $(G,\Sigma )$ is $k$-critical if $l(G,\Sigma )=k$ and $l(G-e,\Sigma -e)<k$, for every $e\in E(G)$. We study decomposition and subdivision of critical signed graphs and completely determine the set of $t$-critical signed graphs, for $t\le 2$. Critical signed graphs are characterized. We then focus on non-decomposable critical signed graphs. In particular, we characterize the set $S^{\ast }$ of non-decomposable $k$-critical signed graphs not containing a decomposable $t$-critical signed subgraph for every $t\le k$. We prove that $S^{\ast }$ consists of cyclically 4-edge-connected projective-planar cubic graphs. Furthermore, we construct $k$-critical signed graphs of $S^{\ast }$ for every $k\ge 1$.