[GAP Forum] DigraphsHomomorphisms

[Gordon Royle]

I am using the GAP package “digraphs” to determine whether or not there is a homomorphism from a digraph d1 to a digraph d2 (in fact they are graphs, but that does not matter).

The actual two graphs that I am using are included at the bottom of this message for anyone wishing to replicate this behaviour, but the key point is that d1 has 16 vertices and d2 has 32.

When I issue the command

gap> DigraphHomomorphism(d1,d2);
Transformation( [ 1, 2, 3, 9, 7, 8, 4, 19, 6, 32, 30, 5, 18, 31, 29, 20, 17,
  18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 ] )

the output is a Transformation, indicating that there is indeed a homomorphism from d1 to d2.


But why does the transformation have 32 entries, when d1 is a digraph with only 16 vertices?

Do I just take the first 16 entries as the actual transformation, and ignore the rest?


Thanks

Gordon




gap> Print(d1);
Digraph( [ [ 12, 2, 13, 3, 4, 5, 6, 7, 8, 9 ], [ 11, 1, 12, 13, 3, 14, 15, 5, \
7, 9 ], [ 11, 1, 12, 2, 15, 6, 7, 8, 9, 10 ], [ 1, 12, 13, 14, 5, 16, 6, 7, 8,\
 10 ], [ 1, 2, 13, 14, 4, 15, 16, 7, 8, 9 ], [ 11, 1, 12, 13, 3, 4, 16, 8, 9, \
10 ], [ 1, 2, 3, 4, 5, 8, 10, 12, 14, 15 ], [ 1, 3, 4, 15, 5, 16, 6, 7, 9, 10 \
], [ 11, 1, 2, 13, 3, 15, 5, 16, 6, 8 ], [ 11, 12, 3, 14, 4, 15, 16, 6, 7, 8 ]\
, [ 12, 2, 13, 3, 14, 15, 16, 6, 9, 10 ], [ 11, 1, 2, 13, 3, 14, 4, 6, 7, 10 ]\
, [ 11, 1, 12, 2, 14, 4, 5, 16, 6, 9 ], [ 2, 4, 5, 7, 10, 11, 12, 13, 15, 16 ]\
, [ 11, 2, 3, 14, 5, 16, 7, 8, 9, 10 ], [ 11, 13, 14, 4, 15, 5, 6, 8, 9, 10 ] \
] )

gap> Print(d2);
Digraph( [ [ 17, 18, 2, 19, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ],\
 [ 29, 1, 30, 31, 3, 4, 5, 6, 7, 10, 11, 12, 13, 18, 21, 22, 23, 24 ], [ 29, 1\
, 30, 2, 32, 4, 5, 6, 8, 10, 11, 14, 15, 19, 21, 22, 25, 26 ], [ 17, 1, 2, 19,\
 3, 5, 23, 7, 24, 9, 27, 28, 12, 29, 13, 31, 32, 16 ], [ 1, 30, 2, 31, 3, 32, \
4, 8, 9, 14, 15, 16, 17, 18, 25, 26, 27, 28 ], [ 17, 1, 18, 2, 19, 3, 20, 23, \
7, 24, 8, 25, 26, 10, 11, 29, 30, 16 ], [ 29, 1, 2, 31, 4, 6, 9, 12, 13, 14, 1\
5, 18, 19, 20, 21, 22, 27, 28 ], [ 1, 30, 3, 32, 5, 6, 9, 12, 13, 14, 15, 18, \
19, 20, 21, 22, 27, 28 ], [ 17, 1, 18, 19, 20, 4, 5, 23, 7, 24, 8, 25, 26, 10,\
 11, 31, 32, 16 ], [ 17, 1, 2, 3, 20, 21, 22, 6, 23, 25, 9, 27, 28, 12, 14, 31\
, 32, 16 ], [ 17, 1, 2, 3, 20, 21, 22, 6, 24, 9, 26, 27, 28, 13, 31, 15, 32, 1\
6 ], [ 1, 30, 2, 32, 4, 7, 8, 10, 14, 15, 16, 20, 21, 23, 24, 25, 26, 28 ], [ \
17, 1, 2, 20, 4, 22, 23, 7, 24, 8, 25, 26, 27, 11, 30, 14, 15, 32 ], [ 29, 1, \
31, 3, 5, 7, 8, 10, 12, 13, 16, 20, 22, 23, 24, 25, 26, 27 ], [ 29, 1, 31, 3, \
5, 7, 8, 11, 12, 13, 17, 20, 21, 23, 24, 25, 26, 28 ], [ 29, 1, 30, 4, 5, 6, 9\
, 10, 11, 12, 14, 20, 21, 22, 24, 26, 27, 28 ], [ 29, 1, 30, 4, 5, 6, 9, 10, 1\
1, 13, 15, 20, 21, 22, 23, 25, 27, 28 ], [ 1, 30, 2, 31, 5, 6, 7, 8, 9, 20, 21\
, 22, 23, 24, 25, 26, 27, 28 ], [ 1, 3, 20, 4, 21, 22, 23, 6, 24, 7, 8, 25, 9,\
 26, 27, 28, 29, 32 ], [ 29, 30, 31, 32, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1\
6, 17, 18, 19 ], [ 2, 31, 3, 32, 7, 8, 10, 11, 12, 15, 16, 17, 18, 19, 23, 26,\
 27, 28 ], [ 2, 31, 3, 32, 7, 8, 10, 11, 13, 14, 16, 17, 18, 19, 24, 25, 27, 2\
8 ], [ 30, 2, 32, 4, 6, 9, 10, 12, 13, 14, 15, 17, 18, 19, 21, 25, 26, 27 ], [\
 30, 2, 32, 4, 6, 9, 11, 12, 13, 14, 15, 16, 18, 19, 22, 25, 26, 28 ], [ 29, 3\
1, 3, 5, 6, 9, 10, 12, 13, 14, 15, 17, 18, 19, 22, 23, 24, 28 ], [ 18, 19, 3, \
21, 5, 6, 23, 24, 9, 27, 11, 12, 29, 13, 14, 31, 15, 16 ], [ 17, 18, 19, 4, 21\
, 5, 22, 23, 7, 8, 26, 10, 11, 29, 13, 30, 14, 16 ], [ 29, 30, 4, 5, 7, 8, 10,\
 11, 12, 15, 16, 17, 18, 19, 21, 22, 24, 25 ], [ 30, 2, 31, 3, 32, 4, 6, 7, 14\
, 15, 16, 17, 19, 20, 25, 26, 27, 28 ], [ 17, 18, 2, 3, 20, 5, 6, 23, 24, 8, 2\
7, 28, 12, 29, 13, 31, 32, 16 ], [ 29, 30, 2, 32, 4, 5, 7, 9, 10, 11, 14, 15, \
18, 20, 21, 22, 25, 26 ], [ 29, 30, 31, 3, 4, 5, 8, 9, 10, 11, 12, 13, 19, 20,\
 21, 22, 23, 24 ] ] )