The cost number and the determining number of a graph

Abstract

The distinguishing number $D(G)$ of a graph $G$ is the least integer $d$ such that $G$ has an vertex labeling with $d$ labels that is preserved only by a trivial automorphism. The minimum size of a label class in such a labeling of $G$ with $D(G)=d$ is called the cost of $d$-distinguishing $G$ and is denoted by ${\rho }_d(G)$. A set of vertices $S\subseteq V(G)$ is a determining set for $G$ if every automorphism of $G$ is uniquely determined by its action on $S$. The determining number of $G$, Det(G), is the minimum cardinality of determining sets of $G$. In this paper we obtain some general upper and lower bounds for ${\rho }_d(G)$ based on Det(G). Finally, we compute the cost and the determining number for the friendship graphs and corona product of two graphs.

8 pages