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?
$\begingroup$
$\endgroup$
4
-
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, anti-magic and about 2000 other variants). $\endgroup$– Gordon RoyleAug 29, 2015 at 14:18
-
1$\begingroup$ There's the adjacency matrix, for a start. $\endgroup$– Chris GodsilAug 29, 2015 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; www-math.mit.edu/~rstan/ec/ec1.pdf for inspiration $\endgroup$– Per AlexanderssonAug 29, 2015 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 BarberAug 30, 2015 at 13:28
Add a comment
|