Investigating the existence and the regularity of Logarithmic Harary Graphs

This paper studies the existence and the regularity of Logarithmic Harary Graphs (LHGs). This study is motivated by the fact that these graphs are employed for modeling the communication topology to support efficient flooding in the presence of link and node failures when considering an initial arbitrary number of nodes n. Therefore, the capability to identify graph constraints that allow the construction of LHGs for the largest number of pairs (n,k) (where k is the desired degree of connectivity to be tolerant to failures) becomes of primary importance. The paper presents several results in that direction. We introduce a graph constraint, namely K-PASTED-TREE, that allows the construction of a LHG for every pair (n,k) such that n≥2k. Secondly we present another graph constraint for LHG, namely K-DIAMOND, which is equivalent to K-PASTED-TREE in terms of capability to construct LHGs for any pair (n,k). The interest of K-DIAMOND lies in the fact that, for a given k, K-DIAMOND allows us to construct more regular graphs than K-PASTED-TREE does. A k-regular graph shows the minimal number of links required by a k-connected graph, leading to minimal flooding cost. The paper formally shows, in particular, that there are an infinite number of pairs (n,k), such that there exists a k-regular LHG for the pair (n,k) that satisfies K-DIAMOND and does not satisfy K-PASTED-TREE.