Critically 3-frustrated signed graphs

C. Cappello, R. Naserasr, E. Steffen, Z. Wang, ArXiv:2304.10243 (2023).

No fulltext has been uploaded.
Preprint | English
Cappello, ChiaraLibreCat; Naserasr, Reza; Steffen, EckhardLibreCat ; Wang, Zhouningxin
Extending the notion of maxcut, the study of the frustration index of signed graphs is one of the basic questions in the theory of signed graphs. Recently two of the authors initiated the study of critically frustrated signed graphs. That is a signed graph whose frustration index decreases with the removal of any edge. The main focus of this study is on critical signed graphs which are not edge-disjoint unions of critically frustrated signed graphs (namely non-decomposable signed graphs) and which are not built from other critically frustrated signed graphs by subdivision. We conjecture that for any given k there are only finitely many critically k-frustrated signed graphs of this kind. Providing support for this conjecture we show that there are only two of such critically 3-frustrated signed graphs where there is no pair of edge-disjoint negative cycles. Similarly, we show that there are exactly ten critically 3-frustrated signed planar graphs that are neither decomposable nor subdivisions of other critically frustrated signed graphs. We present a method for building non-decomposable critically frustrated signed graphs based on two given such signed graphs. We also show that the condition of being non-decomposable is necessary for our conjecture.
Publishing Year
Journal Title

Cite this

Cappello C, Naserasr R, Steffen E, Wang Z. Critically 3-frustrated signed graphs. arXiv:230410243. Published online 2023.
Cappello, C., Naserasr, R., Steffen, E., & Wang, Z. (2023). Critically 3-frustrated signed graphs. In arXiv:2304.10243.
@article{Cappello_Naserasr_Steffen_Wang_2023, title={Critically 3-frustrated signed graphs}, journal={arXiv:2304.10243}, author={Cappello, Chiara and Naserasr, Reza and Steffen, Eckhard and Wang, Zhouningxin}, year={2023} }
Cappello, Chiara, Reza Naserasr, Eckhard Steffen, and Zhouningxin Wang. “Critically 3-Frustrated Signed Graphs.” ArXiv:2304.10243, 2023.
C. Cappello, R. Naserasr, E. Steffen, and Z. Wang, “Critically 3-frustrated signed graphs,” arXiv:2304.10243. 2023.
Cappello, Chiara, et al. “Critically 3-Frustrated Signed Graphs.” ArXiv:2304.10243, 2023.


Marked Publications

Open Data LibreCat


arXiv 2304.10243

Search this title in

Google Scholar