Advertisement
Published in:
2020 | OriginalPaper | Chapter
List Distinguishing Number of \(p^{\text {th}}\) Power of Hypercube and Cartesian Powers of a Graph
Authors : L. Sunil Chandran, Sajith Padinhatteeri, Karthik Ravi Shankar
Published in: Algorithms and Discrete Applied Mathematics
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 \(v\in 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 \(\mathcal {L}\)-distinguishable where \(\mathcal {L}=\{L(v)\}_{v\in V(G)}\). The list distinguishing number of a graph, denoted \(D_l(G)\), is the minimum integer k such that every collection of lists \(\mathcal {L}\) with \(|L(v)|=k\) admits an \(\mathcal {L}\)-distinguishing coloring. In this paper, we prove that
-
when a connected graph G is prime with respect to the Cartesian product then \(D_l(G^r) = D(G^r)\) for \(r \ge 3\) where \(G^r\) is the Cartesian product of the graph G taken r times.
-
The \(p^{th}\) 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 \ge 7, p \ge 1\), where \(Q_n=K_2^n\) is the hypercube of dimension n.