Distinguishing threshold of graphs

DOI10.1002/JGT.22923zbMATH Open1522.05141arXiv2107.14767OpenAlexW3190914299MaRDI QIDQ6074586FDOQ6074586

Authors: Mohammad Hadi Shekarriz, B. Ahmadi, M. H. Shirdareh Haghighi 

Publication date: 12 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: A vertex coloring of a graph $G$ is called distinguishing if no non-identity automorphisms of $G$ can preserve it. The distinguishing number of $G$, denoted by $D(G)$, is the minimum number of colors required for such a coloring, and the distinguishing threshold of $G$, denoted by $heta(G)$, is the minimum number $k$ such that every $k$-coloring of $G$ is distinguishing. As an alternative definition, $heta(G)$ is one more than the maximum number of cycles in the cycle decomposition of automorphisms of $G$. In this paper, we characterize $heta(G)$ when $G$ is disconnected. Afterwards, we prove that, although for every positive integer $keq2$ there are infinitely many graphs whose distinguishing thresholds are equal to $k$, we have $heta(G)=2$ if and only if $vertV(G)vert=2$. Moreover, we show that if $heta(G)=3$, then either $G$ is isomorphic to one of the four graphs on~3 vertices or it is of order $2p$, where $peq3,5$ is a prime number. Furthermore, we prove that $heta(G)=D(G)$ if and only if $G$ is asymmetric, $K_n$ or $overline{K}_n$. Finally, we consider all generalized Johnson graphs, $J(n,k,i)$, which are the graphs on all $k$-subsets of $1,ldots,n$ where two vertices $A$ and $B$ are adjacent if $|AcapB|=k-i$. After studying their automorphism groups and distinguishing numbers, we calculate their distinguishing thresholds as $heta(J(n,k,i))=nchoosek-n-2choosek-1+1$, unless $k=fracn2$ and $iinfrack2,k$ in which case we have $heta(J(n,k,i))=nchoosek$.

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

Recommendations

• Threshold graphs
• Threshold Dimension of Graphs
• Threshold graphs and related topics
• Some notes on the threshold graphs
• The threshold dimension of a graph
• scientific article; zbMATH DE number 568830
• Thresholds for classes of intersection graphs
• Threshold hypergraphs
• Recognizing cographs and threshold graphs through a classification of their edges
• scientific article; zbMATH DE number 1263242

zbMATH Keywords

symmetry breakingdistinguishing coloringdistinguishing thresholdgeneralized Johnson graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Enumeration in graph theory (05C30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Symmetry breaking in graphs
• Graph theory
• The structure of automorphism groups of Cayley graphs and maps.
• Distinguishing number of countable homogeneous relational structures
• The distinguishing number of Cartesian products of complete graphs
• Distinguishing partitions and asymmetric uniform hypergraphs
• Distinguishing maps
• The distinguishing chromatic number
• A note on the asymptotic and computational complexity of graph distinguishability
• Distinguishing infinite graphs
• Distinguishing labellings of group action on vector spaces and graphs
• Endomorphism breaking in graphs
• Linear Graphs of Degree ≤ 6 and their Groups
• Distinguishing graphs by edge-colourings
• Bounds for distinguishing invariants of infinite graphs
• Using determining sets to distinguish Kneser graphs
• Distinguishing Cartesian powers of graphs
• Automorphisms and regular embeddings of merged Johnson graphs
• The distinguishing number of the hypercube
• The distinguishing number and distinguishing index of the lexicographic product of two graphs
• Distinguishing graphs by total colourings
• Asymmetric trees with two prescribed degrees
• The group of an X-join of graphs
• Number of distinguishing colorings and partitions
• Automorphism groups of circulant graphs -- a survey
• THE DISTINGUISHING NUMBERS OF MERGED JOHNSON GRAPHS

Cited In (7)

• Edge-locating coloring of graphs
• Threshold graphs
• Recognizing cographs and threshold graphs through a classification of their edges
• Coarse distinguishability of graphs with symmetric growth
• Distinguishing generalized Mycielskian graphs
• Number of colors needed to break symmetries of a graph by an arbitrary edge coloring
• The number of distinguishing colorings of a Cartesian product graph

This page was built for publication: Distinguishing threshold of graphs

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