A Problem of Combinations

Factual Questions
1

I’m working on a computer game in which the spaces that players can occupy are connected to other spaces by exactly three pathways, always. I wrote a quick-and-dirty program which does lots of brute-force random connections among N spaces and averages the results to tell me how “far away” two spaces can be from one another given N spaces, but I was wondering if this had already been determined, in terms of the number of different arrangements possible.

So, given a number (N) of spaces (S), each of which must have three pathways § connecting to different other S (in other words, S[sub]A[/sub] cannot connect to S[sub]B[/sub] via more than one P), how many three-dimensionally, topologically different arrangements of Ss and Ps are possible? Is there already a formula with the answer?

What I know so far is that N must always be an even number to satisfy the “exactly 3 P from each S, no duplicates” requirement, N must be at least 4, and that if N is 4, the only possible arrangement is one in which each S is at the tip of a tetrehedron, each P being an edge. After scratching for a while with paper and pencil, I’m fairly certain that if N is 6, there is also only one configuration (imagine two triangles floating parallel to each other, their vertices connected by 3 more Ps). If N is 8, I think the number of possibilities is more than 1, but I’m not quite sure. And if N is 10, I’m pretty sure there’s more than one configuration which works, but I don’t have a clue as to how many configurations there really are (2? 3? More?).

This is mostly asked in curiosity, right now, since I can continue to brute-force random networks of Ss and Ps to my heart’s content. But I was thinking about this because I thought it might be interesting to make sure that getting from one particular S to another would take at least X pathways, and was wondering how much N would need to be to force a minimum traverse of X Ps.

Yeah, the question is, given N Ss, what is the maximum mininum number of Ps which must be traversed between two Ss (let’s call this value M), given an optimally “tight” arrangement of Ss and Ps? By “tight” I mean “minimizing the value of M,” since it’s fairly obvious that it’s easy to maximize M by arranging the Ss and Ps for a high-N network…

Oh, my brute-force program came up with an “answer” of M=16 when N=2000, if that helps at all. Of course, it came up with M=15 for N=1990, but M=16 again for something like N=1970, too, so the random-brute-force-and-averaging method doesn’t exactly “work” in any deterministic sort of sense, which is what I’m looking for.

2

You may have better luck searching if you phrase your problem in standard terms. I assume that a path between space A and space B guarantees a path between space B and space A.

You’ve got a graph, with n vertices and m edges. Each vertex has degree 3. What you want to know is the maximum path length. If you don’t know what those words mean, look 'em up over at mathworld.

I’m pretty sure that it can be no more than ceiling(n/3), but that’s just my intuition. I’ll play around with it and see what I can come up with.

3

Yup.

Well, no. What I really want to know is the minimum maximum path length. Given a graph with n vertices, how short can the maximum path length possibly be?

4

Concerning finding the minimum diameter issue:

Given an undirected graph of a given degree and a given degree, finding the maximum number of nodes such a graph can have is called the “(k,d) graph problem”. (I forget which of k/d is degree/diameter.) It’s equivalent, of course, to given degree and number of nodes, find the best diameter.

There was a flurry of papers in IEEE Transactions on Computers in the late 80’s early 90’s. Also a few in Information Processing Letters. Haven’t tracked it in recent years.

There were some very nice theoretical results going back to the 60’s. An IBM researcher showed that there were only 3 non-trivial graphs and a 4th open case that could meet the theoretical minimum. One of which, for degree 3, diameter 2, is the famous Petersen graph that appears on the cover of the Graph Theory journal. A latter result (Singleterry?) showed that the next best type of graphs (very nice symmetry) only exist for a few small degrees and prime power diameters.

A lot of the early work was based on Eigenvalues of the incidence matrices and block designs in combinatorics. But once Computer geeks got involved, the constructions got too ad hoc. (Computer networks are one obvious application.)

So a lot of study of the properties of such stuff. Extremely hard to analyze in general. Not clear off the top of my head how this affects counting. Note that the real issue with counting graphs of a certain type in general is the isomorphism question. It is very easy to generate a graph in two different ways, same “picture” but different names for nodes. There is no known (and unlikely to be) easy way to determine if two graphs are isomorphic. (Graph Isomorphism is known to not be NP-Complete or in P unless the Polynomial Time Hierarchy collapses.)

5

ftg wrote:

Okay, let’s forget that part of the question. The fact that I’m looking for the diameter of the graph is a big help, I think. Makes Googling somewhat more productive. I’ll see what I can find.

By the way, ultrafilter, it seems to me that if you construct a graph like this:


O--O--O--O--O--O-   -O--O--O--O
|\/    \/    \/  ...  \/    \/|
|/\    /\    /\       /\    /\|
O--O--O--O--O--O-   -O--O--O--O

Where the vertices are Os, you wind up with a maximum path length of (n/2)-1. Well, so long as n is a multiple of 4. Obviously I’m not talking about planar graphs. But again, the maximum path length isn’t what I’m looking for.

6

Hmmm… Perhaps what I’m looking for is a way to reverse the Moore bound calculation, if I’m reading this page correctly. If the Moore bound for graphs with a degree of 3 is N(3,D)=3*2[sup]D[/sup]-2, then the minimum diameter for a graph with n vertices (of degree 3) seems like it should be close to D[sub]min/sub=log[sub]2/sub. Not that it will be exactly that value, of course (most n will generate a non-integer D[sub]min[/sub], anyway), but somewhere in that neighborhood?

Wait… Would it be correct to say that if I wanted to create a graph with a specific diameter, D, I would need to use more than N(3,D-1) vertices, but at most N(3,D) vertices? So that if I wanted D to be, say, 10, I would need a graph with between 1536 and 3070 vertices? Obviously, not every graph in that range will have a D of 10 (as per my previous post, one could make a graph with 1536 vertices and a D of 767), but none will have a D of 9 or less, since N(3,9)=1534.

Am I on the right track, at least?

7

It sounds reasonable to me.