[ Post a Response | Puzzles Forum ]
Posted by markr on 10/8/2009, 7:25 am, in reply to "15+ status"
At this site:
http://www.springerlink.com/content/up282173473l0440/fulltext.pdf?page=1
I found this:
1 Introduction
We consider simple (without loops and multiple edges), finite, and undirected
graphs. The order of the graph is the number of its vertices. The degree of a
vertex is the number of incident edges to that vertex. The distance between two
vertices is the length of the shortest path between them. The diameter of a graph
is the maximum distance between any two vertices. Denote by (d,k)-graph the
graph of diameter k and maximum vertex degree d.
Degree/Diameter Problem. To find the largest possible number of vertices
n(d, k) of (d, k)-graphs for various d and k.
The state of general problem is presented in [1,2]. We focus only on graphs
of diameter 2. A well-known bound on the largest order of (d, 2)-graphs is
Moore bound: n(d, 2) = d^2 + 1. This bound is attainable only for d = 1, 2, 3, 7
and, possibly, 57 [3]. Excluding d = 57, the corresponding graphs K2, C2,
the Petersen graph and the Hoffman–Singleton graph are unique. The existing
of a (57, 2)-graph on n = 57^2 + 1 = 3250 vertices is not known. For
the remaining d, it is shown that n(d, 2) = d^2 - 1 [4]. It is known that this
bound is attainable only for d = 4, 5 [5]. The largest known order of (6,2)-
graphs was 32 [1,2]. A theoretic possible bound for these graphs is
n = 6^2 - 1 = 35.
------------------------------------------------
Of course, they don't care about time slots. However, what this means is that the best you can hope for is 4^2 - 1 = 15. I've found a bunch of solutions for 15 but none of them can be scheduled in four time slots.
I think 14 is as high as you're going to go.
Message Thread:
« Back to thread