The distinguishing index of graphs with at least one cycle is not more than its distinguishing number

arXiv1710.08143MaRDI QIDQ6292896FDOQ6292896

Samaneh Soltani, Saeid Alikhani

Publication date: 23 October 2017

Abstract: The distinguishing number (index) $D(G)$ ($D^{\prime }(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^{\prime }(G)leqD(G)+1$. The complete characterization of finite trees $T$ with $D^{\prime }(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^{\prime }(G)leqD(G)$. Finally, we characterize all connected graphs for which $D^{\prime }(G)leqD(G)$.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Group actions on combinatorial structures (05E18)

This page was built for publication: The distinguishing index of graphs with at least one cycle is not more than its distinguishing number

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