Distinguishing number and distinguishing index of some operations on graphs

摘要

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