Flooding in dynamic graphs with arbitrary degree sequence

This paper addresses the flooding problem in dynamic graphs, where flooding is the basic mechanism in which every node becoming aware of a piece of information at step t$t$ forwards this information to all its neighbors at all forthcoming steps t^′>t$t^{\prime }>t$. We show that a technique developed in a previous paper, for analyzing flooding in a Markovian sequence of Erdös–Rényi graphs, is robust enough to be used also in different contexts. We establish this fact by analyzing flooding in a sequence of graphs drawn independently at random according to a model of random graphs with given expected degree sequence. In the prominent case of power-law degree distributions, we prove that flooding takes almost surely O(logn)$O(logn)$ steps even if, almost surely, none of the graphs in the sequence is connected. In the general case of graphs with an arbitrary degree sequence, we prove several upper bounds on the flooding time, which depend on specific properties of the degree sequence.     

Lower bounds for the broadcast problem in mobile radio networks

Summary.  In this paper, we prove a lower bound on the number of rounds required by a deterministic distributed protocol for broadcasting a message in radio networks whose processors do not know the identities of their neighbors. Such an assumption captures the main characteristic of mobile and wireless environments [3], i.e., the instability of the network topology. For any distributed broadcast protocol Π, for any n and for any D≦n/2, we exhibit a network G with n nodes and diameter D such that the number of rounds needed by Π for broadcasting a message in G is Ω(D log n). The result still holds even if the processors in the network use a different program and know n and D. We also consider the version of the broadcast problem in which an arbitrary number of processors issue at the same time an identical message that has to be delivered to the other processors. In such a case we prove that, even assuming that the processors know the network topology, Ω(n) rounds are required for solving the problem on a complete network (D=1) with n processors. Received: August 1994 / Accepted: August 1996     

New spectral lower bounds on the bisection width of graphs

The communication overhead is a major bottleneck for the execution of a process graph on a parallel computer system. In the case of two processors, the minimization of the communication can be modeled using the graph bisection problem. The spectral lower bound of λ₂|V|/4 for the bisection width of a graph is widely known. The bisection width is equal to λ₂|V|/4 iff all vertices are incident to λ₂/2 cut edges in every optimal bisection.

We present a new method of obtaining tighter lower bounds on the bisection width. This method makes use of the level structure defined by the bisection. We define some global expansion properties and we show that the spectral lower bound increases with this global expansion. Under certain conditions we obtain a lower bound depending on λ₂^β|V| with . We also present examples of graphs for which our new bounds are tight up to a constant factor. As a by-product, we derive new lower bounds for the bisection widths of 3- and 4-regular Ramanujan graphs.     

Robustness of regular ring lattices based on natural connectivity

It has been recently proposed that natural connectivity can be used to efficiently characterise the robustness of complex networks. The natural connectivity quantifies the redundancy of alternative routes in the network by evaluating the weighted number of closed walks of all lengths and can be seen as an average eigenvalue obtained from the graph spectrum. In this article, we explore both analytically and numerically the natural connectivity of regular ring lattices and regular random graphs obtained through degree-preserving random rewirings from regular ring lattices. We reformulate the natural connectivity of regular ring lattices in terms of generalised Bessel functions and show that the natural connectivity of regular ring lattices is independent of network size and increases with K monotonically. We also show that random regular graphs have lower natural connectivity, and are thus less robust, than regular ring lattices.     

Hamiltonicity in connected regular graphs

In 1980, Jackson proved that every 2-connected k-regular graph with at most 3k vertices is Hamiltonian. This result has been extended in several papers. In this note, we determine the minimum number of vertices in a connected k-regular graph that is not Hamiltonian, and we also solve the analogous problem for Hamiltonian paths. Further, we characterize the smallest connected k-regular graphs without a Hamiltonian cycle.     

Lower bounds for asynchronous consensus

Impossibility results and best-case lower bounds are proved for the number of message delays and the number of processes required to reach agreement in an asynchronous consensus algorithm that tolerates non-Byzantine failures. General algorithms exist that achieve these lower bounds in the normal case, when the response time of non-faulty processes and the transmission delay of messages they send to one another are bounded. Our theorems allow algorithms to do better in certain exceptional cases, and such algorithms are presented. Two of these exceptional algorithms may be of practical interest.     

Large independent sets in random regular graphs

We present algorithmic lower bounds on the size _sd$s_d$ of the largest independent sets of vertices in random d$d$-regular graphs, for each fixed d≥3$d\ge 3$. For instance, for d=3$d=3$ we prove that, for graphs on n$n$ vertices, _sd≥0.43475n$s_d\ge 0.43475n$ with probability approaching one as n$n$ tends to infinity.     

Bounds on the bisection width for random d -regular graphs

In this paper we provide an explicit way to compute asymptotically almost sure upper bounds on the bisection width of random d$d$-regular graphs, for any value of d$d$. The upper bounds are obtained from the analysis of the performance of a randomized greedy algorithm to find bisections of d$d$-regular graphs. We provide bounds for 5≤d≤12$5\le d\le 12$. We also give empirical values of the size of the bisection found by the algorithm for some small values of d$d$ and compare them with numerical approximations of our theoretical bounds. Our analysis also gives asymptotic lower bounds for the size of the maximum bisection.     

On a game in directed graphs

Inspired by recent algorithms for electing a leader in a distributed system, we study the following game in a directed graph: each vertex selects one of its outgoing arcs (if any) and eliminates the other endpoint of this arc; the remaining vertices play on until no arcs remain. We call a directed graph lethal if the game must end with all vertices eliminated and mortal if it is possible that the game ends with all vertices eliminated. We show that lethal graphs are precisely collections of vertex-disjoint cycles, and that the problem of deciding whether or not a given directed graph is mortal is NP-complete (and hence it is likely that no “nice” characterization of mortal graphs exists).