))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.
We have investigated several families of SI graphs. Here are the results.
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