BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-78-693
       ENTRY:: June 22, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: A class of solutions to the gossip problem
        TYPE:: Technical Report
      AUTHOR:: West, Douglas B.
        DATE:: November 1978
       PAGES:: 66
    ABSTRACT:: We characterize and count optimal solutions to the gossip
               problem in which no one hears his own information. That is,
               we consider graphs with n vertices where the edges have a
               linear ordering such that an increasing path exists from each
               vertex to every other, but there is no increasing path from
               any vertex to itself. Such graphs exist only when n is even,
               in which case the fewest number of edges is 2n-4, as in the
               original gossip problem. We characterize optimal solutions of
               this sort (NOHO-graphs) using a correspondence with a set of
               permutations and binary sequences. This correspondence
               enables us to count these solutions and several subclasses of
               solutions. The numbers of solutions in each class are simple
               powers of 2 and 3, with exponents determined by n. We also
               show constructively that NOHO-graphs are planar and
               Hamiltonian, and we mention applications to related problems.
       NOTES:: [Adminitrivia V1/Prg/19950622]
         END:: STAN//CS-TR-78-693