Advances and Applications in Discrete Mathematics
Volume 24, Issue 2, Pages 129 - 142
(July 2020) http://dx.doi.org/10.17654/DM024020129 |
|
SIGNED COMPLETE GRAPHS ON SIX VERTICES AND THEIR FRUSTRATION INDICES
Deepak Sehrawat and Bikash Bhattacharjya
|
Abstract: A signed graph is a graph whose edges are labeled positive or negative. The sign of a cycle is the product of the signs of its edges. A signed graph is said to be balanced if the sign of every cycle is positive. The frustration index (and frustration number) of a signed graph is the smallest number of edges (and vertices) whose deletion makes the resulting signed graph balanced. In 2012, Zaslavsky [12] proved that upto switching isomorphism, there are six different signed Petersen graphs and he determined the frustration indices (and numbers) of all signed Petersen graphs. In this paper, we determine two things about complete graphs K6, with six vertices. First, we determine that there are sixteen signed K6's upto switching isomorphism. Second, we determine the frustration indices and the frustration numbers of all signed K6's. |
Keywords and phrases: signed graph, switching, switching isomorphism, frustration index, frustration number.
|
|
Number of Downloads: 203 | Number of Views: 527 |
|