Algorithms for Derivation of Structurally Stable Hamiltonian Signed Graphs
A graph Sp,q,n refers to a signed graph with p nodes and q edges with n being the number of negative edges. We introduce two theorems to facilitate identification of the complete set of balanced signed graph configurations for any p-node Hamiltonian signed graph in terms of p, q and n. This allows for the development of computational procedures to efficiently determine the structural stability of a signed graph. This is potentially useful for the planning and analysis of complex situations or scenarios which can be depicted as signed graphs. Through the application of the theorems, the state of balance of a signed graph structure or its affinity towards balance can be determined in a more time-efficient manner compared to any explicit enumeration algorithm.
F. Harary et al., "Algorithms for Derivation of Structurally Stable Hamiltonian Signed Graphs," International Journal of Computer Mathematics, Taylor & Francis Group, Jan 2004.
Electrical and Computer Engineering
Keywords and Phrases
Algorithm; Computational Risk Management; Signed Graphs; Structural Balance
Article - Journal
© 2004 Taylor & Francis Group, All rights reserved.