Frucht’s Theorem for the Digraph Factorial
Richard H. Hammack
Discussiones Mathematicae Graph Theory, Tome 33 (2013), p. 329-336 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2013-01-01
EUDML-ID : urn:eudml:doc:268178 
@article{bwmeta1.element.doi-10_7151_dmgt_1661,
     author = {Richard H. Hammack},
     title = {Frucht's Theorem for the Digraph Factorial},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {33},
     year = {2013},
     pages = {329-336},
     zbl = {1292.05133},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1661}
}

Richard H. Hammack. Frucht’s Theorem for the Digraph Factorial. Discussiones Mathematicae Graph Theory, Tome 33 (2013) pp. 329-336. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1661/

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

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

[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] R. Hammack and H. Smith, Zero divisors among digraphs, Graphs Combin. doi:10.1007/s00373-012-1248-x[Crossref] | Zbl 1292.05221

[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] | Zbl 1217.05197

[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). | Zbl 1283.05001

[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] | Zbl 1062.05139

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