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

MaRDI QIDQ6292896zbMATH OpenFDO

Authors Saeid Alikhani, Samaneh Soltani

Publication date 23 October 2017

Mathematics Subject Classification ID

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

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

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)