Balancing signed graphs |
| |
Authors: | J Akiyama D Avis V Chvátal H Era |
| |
Institution: | Department of Mathematics, Nippon Ika University, Kawasaki 211, Japan;Department of Computer Science, McGill University, Montreal, Quebec, Canada;Department of Mathematics, Tokai University, Hiratsuka, Japan |
| |
Abstract: | A 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 for every graph F with n vertices and m edges. If F is the complete bipartite graph with t vertices in each part, then for some positive constant c. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|