Distinguishing number and distinguishing index of some operations on graphs. Issue 5 (4th July 2018)

• Record Type: Journal Article
• Authors: Alikhani, Saeid; Soltani, Samaneh
• Is Part Of: Journal of information & optimization sciences. Volume 39:Issue 5(2018)
• Page Start: 1047
• Page End: 1059
• Publication Date: 2018-07-04
• Subjects: 05C15 -- 05E18; Distinguishing index -- Distinguishing number -- Edge contraction; Electronic data processing -- Periodicals; Information science -- Periodicals; Mathematical optimization -- Periodicals; 519.6
• DOI: 10.1080/02522667.2017.1294304
• Languages: English
• ISSNs: 0252-2667

Abstract

Abstract: 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 3 D ( G ) (3 D ʹ( G )).