# Accession Number:

## ADA066099

# Title:

## A Class of Solutions to the Gossip Problem.

# Descriptive Note:

## Technical rept.,

# Corporate Author:

## STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

# Personal Author(s):

# Report Date:

## 1979-01-01

# Pagination or Media Count:

## 64.0

# 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. The 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. Author

# Descriptors:

# Subject Categories:

- Numerical Mathematics
- Cybernetics