Distinguishing partitions of complete multipartite graphs

DOI10.26493/1855-3974.428.296zbMATH Open1338.05117arXiv1301.4583OpenAlexW2113730091WikidataQ129355317 ScholiaQ129355317MaRDI QIDQ2810380FDOQ2810380

Authors: Michael Goff 

Publication date: 1 June 2016

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

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.

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

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

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)

Cited In (7)

• Complete partitions of graphs
• Title not available (Why is that?)
• Complete partitions of graphs
• Vertex partition of a complete multipartite graph into two kinds of induced subgraphs
• Partition of a graph with its complete sub-graphs
• Title not available (Why is that?)
• 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)