{
  "id": "1710.08143",
  "version": "v1",
  "published": "2017-10-23T08:33:34.000Z",
  "updated": "2017-10-23T08:33:34.000Z",
  "title": "The distinguishing index of graphs with at least one cycle is not more than its distinguishing number",
  "authors": [
    "Saeid Alikhani",
    "Samaneh Soltani"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The distinguishing number (index) $D(G)$ ($D'(G)$) of a graph $G$ is the least integer $d$ such that $G$ has an vertex (edge) labeling with $d$ labels that is preserved only by the trivial automorphism. It is known that for every graph $G$ we have $D'(G) \\leq D(G) + 1$. The complete characterization of finite trees $T$ with $D'(T)=D(T)+ 1$ has been given recently. In this note we show that if $G$ is a finite connected graph with at least one cycle, then $D'(G)\\leq D(G)$. Finally, we characterize all connected graphs for which $D'(G) \\leq D(G)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-10-23T08:33:34.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05E18"
    ],
    "keywords": [
      "distinguishing number",
      "distinguishing index",
      "complete characterization",
      "trivial automorphism",
      "finite trees"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}