Different labeling on a graph produces class of isomorphic graphs. Two isomorphic graphs possess similar characteristic such as connectivity, degree distribution of vertices, equality of spectrum and many others. I am looking for some properties of graph which depends particularly on vertex labeling. One such property is separability of the quantum state related to that graph. Depending on the vertex labeling two isomorphic graphs may generate different quantum states with different separability. Is there any other properties of graph which depends on vertex labeling only?

1$\begingroup$ It's hard to think of anything sensible and natural other than trivialities or problems that are explicitly related to labellings with particular properties (graceful, prime, magic, antimagic and about 2000 other variants). $\endgroup$ – Gordon Royle Aug 29 '15 at 14:18

1$\begingroup$ There's the adjacency matrix, for a start. $\endgroup$ – Chris Godsil Aug 29 '15 at 15:37

$\begingroup$ It's hard because there is not really a good labelling either: do you start from 0 or 1? So, to be more precise, you seek properties that depend on a total ordering of the vertices... I wonder if there is some way to relate this to partially ordered sets somehow. I'd have a look in R. Stanleys EC1, Chapter 3; wwwmath.mit.edu/~rstan/ec/ec1.pdf for inspiration $\endgroup$ – Per Alexandersson Aug 29 '15 at 18:07

$\begingroup$ People have looked at Ramsey theory for graphs with an ordering of their vertices, although this is more looking at a new class of objects than a property of graphs that depends on some choice of vertex ordering. $\endgroup$ – Ben Barber Aug 30 '15 at 13:28