A class of solutions to the gossip problem. III (Q791539): Difference between revisions

[For part I see ibid. 39, 307-326 (1982, Zbl 0497.05037), for part II see ibid. 40, 87-113 (1982; Zbl 0497.05038)]. This article completes a three part series on the gossip problem. The author begins with a five page synopsis of the material developed in his first two articles. The heart of this article deals with the enumeration of so-called ''NOHO-graphs''. He concludes with some comments about related questions. Given n people, each knowing a unique item of information, the standard gossip problem asserts that at least \(2n-4\) calls are needed to exchange all the gossip. If the calls of a minimum sequence are viewed as the edges of a graph, the graphs that can occur are precisely all connected graphs containing a four cycle and at most \(2n-4\) edges. The author adds the restriction that no one hears his own information and calls the resulting graphs NOHO-graphs. For n odd, the NOHO restriction makes the task impossible in any number of calls, but, surprisingly, for n even \(2n-4\) calls still suffice. But NOHO forces much additional structure on the graphs. Now no calls may be repeated, so each graph has precisely \(2n-4\) edges. When labelled in the order that the calls occur, the first n/2 form a perfect matching. The last n/2 form another perfect matching. The middle \(n-4\) edges induce two caterpillars of order \(n/2-1\) and two isolated points. Since catepillars are easy to count, there is incentive to try to count NOHO-graphs. However, not every NOHO-graph is uniquely generated, complicating the problem. There are reversals and reflections that are pretty straightforward. More subtle is an operation the author calls ''twisting''. After carefully characterizing the circumstances where twists can occur, he generates a sequence \(u_ m=(1,1,2,...)\) satisfying the recurrence \(u_ m= 3u_{m-1}=u_{m-3}.\) He finds that the number of nonisomorphic NOHO-graphs on \(2m+2\) vertices is \[ (u_ m+u_{\lceil m/2\rceil +1}+u_{\lfloor m/2\rfloor +1}- u_{\lfloor m/2\rfloor})/2. \]