## Status Injective (SI) Graphs ()

### Problem Statement

Given a simple, undirected graph G = (V, E) compute the shortest distance vector D =
(d1, d2, ..., dn) for each node in the graph, where n = |V|. The status of a node is the
sum of the computed elements of D. A graph is classified as *status injective* if
the calculated status values for all nodes are different.

I developed a Java applet that enables one to interactively explore SI graphs. For
example, The smallest, non-trivial SI graph is:

Using this software, I have developed several algorithms for constructing SI graphs of
any size. Click here to view the
applet in action.

### Complete Set of Interesting Graphs

We have investigated several families of SI graphs. Here are the results.

### SI Questions

Questions about SI graphs;
some solved, some open.

I have made available the Status Injective Investigator (V1.5.5) for free download. You
will be asked to fill out some brief, non-personal information so I can track the usage
and download of the software.

Click here
to download the Status Injective Investigator.

### References

[1] L. Pachter, **Constructing
Status Injective Graphs**, Discrete Applied Mathematics, 80 (1) (1997) pp. 107--113.

01/14/08 11:07:02 AM

George Heineman <heineman@cs.wpi.edu>