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):

• West,Douglas B.

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:

• *GRAPHS
• *INFORMATION THEORY
• PERMUTATIONS
• HAMILTONIAN FUNCTIONS

Subject Categories:

• Numerical Mathematics
• Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE