Menu
In this paper, we introduce the concept of similar graphs. Similar graphs arise in the design of fault-tolerant networks and in load balancing of the networks in case of node failures. Similar graphs model networks that not only remain connected but also allow a job to be shifted to other processors without re-executing the entire job. This dynamic load balancing capability ensures minimal interruption to the network in case of single or multiple node failures and increases overall efficiency. We define a graph to be \((m, n)\)-similar if each vertex is contained in a set of at least \(m\) vertices, each pair of which share at least \(n\) neighbors. Several well-known classes of \((2, 2)\)-similar graphs are characterized, for example, triangulated, comparability, and co-comparability. The problem of finding a minimum augmentation to obtain a \((2, 2)\)-similar graph is shown to be NP-Complete. A graph is called strongly \(m\)-similar if each vertex is contained in a set of at least \(m\) vertices with the property that they all share the same neighbors. The class of strongly \(m\)-similar graphs is completely characterized.