The distinguishing chromatic number of Cartesian products of two complete graphs |
| |
Authors: | Janja Jerebic |
| |
Institution: | a Faculty of Natural Sciences and Mathematics, University of Maribor, Koroška 160, 2000 Maribor, Slovenia b Faculty of Mathematics and Physics, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia |
| |
Abstract: | A labeling of a graph G is distinguishing if it is only preserved by the trivial automorphism of G. The distinguishing chromatic number of G is the smallest integer k such that G has a distinguishing labeling that is at the same time a proper vertex coloring. The distinguishing chromatic number of the Cartesian product is determined for all k and n. In most of the cases it is equal to the chromatic number, thus answering a question of Choi, Hartke and Kaul whether there are some other graphs for which this equality holds. |
| |
Keywords: | Distinguishing chromatic number Graph automorphism Cartesian product of graphs |
本文献已被 ScienceDirect 等数据库收录! |
|