  Three new graph invariants are introduced which may be measured from a
quantum graph state and form examples of a framework under which other graph
invariants can be constructed. Each invariant is based on distinguishing a
different number of qubits. This is done by applying alternate measurements to
the qubits to be distinguished. The performance of these invariants is
evaluated and compared to classical invariants. We verify that the invariants
can distinguish all non-isomorphic graphs with 9 or fewer nodes. The invariants
have also been applied to `classically hard' strongly regular graphs,
successfully distinguishing all strongly regular graphs of up to 29 nodes, and
preliminarily to weighted graphs. We have found that although it is possible to
prepare states with a polynomial number of operations, the average number of
preparations required to distinguish non-isomorphic graph states scales
exponentially with the number of nodes. We have so far been unable to find
operators which reliably compare graphs and reduce the required number of
preparations to feasible levels.
