Distinguishing number and distinguishing index of strong product of two graphs

Original · EN

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. The strong product G H of two graphs G and H is the graph with vertex set V (G)× V (H) and edge set {{(x₁, x₂), (y₁, y₂)} | xᵢyᵢ ∈ E(Gᵢ) or xᵢ = yᵢ for each 1 ≤ i ≤ 2.}. In this paper we study the distinguishing number and the distinguishing index of strong product of two graphs. We prove that for every k ≥ 2, the k-th strong power of a connected S-thin graph G has distinguishing index equal 2.