Similar Graphs: Characterization and Subclasses

Abstract

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.