{
  "id": "2107.14767",
  "version": "v1",
  "published": "2021-07-30T17:19:13.000Z",
  "updated": "2021-07-30T17:19:13.000Z",
  "title": "Distinguishing threshold of graphs",
  "authors": [
    "Mohammad Hadi Shekarriz",
    "Bahman Ahmadi",
    "Seyed Alireza Talebpoor Shirazi Fard",
    "Mohammad Hasan Shirdareh Haghighi"
  ],
  "comment": "19 pages, 6 figures",
  "categories": [
    "math.CO"
  ],
  "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 coloring. The distinguishing threshold of $G$, denoted by $\\theta(G)$, is the minimum number $k$ of colors such that every $k$-coloring of $G$ is distinguishing. In this paper, we study $\\theta(G)$, find its relation to the cycle structure of the automorphism group and prove that $\\theta(G)=2$ if and only if $G$ is isomorphic to $K_2$ or $\\overline{K_2}$. Moreover, we study graphs that have the distinguishing threshold equal to 3 or more and prove that $\\theta(G)=D(G)$ if and only if $G$ is asymmetric, $K_n$ or $\\overline{K_n}$. Finally, we consider Johnson scheme graphs for their distinguishing number and threshold concludes the paper.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-07-30T17:19:13.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C09",
      "05C15",
      "05C25",
      "05C30"
    ],
    "keywords": [
      "minimum number",
      "johnson scheme graphs",
      "distinguishing number",
      "cycle structure",
      "threshold concludes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}