analytics

Friday, June 28, 2013

Delta-characteristic of a graph

Suppose you have a graph like the following:
I am defining the Delta-characteristic to be, for each vertex set up a distance-like formula (hence the delta in the name) relating the vertex to the vertices it is connected to. For example C is connected to B,D, and J so one formula is:


I found that Maple solves a system of this type of equations readily but won't do anything with the system of actual distance formula equations, and I think this one is enough to accomplish what I need from it. 


Now since there will be one equation for every vertex the system can be solved:
and it turns out the solution is:
Since the labeling of the graph was arbitrary, it was only the way the vertices were connected that mattered, this result can form a list(ordered by magnitude and rounded to the digit necessary to distinguish the numbers):



Isometric graphs will form the same set, because the equations don't take into account the drawing of the graph, and the reordering of the set numerically will end up the same no matter the original labeling. 
I don't know whether two non-isometric graphs can have the same Delta-characteristic but it seems unlikely.

Another interesting aspect of the Delta-characteristic is consider this graph instead:

A vertex L has been added:
the Delta-characteristic works out to:

See the only difference is one more number in the list, and it is a repeat of 3.353, this is because vertex A and vertex L are indistinguishable in the graph apart from labeling, they are connected to the same vertices. 

Maybe I should explain some more, the way I see it the purpose of the square roots is to prevent mixing of the variables, like if I just used the equation A=B+C and B=A+D+E for example when the equations are solved the distinction between variables that occurred on the left side vs the right side and when equations are say, added the distinction between which vertices each variable are connected to are also lost. So the square root is sort of forming logical divisions between how the variables occur in the equations rather than for their numerical significance. 

**EDIT**
Here is an tabulation of the Delta-characteristic of all the simple graphs with 5 vertices:
G1:  1     1     1.259 1.259 1.587
G2:  1     1     2     2     2
G3:  1.341 1.341 1.799 1.799 1.897
G4:  1.375 1.484 1.484 1.892 2.205
G5:  1.587 1.587 1.587 1.587 2.519
G6:  1.587 1.587 2.245 2.52  2.52
G7:  1.673 1.673 2.246 2.246 2.799
G8:  1,406 1.979 2.161 2.161 2.510
G9:  1.415 2.005 2,259 2.505 2.601 
G10: 2     2     2     2     2
G11: 1,640 2.368 2.692 2.804 2.804 
G12: 1.751 2.425 2.425 2.814 3.068
G13: 2.213 2.213 2.318 2.686 2.686
G14: 2.289 2.289 2.289 2.620 2.620
G15: 2.314 2.314 2.314 2.314 3.042
G16: 1.823 3.079 3.079 3.079 3.326
G17: 2.579 2.579 2.579 3.326 3.326
G18: 2.400 2.881 2.881 2.952 2.952
G19: 2.503 2.503 2.961 2.961 3.306
G20: 2.667 3.213 3.213 3.556 3.556
G21: 3.130 3.130 3.130 3.130 3.538
G22: 3.368 3.368 3.781 3.781 3.781 
G23: 4     4     4     4     4

As you can see, no two non-isomorphic graphs gave the same Delta-Characteristic. In fact only G1 and G2 have any numbers in common... 

No comments:

Post a Comment