# Frucht’s Theorem for the Digraph Factorial

• Volume: 33, Issue: 2, page 329-336
• ISSN: 2083-5892

top

## Abstract

top
To every graph (or digraph) A, there is an associated automorphism group Aut(A). Frucht’s theorem asserts the converse association; that for any finite group G there is a graph (or digraph) A for which Aut(A) ∼= G. 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.

## How to cite

top

Richard H. Hammack. "Frucht’s Theorem for the Digraph Factorial." Discussiones Mathematicae Graph Theory 33.2 (2013): 329-336. <http://eudml.org/doc/268178>.

@article{RichardH2013,
abstract = {To every graph (or digraph) A, there is an associated automorphism group Aut(A). Frucht’s theorem asserts the converse association; that for any finite group G there is a graph (or digraph) A for which Aut(A) ∼= G. 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.},
author = {Richard H. Hammack},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Frucht’s theorem; digraphs; graph automorphisms; digraph factorial; Frucht's theorem},
language = {eng},
number = {2},
pages = {329-336},
title = {Frucht’s Theorem for the Digraph Factorial},
url = {http://eudml.org/doc/268178},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Richard H. Hammack
TI - Frucht’s Theorem for the Digraph Factorial
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 2
SP - 329
EP - 336
AB - To every graph (or digraph) A, there is an associated automorphism group Aut(A). Frucht’s theorem asserts the converse association; that for any finite group G there is a graph (or digraph) A for which Aut(A) ∼= G. 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.
LA - eng
KW - Frucht’s theorem; digraphs; graph automorphisms; digraph factorial; Frucht's theorem
UR - http://eudml.org/doc/268178
ER -

## References

top
1. [1] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs, 5th edition (CRC Press, Boca Raton, FL, 2011). Zbl1211.05001
2. [2] R. Hammack, Direct product cancellation of digraphs, European J. Combin. 34 (2013) 846-858. doi:10.1016/j.ejc.2012.11.003[Crossref] Zbl1260.05067
3. [3] R. Hammack, On direct product cancellation of graphs, Discrete Math. 309 (2009) 2538-2543. doi:10.1016/j.disc.2008.06.004[Crossref][WoS]
4. [4] R. Hammack and H. Smith, Zero divisors among digraphs, Graphs Combin. doi:10.1007/s00373-012-1248-x[Crossref] Zbl1292.05221
5. [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[Crossref] Zbl1217.05197
6. [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). Zbl1283.05001
7. [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[Crossref] Zbl1062.05139
8. [8] L. Lovász, On the cancellation law among finite relational structures, Period. Math. Hungar. 1 (1971) 145-156. doi:10.1007/BF02029172[Crossref] Zbl0223.08002

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.