Maximum Frustration in Signed Generalized Petersen Graphs

A $\mathit{\text{signed}}\mathit{\text{graph}}$ is a simple graph whose edges are labelled with positive or negative signs. A cycle is $\mathit{\text{positive}}$ if the product of its edge signs is positive. A signed graph is $\mathit{\text{balanced}}$ if every cycle in the graph is positive. The $\mathit{\text{frustration}}\mathit{\text{index}}$ of a signed graph is the minimum number of edges whose deletion makes the graph balanced. The $\mathit{\text{maximum}}\mathit{\text{frustration}}$ of a graph is the maximum frustration index over all sign labellings. In this paper, first, we prove that the maximum frustration of generalized Petersen graphs $P_{n,k}$ is bounded above by $\lfloor \frac{n}{2}\rfloor +1$ for $\gcd (n,k)=1$, and this bound is achieved for $k=1,2,3$. Second, we prove that the maximum frustration of $P_{n,k}$ is bounded above by $d\left\lfloor \frac{n}{2d} \right\rfloor + d + 1$,where$\gcd(n,k)=d\geq2$.