Skip to main content
Algorithms for Derivation of Structurally Stable Hamiltonian Signed Graphs
International Journal of Computer Mathematics
  • Frank Harary
  • Meng-Hiot Lim
  • Amit Agarwal
  • Donald C. Wunsch, Missouri University of Science and Technology

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.

Electrical and Computer Engineering
Keywords and Phrases
  • Algorithm,
  • Computational Risk Management,
  • Signed Graphs,
  • Structural Balance
Document Type
Article - Journal
Document Version
File Type
© 2004 Taylor & Francis Group, All rights reserved.
Publication Date
Publication Date
01 Jan 2004
Citation Information
Frank Harary, Meng-Hiot Lim, Amit Agarwal and Donald C. Wunsch. "Algorithms for Derivation of Structurally Stable Hamiltonian Signed Graphs" International Journal of Computer Mathematics (2004) ISSN: 0020-7160
Available at: