Distinguishing threshold of graphs

DOI10.1002/JGT.22923MaRDI QIDQ6074586zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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$.

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

Cites work

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

Cited in

(7)

• 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
• 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

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)