Distinguishing Cartesian Products of Countable Graphs

Ehsan Estaji, Wilfried Imrich, Rafal Kalinowski, Monika Pilsniak, Thomas Tucker

Research output: Contribution to journalArticleResearchpeer-review

12 Citations (Scopus)


The distinguishing number D(G) of a graph G is the minimum number
of colors needed to color the vertices of G such that the coloring is preserved
only by the trivial automorphism. In this paper we improve results about
the distinguishing number of Cartesian products of finite and infinite graphs
by removing restrictions to prime or relatively prime factors.
Keywords: vertex coloring, distinguishing number, automorphisms, infinite
graphs, Cartesian and weak Cartesian product.
Original languageEnglish
Pages (from-to)155-164
Number of pages10
JournalDiscussiones mathematicae / Graph theory
Issue number1
Publication statusPublished - 1 Dec 2017

Cite this