Optimally restricted edge connected elementary Harary graphs.

Abstract: An edge subset of a connected graph is a -restricted edge cut if is disconnected, and every component of has at least vertices. The -restricted edge connectivity of G, denoted by , is the cardinality of a minimum -restricted edge cut. By the current studies on , it can be seen that the larger is, the more reliable the graph is. Hence one expects to be as large as possible. A possible upper bound for is defined as and is connected , where is the number of edges with one end in and the other end in , and is the subgraph of induced by . A graph is called -optimal if . A natural question is whether there exists a graph which is -optimal for any . In this paper, we show that except for two cases, the elementary Harary graph has this property. [Copyright &y& Elsevier]