Distinguishing number and distinguishing index of some operations on graphs
Saeid Alikhani, Samaneh Soltani · Journal of Information and Optimization Sciences · 2018
The distinguishing number (index) D(G) (Dʹ(G)) of a graph G is the least integer d such that G has an vertex labeling (edge labeling) with d labels that is preserved only by a trivial automorphism. We examine the effects on D(G) and Dʹ(G) when G is modified by operations on vertex and edge of G. Let G be a connected graph of order n ≥ 3. We show that –1 ≤ D(G – v) – D(G) ≤ D(G), where G – v denotes the graph obtained from G by removal of a vertex v and all edges incident to v and these inequalities are true for the distinguishing index. Also we prove that |D(G – e) – D(G)| ≤ 2 and –1 ≤ Dʹ (G – e) – Dʹ(G) ≤ 2, where G – e denotes the graph obtained from G by simply removing the edge e. Finally we consider the vertex contraction and the edge contraction of G and prove that the edge contraction decrease the distinguishing number (index) of G by at most one and increase by at most 3D(G) (3Dʹ(G)).