Challenge

You likely have never heard of a status injective (SIJ) graph. Too bad. Your goal is to find as many unique status injective graphs as you can in 20 minutes.

Definition

A status injective graph is an undirected graph G=(V,E) where each vertex is assigned a computed status value. The status value is computed by adding together the shortest distance to all other graphs in the graph. It may take a moment to see that a status injective graph must be connected. In a status injective graph, there are no duplicate status values among the vertices. That is, if status(v_i) = status(v_j) then i=j. As an example, consider the following graph:

In this connected graph of three vertices (A, B, and C) the status of A is computed to be 2 (total of 1 from A to B and 1 from A to C). The status value for B is 3 (total of 1 from B to A and 2 from B to C). Note that both B and C have duplicate status values so this graph is not status injective. Let's add a few more edges:

As more nodes are added, the computed status values for each node increases. Consider node D, for example. Its status value is 12, which equals:

	A	B	C	E	F	Total
D	1	2	2	3	4	12

This time two nodes B and E have the same status value so the overall graph is still not a status injective graph... Hmm. Let's add one more edge from F to a new node G.

Whoa! Check this out. All of the status values are different. Indeed the grey Properties box associated with the graph comes right out and declares that the graph is status injective. So this is your first SIJ graph.

Tool Support

You could dull a lot of pencils working on this problem! Fortunately you have tool support in your quest. Yes, the Status Injective Applet (v1.5.1) is available for you to use. Documentation? Non-existent, but the tool is rather intuitive to use. Find the applet at:

Here are the highlights:

Process

A screenshot of each discovered SIJ graph should be saved to a folder on your computer. The judges will review the results once you are done.

Inspiration

Here are two sample SIJ graphs to provide.... inspiration?

Notes

1. Initial Version