Friday, March 29, 2013

T list of a graph

So to create this list T, you first label all nodes of a graph as 1 in the first step. Then in the second step each vertex becomes the sum of it's label in step 1 summed with the label of each node it's connected to in the first graph. Then this process iterates until the number of steps equals the diameter of the graph, which is the max number of edges one has to cross between any two points on the graph. For example the point labeled 43 in the bottom right graph was labeled so because it had a label of 12 in the bottom left graph and it was connected to 16 and 15. 43 = 12+15+16. 
Then the list T is just the value of the vertices listed in increasing order: T={23,36,38,39,40,43,47,55,59,67}

So I believe that isomorphic graphs yield the same list, but I'm conjecturing that the only graphs that produce the same list are isometries. 

But even if this doesn't end up true there is an interesting use for this T list: I can say whatever graph you have and whatever labeling to pick one of the vertices with the lowest value in the T list. Because I believe that if two vertices have the same value in the T list if the graph looks the same from either of those two points... Then this gives a way to distinguish one point on any graph. Or at least one of the points that the rest of the graph looks the same from. So no matter how they have a graph labeled or drawn this gives a way to specify a vertex. 

The last thing I said doesn't necessarily apply if you have for instance a graph with two disconnected subgraphs, then you might have two vertices that end up with the same number but the graph doesn't look the same from their two perspectives...

No comments:

Post a Comment