[net.misc] Hamilton Cycle of the Net?

donn (03/13/83)

Now that we have some better data on the topology of the net, thanks to
the efforts of various people such as Steven Bellovin, maybe we can
answer some silly trivia questions such as, what is the longest path on
the net?  Remember, news (unlike mail) never goes through the same
machine twice, so if there was a route that took you through every
machine on the net then it would be a Hamilton cycle (according to my
vague recollection of graph theory -- correct me if I'm wrong).  It's a
fairly simple undertaking to measure the longest path in one's current
batch of news so I did it on our local machine.  It turns out have 29
machines in it (the path is hyphenated for the benefit of those with
brain-damaged terminals):

    sdchema!sdcsvax!philabs!cmcl2!floyd!vax135!ariel!houti!lime-
	   !we13!otuxa!ll1!sb1!burl!mhuxv!mhuxm!mhuxh!mhuxa!mhuxt-
	   !eagle!harpo!seismo!hao!hplabs!sri-unix!cca!decvax-
	   !utzoo!utcsrgv!newman

Notice that it crosses the country from coast to coast at least three
times...  and ends up in Canada.  I guess the question I want to ask
is, what is the maximal subgraph of the net that has a Hamilton cycle?
I.e., what is the upper bound on the path length of a news item?

Donn Seeley  UCSD Chemistry Dept. RRCF  ucbvax!sdcsvax!sdchema!donn

honey (03/14/83)

is sdchema!donn willing to let me use his cycles to solve this np-complete
problem?
	peter honeyman

jcz (03/15/83)

References: sdchema.445


	Other Trivia Questions:

		What netnews path is the longest in miles?

		What netnews path cost the most (Phone charges)?

		which site is the most populated? (only >500 need apply)

		What city has the greatest concentration of (non-btl,
		including btl) sites?

		Which site pays the most to Ma Bell? (decvax?)

		How many different transport protocols actually makeup
		the net?  (What are they?)

	Some of these questions should pinpoint the more inmportant sites,
	at least one is designed to help me figure out what kind of
	automatic DBMS for site directories would be useful.

						John Carl Zeigler
						North Carolina State Univ.
						ACC Champs! (NCAA?)