Discussiones Mathematicae Graph Theory 33(2) (2013)
329-336

doi: 10.7151/dmgt.1661

Richard H. Hammack
Department of Mathematics and Applied Mathematics |

A new operation on digraphs was introduced recently as an aid in solving certain
questions regarding cancellation over the direct product of digraphs. Given a digraph
A, its *factorial* A! is certain digraph whose vertex set is the permutations of
V(A). The arc set E(A!) forms a group, and the loops form a subgroup that is isomorphic
to Aut(A). (So E(A!) can be regarded as an extension of Aut(A).)

This note proves an analogue of Frucht's theorem in which Aut(A) is replaced by the group E(A!). Given any finite group G, we show that there is a graph A for which E(A!) ≅ G.

**Keywords:** Frucht's theorem, digraphs, graph automorphisms, digraph factorial

**2010 Mathematics Subject Classification:** 05C25.

[1] | G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs, 5th edition (CRC Press, Boca Raton, FL, 2011). |

[2] | R. Hammack, Direct product cancellation of digraphs, European J. Combin. 34 (2013) 846--858, doi: 10.1016/j.ejc.2012.11.003. |

[3] | R. Hammack, On direct product cancellation of graphs, Discrete Math. 309 (2009) 2538--2543, doi: 10.1016/j.disc.2008.06.004. |

[4] | R. Hammack and H. Smith, Zero divisors among digraphs, Graphs Combin, doi: 10.1007/s00373-012-1248-x. |

[5] | R. Hammack and K. Toman, Cancellation of direct products of digraphs, Discuss. Math. Graph Theory 30 (2010) 575--590, doi: 10.7151/dmgt.1515. |

[6] | R. Hammack, W. Imrich, and S. Klavžar, Handbook of Product Graphs, 2nd edition, Series: Discrete Mathematics and its Applications (CRC Press, Boca Raton, FL, 2011). |

[7] | P. Hell and J. Nešetřil, Graphs and Homomorphisms, Oxford Lecture Series in Mathematics (Oxford Univ. Press, 2004), doi: 10.1093/acprof:oso/9780198528173.001.0001. |

[8] | L. Lovász, On the cancellation law among finite relational structures, Period. Math. Hungar. 1 (1971) 145--156, doi: 10.1007/BF02029172. |

Received 10 September 2011

Revised 19 March 2012

Accepted 22 March 2012