From: hiraga@Csli.Stanford.EDU (Yuzuru Hiraga)
Subject: Re: Circular graph problem
Organization: Stanford University CSLI
Date: Fri, 18 Dec 1992 16:27:26 GMT

In article <1992Dec16.113500.1157@client24.comlab.ox.ac.uk> mnewman@comlab.ox.ac.uk (Matthew Newman) writes:
>Consider circular graphs with N nodes, such that there is an integer
>at each node. Consider those integers K such that for some graph G
>each integer in [1..k] is the sum of integers at the nodes of some
>connected sub-graph G. For example with N=4 I can get K=11 with the
>following graph :     (1)--(2)
>                       |    | 
>                      (3)--(5) 
>
>and I can do better than this and get the maximum possible k=13 like
>this :     (1)--(2)    and like this:   (1)--(3)
>            |    |                       |    |
>           (4)--(6)                     (2)--(7)

The second one should be
  (1)--(3)
   |    |
  (7)--(2)

>and for N=8 I can get K=53 with 1-4-22-7-3-6-2-12- (where notationally
>the above graphs are 1-2-5-3- ; 1-2-6-4- ; 1-3-2-7- i.e. read round
>clockwise) which again is maximal.

K=53 should be K=57.

>The question is, what is the largest K I can get for a given N ?

First note that the upper bound for K is N^2-N+1 (easy to prove).
Eg. N=4 -> supK=13; N=8 -> supK=57

The following is from a Japanese math magazine, which considers
only this upper bound case.

[Takakazu Shimauchi, in "Suugaku Seminar" 1982.1]

The problem was presented by Pablo Manalastas (Philippines).
(Nagayoshi) Iwabori's conjecture is that:
  1) The [upper bound] circular graph exists iff N-1 is a power of
     a prime; i.e. N-1 = p^e, p:prime.
  2) For those N that fulfill the above, the number of distinct
     graphs are phi(K)/6e = phi(N^2-N+1)/6e; where phi is the Euler function.

According to Masahiko Miyamoto, this problem is related to a difficult
problem in projective space over a classic finite field, known as
"cyclic plane"s [don't ask me what this is].
The following theorem is known:
  when N-1 = p^e, the number of distinct graphs m is:
	m >= phi(K)/6e

[end quote]

Furthermore, in the 1987.7 issue, there is a report on an exhaustive
search by a computer.
[Minoru Shimobayashiyama]
Solutions for:
 N= 3 (K= 7): 1-2-4-
 N= 4 (K=13): 1-2-6-4-
	      1-3-2-7-
 N= 5 (K=21): 1-5-2-10-3-
 N= 6 (K=31): 1-2-5-4-6-13-
	      1-2-7-4-12-5-
	      1-3-2-7-8-10-
	      1-3-6-2-5-14-
	      1-7-3-2-4-14-
 N= 7 (K=43): (no solution)
 N= 8 (K=57): 1-2-10-19-4-7-9-5-
	      1-8-2-3-21-4-12-6-
	      1-12-2-6-3-7-22-4- [mirror image of the one given by the poster]
	      1-4-2-10-18-3-11-8-
	      1-3-8-2-16-7-15-5-
	      1-3-5-11-2-12-17-6-
 N= 9 (K=73): 1-2-4-8-16-5-18-9-10-
	      1-16-22-2-3-4-6-8-11-
	      1-8-12-2-3-13-24-4-6-
	      1-14-8-2-28-3-6-7-4-
 N=10 (K=91): 1-2-6-18-22-7-5-16-4-10-
	      1-36-2-12-7-8-3-13-4-5-
	      1-4-2-20-8-9-23-10-3-11-
	      1-18-3-2-8-4-29-11-9-6-
	      1-4-3-10-2-9-14-16-6-26-
	      1-18-28-5-2-8-6-11-9-3-
 N=11 (K=111): (no solution)
 N=12 (K=133):1-2-14-4-37-7-8-27-5-6-13-9-
	      1-2-9-8-14-4-43-7-6-10-5-24-
	      1-2-12-31-25-4-9-10-7-11-16-5-
	      1-2-14-12-32-19-6-5-4-18-13-7-
	      1-7-2-22-4-16-3-11-29-21-12-5-
	      1-11-2-8-7-25-6-3-27-20-19-4-
	      1-6-2-33-17-14-12-10-15-3-16-4-
	      1-14-3-2-4-7-21-8-25-10-12-26-
	      1-31-10-2-4-3-8-13-5-20-14-22-
	      1-9-48-2-4-18-5-11-3-12-13-7-
	      1-8-5-2-18-11-10-22-6-24-23-3-
	      1-6-28-2-13-16-23-19-5-9-8-3-
	      1-3-12-34-21-2-8-9-5-6-7-25-
	      1-4-7-3-16-2-6-17-20-9-13-35-
	      1-35-26-3-11-2-4-21-7-5-10-8-
	      1-15-5-3-25-2-7-4-6-12-14-39-
	      1-41-8-4-17-2-3-6-7-20-10-14-
	      1-7-6-16-15-2-9-10-40-3-20-4-

-Yuzuru Hiraga
Xref: sparky rec.puzzles:7975 sci.math:17037