The Tenacity of the Harary Graphs

Abstract

As a network begins losing links or nodes, eventually there is a loss in its effectiveness. Thus, communication networks must be constructed to be as stable as possible, not only with respect to the initial disruption, but also with respect to the possible reconstruction of the network. Many graph theoretical parameters have been used to describe the stability of communication networks, including connectivity, integrity, toughness, tenacity, and binding number. Several of these deal with two fundamental questions about the resulting graph. How many vertices can still communicate? How difficult is it to reconnect the graph? For any fixed integers $n,p$, with $p\ge n+1$, Harary constructed classes of graphs $H_{n,p}$, that are $n$-connected with the minimum number of edges. Thus Harary graphs are examples of graphs with maximum connectivity. This property makes them useful to network designers and thus it is of interest to study the behavior of other stability parameters for the Harary graphs. In this paper, we study the tenacity of the Harary graphs.