Graphs Discussed on TTL-Problem Page    

This page gives edge-lists for all the graphs described on this page. All of these were auto-generated in order to avoid errors in the edge lists and to verify the valencies and diameters.

— any K, D=1 —

Graph Name: K₃ Nodes: 3 Edges: 3 Valency: 2 Diameter: 1 0 1 0 2 1 2

Graph Name: K₄ Nodes: 4 Edges: 6 Valency: 3 Diameter: 1 0 1 0 2 0 3 1 2 1 3 2 3

Graph Name: K₅ Nodes: 5 Edges: 10 Valency: 4 Diameter: 1 0 1 0 2 0 3 0 4 1 2 1 3 1 4 2 3 2 4 3 4

Graph Name: K₆ Nodes: 6 Edges: 15 Valency: 5 Diameter: 1 0 1 0 2 0 3 0 4 0 5 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5

— K=2, any D —

Graph Name: C₃ Nodes: 3 Edges: 3 Valency: 2 Diameter: 1 0 1 1 2 2 0

Graph Name: C₅ Nodes: 5 Edges: 5 Valency: 2 Diameter: 2 0 1 1 2 2 3 3 4 4 0

Graph Name: C₇ Nodes: 7 Edges: 7 Valency: 2 Diameter: 3 0 1 1 2 2 3 3 4 4 5 5 6 6 0

— K=3, D=2 —

Graph Name: K_3,3 = C_6(1,3) Nodes: 6 Edges: 9 Valency: 3 Diameter: 2 0 1 0 3 0 5 1 2 1 4 2 3 2 5 3 4 4 5

Graph Name: C_8(1,4) Nodes: 8 Edges: 12 Valency: 3 Diameter: 2 0 1 0 4 0 7 1 2 1 5 2 3 2 6 3 4 3 7 4 5 5 6 6 7

Graph Name: P Nodes: 10 Edges: 15 Valency: 3 Diameter: 2 0 1 0 4 0 5 1 2 1 6 2 3 2 7 3 4 3 8 4 9 5 7 5 8 6 8 6 9 7 9

— K=3, D=3 —

Graph Name: C = Cml_8(2:0,3) Nodes: 8 Edges: 12 Valency: 3 Diameter: 3 0 1 0 3 0 7 1 2 1 6 2 3 2 5 3 4 4 5 4 7 5 6 6 7

Graph Name: C_10(1,5) Nodes: 10 Edges: 15 Valency: 3 Diameter: 3 0 1 0 5 0 9 1 2 1 6 2 3 2 7 3 4 3 8 4 5 4 9 5 6 6 7 7 8 8 9

Graph Name: C_12(1,6) Nodes: 12 Edges: 18 Valency: 3 Diameter: 3 0 1 0 11 0 6 1 2 1 7 2 3 2 8 3 4 3 9 4 10 4 5 5 11 5 6 6 7 7 8 8 9 9 10 10 11

Graph Name: PP_{7(1,3) K2} Nodes: 14 Edges: 21 Valency: 3 Diameter: 3 0 1 0 6 0 7 1 2 1 8 2 3 2 9 3 10 3 4 4 11 4 5 5 12 5 6 6 13 7 10 7 11 8 11 8 12 9 12 9 13 10 13

Graph Name: PP_{7(1,2) K2} Nodes: 14 Edges: 21 Valency: 3 Diameter: 3 0 1 0 6 0 7 1 2 1 8 2 3 2 9 3 10 3 4 4 11 4 5 5 12 5 6 6 13 7 12 7 9 8 10 8 13 9 11 10 12 11 13

Graph Name: Heawood Nodes: 14 Edges: 21 Valency: 3 Diameter: 3 0 1 0 13 0 5 1 10 1 2 2 3 2 7 3 12 3 4 4 5 4 9 5 6 6 11 6 7 7 8 8 13 8 9 9 10 10 11 11 12 12 13

— K=4, D=2 —

Graph Name: O = C_6(1,2) Nodes: 6 Edges: 12 Valency: 4 Diameter: 2 0 1 0 2 0 4 0 5 1 2 1 3 1 5 2 3 2 4 3 4 3 5 4 5

Graph Name: K_4,4 = C_8(1,3) Nodes: 8 Edges: 16 Valency: 4 Diameter: 2 0 1 0 3 0 5 0 7 1 2 1 4 1 6 2 3 2 5 2 7 3 4 3 6 4 5 4 7 5 6 6 7

Graph Name: K₃ × K₃ Nodes: 9 Edges: 18 Valency: 4 Diameter: 2 0 1 0 2 0 3 0 6 1 2 1 4 1 7 2 5 2 8 3 4 3 5 3 6 4 5 4 7 5 8 6 7 6 8 7 8

Graph Name: C_11(1,3) Nodes: 11 Edges: 22 Valency: 4 Diameter: 2 0 1 0 10 0 3 0 8 1 2 1 4 1 9 2 10 2 3 2 5 3 4 3 6 4 5 4 7 5 6 5 8 6 7 6 9 7 10 7 8 8 9 9 10

Graph Name: Cml_{15(5:1,4:2,5:3,7:4,4:4,7)} Nodes: 15 Edges: 30 Valency: 4 Diameter: 2 0 1 0 11 0 14 0 8 1 2 1 5 1 9 2 12 2 3 2 7 3 10 3 14 3 4 4 11 4 5 4 8 5 13 5 6 6 10 6 14 6 7 7 12 7 8 8 9 9 10 9 13 10 11 11 12 12 13 13 14

— K=3, D=4 —

Graph Name: C_14(1,7) Nodes: 14 Edges: 21 Valency: 3 Diameter: 4 0 1 0 13 0 7 1 2 1 8 2 3 2 9 3 10 3 4 4 11 4 5 5 12 5 6 6 13 6 7 7 8 8 9 9 10 10 11 11 12 12 13

Graph Name: C_16(1,8) Nodes: 16 Edges: 24 Valency: 3 Diameter: 4 0 1 0 15 0 8 1 2 1 9 2 10 2 3 3 11 3 4 4 12 4 5 5 13 5 6 6 14 6 7 7 15 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15

Graph Name: PP_{11(1,3) K2} Nodes: 22 Edges: 33 Valency: 3 Diameter: 4 0 1 0 10 0 11 1 12 1 2 2 13 2 3 3 14 3 4 4 15 4 5 5 16 5 6 6 17 6 7 7 18 7 8 8 19 8 9 9 10 9 20 10 21 11 14 11 19 12 15 12 20 13 16 13 21 14 17 15 18 16 19 17 20 18 21

Graph Name: McGee = Cml_{24(3:1,12:2,7:0,17)} Nodes: 24 Edges: 36 Valency: 3 Diameter: 4 0 1 0 17 0 23 1 13 1 2 2 3 2 9 3 20 3 4 4 16 4 5 5 12 5 6 6 23 6 7 7 19 7 8 8 15 8 9 9 10 10 11 10 22 11 12 11 18 12 13 13 14 14 15 14 21 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23

Graph Name: Tutte-Coxeter = Cml_{30(6:1,17:2,21:3,7)} Nodes: 30 Edges: 45 Valency: 3 Diameter: 4 0 1 0 13 0 29 1 18 1 2 2 23 2 3 3 10 3 4 4 27 4 5 5 14 5 6 6 19 6 7 7 24 7 8 8 29 8 9 9 10 9 16 10 11 11 12 11 20 12 13 12 25 13 14 14 15 15 16 15 22 16 17 17 18 17 26 18 19 19 20 20 21 21 22 21 28 22 23 23 24 24 25 25 26 26 27 27 28 28 29

— K=4, D=3 —

Graph Name: K₂ × K_3,3 Nodes: 12 Edges: 24 Valency: 4 Diameter: 3 0 1 0 10 0 2 0 6 1 11 1 3 1 7 2 3 2 4 2 8 3 5 3 9 4 10 4 5 4 6 5 11 5 7 6 7 6 8 7 9 8 10 8 9 9 11 10 11

Graph Name: K₂ × P Nodes: 20 Edges: 40 Valency: 4 Diameter: 3 0 1 0 10 0 2 0 8 1 11 1 3 1 9 2 12 2 3 2 4 3 13 3 5 4 14 4 5 4 6 5 15 5 7 6 16 6 7 6 8 7 17 7 9 8 18 8 9 9 19 10 11 10 14 10 16 11 15 11 17 12 13 12 16 12 18 13 17 13 19 14 15 14 18 15 19 16 17 18 19

Graph Name: Moebius D Nodes: 20 Edges: 40 Valency: 4 Diameter: 3 0 10 0 16 0 19 0 4 1 11 1 19 1 2 1 3 2 12 2 18 2 6 3 13 3 4 3 5 4 14 4 8 5 15 5 6 5 7 6 10 6 16 7 17 7 8 7 9 8 12 8 18 9 10 9 11 9 19 10 14 11 12 11 13 12 16 13 14 13 15 14 18 15 16 15 17 17 18 17 19

Graph Name: PP_{7(1,2,3) K3} Nodes: 21 Edges: 42 Valency: 4 Diameter: 3 0 1 0 14 0 6 0 7 1 15 1 2 1 8 2 16 2 3 2 9 3 10 3 17 3 4 4 11 4 18 4 5 5 12 5 19 5 6 6 13 6 20 7 12 7 14 7 9 8 10 8 13 8 15 9 11 9 16 10 12 10 17 11 13 11 18 12 19 13 20 14 17 14 18 15 18 15 19 16 19 16 20 17 20

Graph Name: (4,6)-cage Nodes: 26 Edges: 52 Valency: 4 Diameter: 3 0 1 0 17 0 25 0 5 1 10 1 2 1 22 2 19 2 3 2 7 3 12 3 24 3 4 4 21 4 5 4 9 5 14 5 6 6 11 6 23 6 7 7 16 7 8 8 13 8 25 8 9 9 10 9 18 10 11 10 15 11 12 11 20 12 13 12 17 13 14 13 22 14 15 14 19 15 16 15 24 16 17 16 21 17 18 18 19 18 23 19 20 20 21 20 25 21 22 22 23 23 24 24 25

Graph Name: PP_{7(1,2,3,2) C4} Nodes: 28 Edges: 56 Valency: 4 Diameter: 3 0 1 0 21 0 6 0 7 1 2 1 22 1 8 2 23 2 3 2 9 3 10 3 24 3 4 4 11 4 25 4 5 5 12 5 26 5 6 6 13 6 27 7 12 7 14 7 9 8 10 8 13 8 15 9 11 9 16 10 12 10 17 11 13 11 18 12 19 13 20 14 17 14 18 14 21 15 18 15 19 15 22 16 19 16 20 16 23 17 20 17 24 18 25 19 26 20 27 21 23 21 26 22 24 22 27 23 25 24 26 25 27

— K=5, D=2 —

Graph Name: PP_{9(1,3) K2} U PP_{9(2,4) K2} Nodes: 18 Edges: 45 Valency: 5 Diameter: 2 0 1 0 2 0 7 0 8 0 9 1 10 1 2 1 3 1 8 2 11 2 3 2 4 3 12 3 4 3 5 4 13 4 5 4 6 5 14 5 6 5 7 6 15 6 7 6 8 7 16 7 8 8 17 9 12 9 13 9 14 9 15 10 13 10 14 10 15 10 16 11 14 11 15 11 16 11 17 12 15 12 16 12 17 13 16 13 17 14 17

— K=3, D=5 —

Graph Name: D Nodes: 20 Edges: 30 Valency: 3 Diameter: 5 0 16 0 19 0 4 1 19 1 2 1 3 2 18 2 6 3 4 3 5 4 8 5 6 5 7 6 10 7 8 7 9 8 12 9 10 9 11 10 14 11 12 11 13 12 16 13 14 13 15 14 18 15 16 15 17 17 18 17 19

— K=4, D=4 —

Graph Name: C × K₂ Nodes: 16 Edges: 32 Valency: 4 Diameter: 4 0 1 0 3 0 7 0 8 1 2 1 6 1 9 2 10 2 3 2 5 3 11 3 4 4 12 4 5 4 7 5 13 5 6 6 14 6 7 7 15 8 11 8 15 8 9 9 10 9 14 10 11 10 13 11 12 12 13 12 15 13 14 14 15

Graph Name: C₅ × C₅ Nodes: 25 Edges: 50 Valency: 4 Diameter: 4 0 1 0 20 0 4 0 5 1 2 1 21 1 6 2 22 2 3 2 7 3 23 3 4 3 8 4 24 4 9 5 10 5 6 5 9 6 11 6 7 7 12 7 8 8 13 8 9 9 14 10 11 10 14 10 15 11 12 11 16 12 13 12 17 13 14 13 18 14 19 15 16 15 19 15 20 16 17 16 21 17 18 17 22 18 19 18 23 19 24 20 21 20 24 21 22 22 23 23 24

Graph Name: PP_{7(1,3) K2} × K₂ Nodes: 28 Edges: 56 Valency: 4 Diameter: 4 0 1 0 14 0 6 0 7 1 15 1 2 1 8 2 16 2 3 2 9 3 10 3 17 3 4 4 11 4 18 4 5 5 12 5 19 5 6 6 13 6 20 7 10 7 11 7 21 8 11 8 12 8 22 9 12 9 13 9 23 10 13 10 24 11 25 12 26 13 27 14 15 14 20 14 21 15 16 15 22 16 17 16 23 17 18 17 24 18 19 18 25 19 20 19 26 20 27 21 24 21 25 22 25 22 26 23 26 23 27 24 27

Graph Name: Heawood × K₂ Nodes: 28 Edges: 56 Valency: 4 Diameter: 4 0 1 0 13 0 14 0 5 1 10 1 15 1 2 2 16 2 3 2 7 3 12 3 17 3 4 4 18 4 5 4 9 5 19 5 6 6 11 6 20 6 7 7 21 7 8 8 13 8 22 8 9 9 10 9 23 10 11 10 24 11 12 11 25 12 13 12 26 13 27 14 15 14 19 14 27 15 16 15 24 16 17 16 21 17 18 17 26 18 19 18 23 19 20 20 21 20 25 21 22 22 23 22 27 23 24 24 25 25 26 26 27

Graph Name: PP_{9(1,2,3,4) C4} Nodes: 36 Edges: 72 Valency: 4 Diameter: 4 0 1 0 27 0 8 0 9 1 10 1 2 1 28 2 11 2 29 2 3 3 12 3 30 3 4 4 13 4 31 4 5 5 14 5 32 5 6 6 15 6 33 6 7 7 16 7 34 7 8 8 17 8 35 9 11 9 16 9 18 10 12 10 17 10 19 11 13 11 20 12 14 12 21 13 15 13 22 14 16 14 23 15 17 15 24 16 25 17 26 18 21 18 24 18 27 19 22 19 25 19 28 20 23 20 26 20 29 21 24 21 30 22 25 22 31 23 26 23 32 24 33 25 34 26 35 27 31 27 32 28 32 28 33 29 33 29 34 30 34 30 35 31 35

Graph Name: PP_{9(1,2,3,4,2) C5} Nodes: 45 Edges: 90 Valency: 4 Diameter: 4 0 1 0 36 0 8 0 9 1 10 1 2 1 37 2 11 2 3 2 38 3 12 3 39 3 4 4 13 4 40 4 5 5 14 5 41 5 6 6 15 6 42 6 7 7 16 7 43 7 8 8 17 8 44 9 11 9 16 9 18 10 12 10 17 10 19 11 13 11 20 12 14 12 21 13 15 13 22 14 16 14 23 15 17 15 24 16 25 17 26 18 21 18 24 18 27 19 22 19 25 19 28 20 23 20 26 20 29 21 24 21 30 22 25 22 31 23 26 23 32 24 33 25 34 26 35 27 31 27 32 27 36 28 32 28 33 28 37 29 33 29 34 29 38 30 34 30 35 30 39 31 35 31 40 32 41 33 42 34 43 35 44 36 38 36 43 37 39 37 44 38 40 39 41 40 42 41 43 42 44

Graph Name: PP_{11(1,2,4,3,5) C5} Nodes: 55 Edges: 110 Valency: 4 Diameter: 4 0 1 0 10 0 11 0 44 1 12 1 2 1 45 2 13 2 3 2 46 3 14 3 4 3 47 4 15 4 48 4 5 5 16 5 49 5 6 6 17 6 50 6 7 7 18 7 51 7 8 8 19 8 52 8 9 9 10 9 20 9 53 10 21 10 54 11 13 11 20 11 22 12 14 12 21 12 23 13 15 13 24 14 16 14 25 15 17 15 26 16 18 16 27 17 19 17 28 18 20 18 29 19 21 19 30 20 31 21 32 22 26 22 29 22 33 23 27 23 30 23 34 24 28 24 31 24 35 25 29 25 32 25 36 26 30 26 37 27 31 27 38 28 32 28 39 29 40 30 41 31 42 32 43 33 36 33 41 33 44 34 37 34 42 34 45 35 38 35 43 35 46 36 39 36 47 37 40 37 48 38 41 38 49 39 42 39 50 40 43 40 51 41 52 42 53 43 54 44 49 44 50 45 50 45 51 46 51 46 52 47 52 47 53 48 53 48 54 49 54

Graph Name: PP_{13(1,5,4,2,3,6) C6} Nodes: 78 Edges: 156 Valency: 4 Diameter: 4 0 1 0 12 0 13 0 65 1 14 1 2 1 66 2 15 2 3 2 67 3 16 3 4 3 68 4 17 4 5 4 69 5 18 5 6 5 70 6 19 6 7 6 71 7 20 7 72 7 8 8 21 8 73 8 9 9 10 9 22 9 74 10 11 10 23 10 75 11 12 11 24 11 76 12 25 12 77 13 18 13 21 13 26 14 19 14 22 14 27 15 20 15 23 15 28 16 21 16 24 16 29 17 22 17 25 17 30 18 23 18 31 19 24 19 32 20 25 20 33 21 34 22 35 23 36 24 37 25 38 26 30 26 35 26 39 27 31 27 36 27 40 28 32 28 37 28 41 29 33 29 38 29 42 30 34 30 43 31 35 31 44 32 36 32 45 33 37 33 46 34 38 34 47 35 48 36 49 37 50 38 51 39 41 39 50 39 52 40 42 40 51 40 53 41 43 41 54 42 44 42 55 43 45 43 56 44 46 44 57 45 47 45 58 46 48 46 59 47 49 47 60 48 50 48 61 49 51 49 62 50 63 51 64 52 55 52 62 52 65 53 56 53 63 53 66 54 57 54 64 54 67 55 58 55 68 56 59 56 69 57 60 57 70 58 61 58 71 59 62 59 72 60 63 60 73 61 64 61 74 62 75 63 76 64 77 65 71 65 72 66 72 66 73 67 73 67 74 68 74 68 75 69 75 69 76 70 76 70 77 71 77

— K=5, D=3 —

Graph Name: Robertson-Wegner Nodes: 30 Edges: 75 Valency: 5 Diameter: 3 0 10 0 15 0 19 0 2 0 29 1 12 1 2 1 21 1 28 1 4 2 26 2 3 2 8 3 13 3 18 3 22 3 5 4 15 4 24 4 5 4 7 5 11 5 29 5 6 6 16 6 21 6 25 6 8 7 10 7 18 7 27 7 8 8 14 8 9 9 11 9 19 9 24 9 28 10 11 10 13 10 21 11 12 11 17 12 14 12 22 12 27 13 14 13 16 13 24 14 15 14 20 15 17 15 25 16 17 16 19 16 27 17 18 17 23 18 20 18 28 19 20 19 22 20 21 20 26 21 23 22 23 22 25 23 24 23 29 24 26 25 26 25 28 26 27 27 29 28 29

Graph Name: PP_{9(1,2,3,4) K4} Nodes: 36 Edges: 90 Valency: 5 Diameter: 3 0 1 0 18 0 27 0 8 0 9 1 10 1 19 1 2 1 28 2 11 2 20 2 29 2 3 3 12 3 21 3 30 3 4 4 13 4 22 4 31 4 5 5 14 5 23 5 32 5 6 6 15 6 24 6 33 6 7 7 16 7 25 7 34 7 8 8 17 8 26 8 35 9 11 9 16 9 18 9 27 10 12 10 17 10 19 10 28 11 13 11 20 11 29 12 14 12 21 12 30 13 15 13 22 13 31 14 16 14 23 14 32 15 17 15 24 15 33 16 25 16 34 17 26 17 35 18 21 18 24 18 27 19 22 19 25 19 28 20 23 20 26 20 29 21 24 21 30 22 25 22 31 23 26 23 32 24 33 25 34 26 35 27 31 27 32 28 32 28 33 29 33 29 34 30 34 30 35 31 35

— K=5, D=4 —

Graph Name: PP_{7(1,2,3,2) C4} × K₂ Nodes: 56 Edges: 140 Valency: 5 Diameter: 4 0 1 0 21 0 28 0 6 0 7 1 2 1 22 1 29 1 8 2 23 2 3 2 30 2 9 3 10 3 24 3 31 3 4 4 11 4 25 4 32 4 5 5 12 5 26 5 33 5 6 6 13 6 27 6 34 7 12 7 14 7 35 7 9 8 10 8 13 8 15 8 36 9 11 9 16 9 37 10 12 10 17 10 38 11 13 11 18 11 39 12 19 12 40 13 20 13 41 14 17 14 18 14 21 14 42 15 18 15 19 15 22 15 43 16 19 16 20 16 23 16 44 17 20 17 24 17 45 18 25 18 46 19 26 19 47 20 27 20 48 21 23 21 26 21 49 22 24 22 27 22 50 23 25 23 51 24 26 24 52 25 27 25 53 26 54 27 55 28 29 28 34 28 35 28 49 29 30 29 36 29 50 30 31 30 37 30 51 31 32 31 38 31 52 32 33 32 39 32 53 33 34 33 40 33 54 34 41 34 55 35 37 35 40 35 42 36 38 36 41 36 43 37 39 37 44 38 40 38 45 39 41 39 46 40 47 41 48 42 45 42 46 42 49 43 46 43 47 43 50 44 47 44 48 44 51 45 48 45 52 46 53 47 54 48 55 49 51 49 54 50 52 50 55 51 53 52 54 53 55

---

---

Robert Munafo's home pages on AWS    © 1996-2024 Robert P. Munafo.    about    contact
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Details here.
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2018 Mar 07. s.27