Skip to main content
Article
List-Distinguishing Cartesian Products of Cliques
Discrete Mathematics (2019)
  • Michael Ferrara, University of Colorado, Denver
  • Zoltan Füredi, Alfréd Rényi Institute of Mathematics
  • Sogol Jahanbekam, Rochester Institute of Technology
  • Paul Wenger, Rochester Institute of Technology
Abstract
The distinguishing number of a graph G, denoted D(G), is the minimum number of colors needed to produce a coloring of the vertices of G so that every nontrivial isomorphism interchanges vertices of different colors. A list assignment L on a graph G is a function that assigns each vertex of G a set of colors. An L-coloring of G is a coloring in which each vertex is colored with a color from L(v). The list distinguishing number of G, denoted Dℓ(G) is the minimum k such that every list assignment L that assigns a list of size at least k to every vertex permits a distinguishing L-coloring. In this paper, we prove that when and n is large enough, the distinguishing and list-distinguishing numbers of Kn□Km agree for almost all m>n, and otherwise differ by at most one. As a part of our proof, we give (to our knowledge) the first application of the Combinatorial Nullstellensatz to the graph distinguishing problem and also prove an inequality for the binomial distribution that may be of independent interest.
Keywords
  • distinguishing,
  • list distinguishing
Publication Date
July, 2019
DOI
10.1016/j.disc.2019.03.001
Publisher Statement
The Version of Record for this article was published in Discrete Mathematics, volume 342, issue 7, 2019 and can be found online at this link.

This manuscript can also be found on Arxiv.org at this link.

SJSU users: use the following link to login and access the article via SJSU databases.
Citation Information
Michael Ferrara, Zoltan Füredi, Sogol Jahanbekam and Paul Wenger. "List-Distinguishing Cartesian Products of Cliques" Discrete Mathematics Vol. 342 Iss. 7 (2019) p. 2012 - 2022 ISSN: 0012-365X
Available at: http://works.bepress.com/sogol-jahanbekam/2/