A graph G is said to be k-distinguishable if every vertex of the graph can be colored from a set of k colors such that no non-trivial automorphism fixes every color class. The distinguishing number D(G) is the least integer k for which G is k-distinguishable. If for each v ∈ V(G) we have a list L(v) of colors, and we stipulate that the color assigned to vertex v comes from its list L(v) then G is said to be L-distinguishable where L = {L(v)}_(v∈V(G)). The list distinguishing number of a graph, denoted D_l(G), is the minimum integer k such that every collection of lists L with |L(v)| = k admits an L-distinguishing coloring. In this paper, we prove that: 1. when a connected graph G is prime with respect to the Cartesian product then D_l(G~r) = D(G~r) for r ≥ 3 where G~r is the Cartesian product of the graph G taken r times. 2. The pth power of a graph (Some authors use G~p to denote the pth power of G, to avoid confusion with the notation of Cartesian power of graph G we use G~([p]) for the pth power of G.) G is the graph G~([p]), whose vertex set is V(G) and in which two vertices are adjacent when they have distance less than or equal to p. We determine D_l (Q_n~([p])) for all n ≥ 7, p ≥ 1, where Q_n = K_2~n is the hypercube of dimension n.
展开▼
