Algorithms for Derivation of Structurally Stable Hamiltonian Signed Graphs

Abstract

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.

Department(s)

Electrical and Computer Engineering

Keywords and Phrases

Algorithm; Computational Risk Management; Signed Graphs; Structural Balance

International Standard Serial Number (ISSN)

0020-7160

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2004 Taylor & Francis Group, All rights reserved.

Publication Date

01 Jan 2004

Link to Full Text

Share

 
COinS