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.

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