Distinguishing partitions of complete multipartite graphs

Michael Goff


distinguishing partition of a set X with automorphism group aut(X) is a partition of X that is fixed by no nontrivial element of aut(X). In the event that X is a complete multipartite graph with its automorphism group, the existence of a distinguishing partition is equivalent to the existence of an asymmetric hypergraph with prescribed edge sizes. An asymptotic result is proven on the existence of a distinguishing partition when X is a complete multipartite graph with m1 parts of size n1 and m2 parts of size n2 for small n1m2 and large m1n2. A key tool in making the estimate is counting the number of trees of particular classes.


Complete multipartite graph, distinguishing partition, combinatorial species, tree enumeration.

Full Text:


DOI: https://doi.org/10.26493/1855-3974.428.296

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications