Status Injective (SI) Graphs (download.gif (1186 bytes))

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:

7_Vertices_7_Edges_K3.gif (11424 bytes)

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.


[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 <>