List Distinguishing Number of pth Power of Hypercube and Cartesian Powers of a Graph

Chandran, L. Sunil and Padinhatteeri, Sajith and Ravi Shankar, Karthik (2020) List Distinguishing Number of pth Power of Hypercube and Cartesian Powers of a Graph. In: 6th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2020, 13-15 February 2020, Hyderabad.

Full text not available from this repository. (Request a copy)

Abstract

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 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 -distinguishable where The list distinguishing number of a graph, denoted is the minimum integer k such that every collection of lists with admits an distinguishing coloring. In this paper, we prove thatwhen a connected graph G is prime with respect to the Cartesian product then for where is the Cartesian product of the graph G taken r times. The power of a graph (Some authors use to denote the pth power of G, to avoid confusion with the notation of Cartesian power of graph G we use for the pth power of G.) G is the graph 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 for all where is the hypercube of dimension n. © 2020, Springer Nature Switzerland AG.

[error in script]

IITH Creators: