Pith. sign in

REVIEW 3 minor 19 references

On the maximum and negative frustration indices of graphs

T0 review · 0 major / 3 minor · reviewed 2026-06-27 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The all-negative signature does not always achieve the maximum frustration index over all possible signatures

desk verdict Classifies maximizers for fans/wheels and refutes three Zaslavsky conjectures via explicit constructions and case analysis. read the letter →

arxiv 2606.11108 v1 pith:R6FNVUBX submitted 2026-06-09 math.CO

Maximilien Gadouleau , Huiying Zeng This is my paper · ORCID
classification math.CO
keywords frustrationindexsignedgraphsbalancedfanwheelmaximumZaslavskyconjectures
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper compares the frustration index under the all-negative signing to the highest frustration index attainable by any choice of signs on the same graph. It places several families into three categories: those where the all-negative signing fails to reach the maximum, those where it reaches the maximum but not uniquely, and those where it reaches the maximum uniquely. For fan graphs and wheel graphs the authors give a complete description of every maximizing signature together with their counts. The work also identifies graph classes in which the frustration index equals the maximum number of edge-disjoint negative triangles and disproves three conjectures of Zaslavsky.

What carries the argument

The frustration index of a signed graph, defined as the minimum number of edges whose deletion leaves every remaining cycle positive.

What would settle it

A concrete graph in one of the families where the frustration index under all-negative signs differs from the enumerated maximum, or a signed graph in the claimed classes whose frustration index is strictly smaller than its maximum number of edge-disjoint negative triangles.

Watch

Extended reading notes

Core claim

For certain graphs the all-negative signature does not maximize the frustration index, while for others it does so either uniquely or non-uniquely; the maximizers for fans and wheels are fully described, and in multiple classes the frustration index coincides with the size of a maximum set of edge-disjoint negative triangles, disproving three conjectures of Zaslavsky.

Load-bearing premise

That the standard deletion definition of the frustration index applies directly and that the studied families illustrate the full range of possible behaviors.

Editorial extensions

If this is right

  • For fan graphs the signatures achieving the maximum frustration index are completely characterized and counted.
  • For wheel graphs the signatures achieving the maximum frustration index are completely characterized and counted.
  • Both chordal and non-chordal graphs appear in each of the three scenarios.
  • In several graph classes the frustration index equals the number of edge-disjoint negative triangles.
  • Three conjectures of Zaslavsky on the frustration index are false.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The equality between frustration index and edge-disjoint negative triangles may supply a practical computational shortcut for triangle-dense graphs.
  • Extending the fan and wheel characterizations could make the maximum frustration index tractable for additional recursively defined families.
  • Network-balance applications that seek the most imbalanced signing may need to search beyond the all-negative case.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 3 minor

Summary. The manuscript compares the frustration index of the all-negative signing to the maximum frustration index attainable over all signings of a given undirected graph. It partitions several families (apex trees, fan graphs, wheel graphs, complete split graphs) into three scenarios: the all-negative signing fails to maximize the index, maximizes it non-uniquely, or maximizes it uniquely; both chordal and non-chordal examples are supplied for each scenario. Complete characterizations and enumerations of the maximizing signings are given for the fan and wheel families, several classes are shown to realize frustration index equal to the number of edge-disjoint negative triangles, and three conjectures of Zaslavsky are refuted by explicit counterexamples whose frustration indices are computed directly from the definition.

Significance. If the explicit constructions and case analyses hold, the work supplies concrete classifications, full enumerations for two infinite families, and direct refutations of three open conjectures. The combinatorial approach—relying on exhaustive casework on hubs/rims for fans (§3) and wheels (§4) together with deletion-set computations—provides verifiable, parameter-free results that advance the structural understanding of the frustration index.

minor comments (3)
  1. [§3] §3 (fan graphs): the enumeration of maximizing signatures is complete but the proof of uniqueness of the listed cases would benefit from an explicit statement that all other signings on the rim yield strictly lower frustration index.
  2. The three refuted Zaslavsky conjectures are identified only by number in the text; a one-sentence restatement of each conjecture immediately before its counterexample would improve readability.
  3. Table captions for the small-order exhaustive checks (if present) should state the precise range of orders examined so that the scope of the computational verification is immediately clear.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the detailed and positive summary of our work, including the recognition of the classifications, enumerations, and refutations of Zaslavsky's conjectures. The recommendation of minor revision is noted; however, the report contains no specific major comments or requested changes.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified

full rationale

The paper's claims rest on explicit constructions, exhaustive case analysis for specific graph families (apex trees, fans, wheels, complete split graphs), and direct computation of frustration indices from the standard definition (minimum edges to delete to balance all cycles). Characterizations for fans and wheels enumerate maximizers via casework on hubs and rims; refutations of Zaslavsky conjectures use concrete counterexamples. No parameters are fitted and called predictions, no self-definitional loops, and no load-bearing self-citations reduce any result to its inputs by construction. The work is self-contained combinatorial enumeration.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The paper rests on the standard definition of signed graphs and the frustration index; no free parameters, ad-hoc axioms or invented entities are introduced beyond the usual combinatorial setting.

assumptions (2)
  • standard math A cycle is positive if the product of its edge signs is +1; a signed graph is balanced if every cycle is positive.
    Invoked in the opening paragraph as the definition of balance.
  • standard math The frustration index equals the minimum number of edges whose deletion yields a balanced signed graph.
    Used throughout as the central quantity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the maximum and negative frustration indices of graphs." pith.science (2026). https://pith.science/paper/R6FNVUBX

@misc{pith2026260611108,
  author       = {Pith},
  title        = {Pith review of: On the maximum and negative frustration indices of graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R6FNVUBX}},
  note         = {Machine review of arXiv:2606.11108}
}
abstract

A signed graph is a graph with signatures ($+1$ or $-1$) on its edges. A cycle is called positive if the product of its edge signatures is positive, and a signed graph is called balanced if each cycle in it is positive. The frustration index is the minimum number of edges whose deletion makes the signed graph balanced, which is considered to be a measurement of the imbalance of the signed graph. In this paper, we compare the frustration index of the all-negative signature with the maximum frustration index of all possible signatures on the unsigned graph. We classify some families of graphs into three scenarios: the all-negative signature does not maximise the frustration index, the all-negative signature maximises the frustration index non-uniquely, and the all-negative signature maximises the frustration index uniquely. For all three scenarios, we can exhibit chordal and non-chordal graphs alike. The classes we consider include apex trees, fan graphs, wheel graphs, and complete split graphs. Moreover, for the families of fan graphs and wheel graphs, we fully characterise and count the signatures maximising the frustration index. Throughout our study, we exhibit different classes of signed graphs for which the frustration index equals the number of edge-disjoint negative triangles. Moreover, as part of our study, we are able to refute three conjectures of Zaslavsky on the frustration index.

Figures

Figures reproduced from arXiv: 2606.11108 by the authors.

Figure 1
Figure 1. Counterexample Σ to Conjecture 7 The signed graph Σ is formed by connecting two non-adjacent vertices in a minimum signed wheel graph (W5, σ) in the switching class of −W5. Since l(−W5) = 3, we have l(Σ) ≥ 3 (and since Σ only has three negative edges, we obtain l(Σ) = 3). Additionally, it is not hard to check that p −(Σ) = 2, while p△(Σ) = p(Σ) = 3. Therefore, p −(Σ) < min(l(Σ), p△(Σ)). In fact, Σ is planar and thus… view at source ↗
Figure 2
Figure 2. Two subcases of Case 32.1 Case 32.2. T ⊆ V (K5). In this case, |Σ[S]| = K1 ∨ S3. According to Corollary 13 and Theorem 14, l(Σ) ≤ 9. Suppose that l(Σ) = 9, and Σ is minimum. According to the discussion in Case 32.1, there cannot be a positive triangle with two vertices in V (K5) and one vertex in V (K3). For a vertex v ∈ V (K3), v must be negatively adjacent to exactly one vertex in {a, b}, exactly one vertex in {b,… view at source ↗
Figure 3
Figure 3. Another signature maximising the frustration index of [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 2 canonical work pages

  1. [1]

    Harary, On the measurement of structural balance

    F. Harary, On the measurement of structural balance. Behavioral Science, 4(1959). 316-323

    1959

  2. [2]

    Harary, On the notion of balance of a signed graph

    F. Harary, On the notion of balance of a signed graph. Michigan Mathematical Journal, 2(1953). 143-146

    1953

  3. [3]

    Zaslavsky, Graphs, gain graphs, and geometry aka signed graphs and their friends

    T. Zaslavsky, Graphs, gain graphs, and geometry aka signed graphs and their friends. Binghamton University; 2014. Available from: https://people.math.binghamton.edu/zaslav/Oldcourses/581.F14/course-notes- chapter2.pdf[Accessed 27th October 2025] 17 Figure 3: Another signature maximising the frustration index ofS 3 4

    2014

  4. [4]

    Petersdorf

    M. Petersdorf. Einige Bemerkungen ¨ uber Vollst¨ andige Bigraphen. Wissenschaftliche Zeitschrift der Technischen Hochschule Ilmenau. 12 (1966). 257-260

    1966

  5. [5]

    D.B. West. Introduction to Graph Theory. Vol. 2. Upper Saddle River: Prentice hall, 2001

    2001

  6. [6]

    H. L. Bodlaender, K. Jansen. On the complexity of the maximum cut problem. Nordic Journal of Computing, 7(1). 14-31

  7. [7]

    Iacono, F

    G. Iacono, F. Ramezani, N. Soranzo, et al. Determining the distance to monotonicity of a biolog- ical network: a graph-theoretical approach. IET Systems Biology, 4(2010). 223-235

    2010

  8. [8]

    Zaslavsky

    T. Zaslavsky. Negative (and positive) circles in signed graphs: A problem collection. AKCE International Journal of Graphs and Combinatorics, 2018, 15(1): 31-48

    2018

Show all 19 references
  1. [9]

    Zaslavsky

    T. Zaslavsky. Signed graphs. Discrete Applied Mathematics, 1982, 4(1): 47-74

    1982

  2. [10]

    Katai, S

    O. Katai, S. Iwai. Studies on the balancing, the minimal balancing, and the minimum balancing processes for social groups with planar and nonplanar graph structures. Journal of Mathematical Psychology, 1978, 18(2), 140-176

    1978

  3. [11]

    Sol´ e, T

    P. Sol´ e, T. Zaslavsky. A coding approach to signed graphs. SIAM Journal on Discrete Mathemat- ics, 1994, 7(4), 544-553

    1994

  4. [12]

    G. S. Bowlin. Maximum frustration in bipartite signed graphs. The Electronic Journal of Com- binatorics, 2012, 19(4), 10-10

    2012

  5. [13]

    F. Martin. Frustration and isoperimetric inequalities for signed graphs. Discrete Applied Mathe- matics, 2017, 217, 276-285

    2017

  6. [14]

    Sehrawat, B

    D. Sehrawat, B. Bhattacharjya. Maximum Frustration in Signed Generalized Petersen Graphs. Indian Journal of Discrete Mathematics, 2019, 5(2), 77-93

    2019

  7. [15]

    S. Aref, A. J. Mason, M. C. Wilson. A modeling and computational study of the frustration index in signed networks. Networks, 2020 75(1), 95-110

    2020

  8. [16]

    Diaz-Diaz, E

    F. Diaz-Diaz, E. Candellone, M. A. Gonz´ alez-Casado, E. Fraxanet, A. Vendeville, I. Ferri, A. S. Teixeira. Signed Networks: theory, methods, and applications. arXiv preprint arXiv:2511.17247, 2025

    2025

  9. [17]

    S. Chen, J. Li, Z. Wang. Frustration indices of signed subcubic graphs. arXiv preprint arXiv:2511.15226, 2025. 18

    2025

  10. [18]

    Shahul Hameed, K

    K. Shahul Hameed, K. Biju, Z. Stanic. Spectral measures of balance for signed graphs. Aus- tralasian Journal of Combinatorics, 2025 93(1), 198-210

    2025

  11. [19]

    S. Wu, U. Manber. Path-matching problems. Algorithmica, 1992 8(1), 89-101. 19

    1992

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.