Maximum Frustration in Signed Generalized Petersen Graphs

MaRDI QIDQ6318699zbMATH OpenFDO

Authors Deepak Sehrawat, Bikash Bhattacharjya

Publication date 14 May 2019

Abstract: A extit{signed graph} is a simple graph whose edges are labelled with positive or negative signs. A cycle is extit{positive} if the product of its edge signs is positive. A signed graph is extit{balanced} if every cycle in the graph is positive. The extit{frustration index} of a signed graph is the minimum number of edges whose deletion makes the graph balanced. The extit{maximum 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 $leftlfloorfracn2ightfloor+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 $dleftlfloorfracn2dightfloor+d+1$, where $gcd(n,k)=dgeq2$.

This page was built for publication: Maximum Frustration in Signed Generalized Petersen Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6318699)