meditationatae

Just another WordPress.com site

Possible unit distance graph with 13 vertices and 30 edges

The unit distance graph solver I wrote in the C programming language may have found a unit distance graph with 13 vertices, 30 edges of length one, chromatic number 4, and 212 4-colourings, up to permutation of the 4 colours, where there are 4! = 24 permutations of the colours, say, Red, Green, Blue, and Yellow.

Below, I give the 13×13 adjacency matrix for the vertices labelled A through M. Computations show that in the embedding of the 13-vertex graph into R^2, adjacent vertices are at distance 1.0 to within 1/(10^16). For now, it seems too hard for me to prove that the distances (edges) can be made equal to 1.0 exactly, judging from the rather complex figure I have on graph paper.

Now, for the adjacency matrix:

adjacency matrix, 13×13 :

A B C D E F G H I J K L M
A 0 0 1 0 0 1 1 0 1 0 0 1 0
B 0 0 0 1 1 0 1 0 0 0 0 0 0
C 1 0 0 0 1 0 0 1 0 1 0 1 0
D 0 1 0 0 1 1 0 0 0 0 0 1 1
E 0 1 1 1 0 1 0 0 0 1 0 0 0
F 1 0 0 1 1 0 0 0 1 0 0 0 0
G 1 1 0 0 0 0 0 1 1 0 1 0 0
H 0 0 1 0 0 0 1 0 0 1 1 0 0
I 1 0 0 0 0 1 1 0 0 1 0 0 1
J 0 0 1 0 1 0 0 1 1 0 0 0 1
K 0 0 0 0 0 0 1 1 0 0 0 1 1
L 1 0 1 1 0 0 0 0 0 0 1 0 1
M 0 0 0 1 0 0 0 0 1 1 1 1 0

Next, the list of the 30 edges in the graph :

AC
AF
AG
AI
AL
BD
BE
BG
CE
CH
CJ
CL
DE
DF
DL
DM
EF
EJ
FI
GH
GI
GK
HJ
HK
IJ
IM
JM
KL
KM
LM

When embedded in the plane, these edges have a lentgh between 1 – epsilon and 1 + epsilon, where epsilon = 1E-16 .

For graphing/plotting purposes, I scaled/multiplied by a factor of 8.0 the x and y coordinates of the embedding in the plane for the graph. Thus, in the plotting coordinates below, edges have lengths very close to 8.0 :

PLOT COORDINATES:
x: y:
A 11.19821919 13.25045231
B 5.32174392 12.81261277
C 3.72492760 16.10525751
D 12.79503551 9.95780756
E 11.53072355 17.85727053
F 19.00401514 15.00246532
G 8.81260900 5.61442821
H 1.33931741 8.46923342
I 16.61840495 7.36644123
J 9.14511336 10.22124644
K 2.60362937 0.56977044
L 4.98923956 8.20579454
M 10.40942532 2.32178346

These plotting coordinates are given to 8 decimals. Here they are to 18 decimals:

PLOT COORDINATES:
x: y:
A 11.198219191921061789 13.250452305406670937
B 5.321743918026219025 12.812612769849526509
C 3.724927600140764836 16.105257514913251721
D 12.795035509806516247 9.957807560342945618
E 11.530723548205223334 17.857270533466618027
F 19.004015139985520824 15.002465323960036954
G 8.812608999717104444 5.614428208348530141
H 1.339317407936807158 8.469233417855111156
I 16.618404947781563135 7.366441226901895712
J 9.145113356001265674 10.221246436408476720
K 2.603629369538099817 0.569770444731438857
L 4.989239561742057498 8.205794541789579483
M 10.409425317602558271 2.321783463284804645

Finally, a scan of a plot I did manually on graph paper :

 

feb18scan2

Advertisements

Written by meditationatae

February 19, 2017 at 2:38 am

Posted in History

%d bloggers like this: