Counting balanced signed graphs using marked graphs

Abstract

A graph in which each line is designated as either positive or negative is called a signed graph S . The sign of a cycle in S is a product of the signs of its lines. A signed graph in which every cycle is positive is called balanced . This concept was introduced by Harary in ( 3 ) and the following characterisation of balanced signed graphs was given.