ORCID Profile
0000-0001-6640-4858
Current Organisation
Deakin University
Does something not look right? The information on this page has been harvested from data sources that may not be up to date. We continue to work with information providers to improve coverage and quality. To report an issue, use the Feedback Form.
Publisher: Elsevier BV
Date: 09-2020
Publisher: Wiley
Date: 28-12-2022
DOI: 10.1002/JGT.22923
Abstract: A vertex coloring of a graph is called distinguishing if no nonidentity automorphisms of can preserve it. The distinguishing number of , denoted by , is the minimum number of colors required for such a coloring, and the distinguishing threshold of , denoted by , is the minimum number such that every ‐coloring of is distinguishing. As an alternative definition, is one more than the maximum number of cycles in the cycle decomposition of automorphisms of . In this paper, we characterize when is disconnected. Afterwards, we prove that, although for every positive integer there are infinitely many graphs whose distinguishing thresholds are equal to , we have if and only if . Moreover, we show that if , then either is isomorphic to one of the four graphs on three vertices or it is of order , where is a prime number. Furthermore, we prove that if and only if is asymmetric, or . Finally, we consider all generalized Johnson graphs, , which are the graphs on all ‐subsets of where two vertices and are adjacent if . After studying their automorphism groups and distinguishing numbers, we calculate their distinguishing thresholds as , unless and in which case we have .
Publisher: University of Zielona Góra, Poland
Date: 2018
DOI: 10.7151/DMGT.1994
Publisher: AIP Publishing
Date: 03-2022
DOI: 10.1063/5.0062801
Abstract: We discuss representations and colorings of orthogonality hypergraphs in terms of their two-valued states interpretable as classical truth assignments. Such hypergraphs, if they allow for a faithful orthogonal representation, have quantum mechanical realizations in terms of intertwined contexts or maximal observables that are widely discussed as empirically testable criteria for contextuality. A reconstruction is possible for the class of perfectly separable hypergraphs. Colorings can be constructed from a minimal set of two-valued states. Some ex les from exempt categories are presented, which either cannot be reconstructed by two-valued states or whose two-valued states cannot yield a chromatic number that is equal to the maximal clique number.
Publisher: The Electronic Journal of Combinatorics
Date: 14-07-2017
DOI: 10.37236/6362
Abstract: We consider infinite graphs. The distinguishing number $D(G)$ of a graph $G$ is the minimum number of colours in a vertex colouring of $G$ that is preserved only by the trivial automorphism. An analogous invariant for edge colourings is called the distinguishing index, denoted by $D'(G)$. We prove that $D'(G)\\leq D(G)+1$. For proper colourings, we study relevant invariants called the distinguishing chromatic number $\\chi_D(G)$, and the distinguishing chromatic index $\\chi'_D(G)$, for vertex and edge colourings, respectively. We show that $\\chi_D(G)\\leq 2\\Delta(G)-1$ for graphs with a finite maximum degree $\\Delta(G)$, and we obtain substantially lower bounds for some classes of graphs with infinite motion. We also show that $\\chi'_D(G)\\leq \\chi'(G)+1$, where $\\chi'(G)$ is the chromatic index of $G$, and we prove a similar result $\\chi''_D(G)\\leq \\chi''(G)+1$ for proper total colourings. A number of conjectures are formulated.
Publisher: Springer Science and Business Media LLC
Date: 29-12-2022
Publisher: Informa UK Limited
Date: 08-2012
No related grants have been discovered for Mohammad Hadi Shekarriz.