Distinguishing partitions of complete multipartite graphs

DOI10.26493/1855-3974.428.296MaRDI QIDQ2810380zbMATH OpenOpenAlexWikidataFDO

Authors Michael Goff

Publication date 1 June 2016

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.4583

zbMATH Keywords

complete multipartite graphcombinatorial speciestree enumerationdistinguishing partition

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Hypergraphs (05C65) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25)

Abstract: A extit{distinguishing partition} of a group $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 $m_1$ parts of size $n_1$ and $m_2$ parts of size $n_2$ for small $n_1$, $m_2$ and large $m_1$, $n_2$. A key tool in making the estimate is counting the number of trees of particular classes.

Recommendations

• Distinguishing partitions and asymmetric uniform hypergraphs
• Number of distinguishing colorings and partitions
• Distinguishing colorings of Cartesian products of complete graphs
• Graphs with large distinguishing chromatic number
• Distinguishing numbers for graphs and groups

Cited in

(7)

• Complete partitions of graphs
• scientific article; zbMATH DE number 5077172 (Why is no real title available?)
• Vertex partition of a complete multipartite graph into two kinds of induced subgraphs
• Complete partitions of graphs
• Partition of a graph with its complete sub-graphs
• scientific article; zbMATH DE number 4008444 (Why is no real title available?)
• Distinguishing partitions and asymmetric uniform hypergraphs

This page was built for publication: Distinguishing partitions of complete multipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2810380)