Distinguishing numbers and distinguishing indices of oriented graphs (Q2197442)

A distinguishing $r$-vertex labeling ($r$-edge labeling) of an undirected graph $G$ is a mapping \(\lambda\) from the set of vertices (the set of edges) of $G$ to the set of labels $\{1,2,\dots,r\}$ such that no non-trivial automorphism of $G$ preserves all the vertex (edge) labels. The distinguishing number $D(G)$ and the distinguishing index \(D^\prime ( G )\) of $G$ are then the smallest $r$ for which $G$ admits a distinguishing $r$-vertex labeling or $r$-edge labeling respectively. The distinguishing chromatic number \(D_\chi ( G )\) and the distinguishing chromatic index \(D_{\chi^\prime} ( G )\) are defined similarly, with the additional requirement that the corresponding labeling must be a proper coloring. An oriented graph is a digraph with no loops and no pairs of opposite arcs. In this paper, the authors give four parameters for oriented graphs whose underlying graph is a path, a cycle, a complete graph or a complete bipartite graph. Also, they find the minimum and maximum values, taken over all possible orientations of the corresponding underlying graph, except for the minimum values for unbalanced complete bipartite graphs \(K_{m , n}\) with $m=2,3$ or 4 and \(n > 3, 6\) or 13 respectively, or \(m \geq 5\) and \(n > 2^m - \left\lceil \frac{ m}{ 2}\right\rceil \), for which they provide the upper bounds only.