Balancing signed graphs

AbstractA signed graph based on F is an ordinary graph F with each edge marked as positive or negative. Such a graph is called balanced if each of its cycles includes an even number of negative edges. Psychologists are sometimes interested in the smallest number d=d(G) such that a signed graph G may be converted into a balanced graph by changing the signs of d edges. We investigate the number D(F) defined as the largest d(G) such that G is a signed graph based on F. We prove that 12m−nm≤D(F)≤12m for every graph F with n vertices and m edges. If F is the complete bipartite graph with t vertices in each part, then D(F)≤12t2−ct32 for some positive constant c