Distinguishing chromatic numbers of complements of Cartesian products of complete graphs
| Autor: | Ethan P. White, Karen Seyffarth, Michael S. Cavers |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Mathematics::Combinatorics 010102 general mathematics 0102 computer and information sciences Cartesian product Automorphism 01 natural sciences Graph Theoretical Computer Science Combinatorics Arbitrarily large symbols.namesake Computer Science::Discrete Mathematics 010201 computation theory & mathematics symbols Physics::Accelerator Physics Discrete Mathematics and Combinatorics Chromatic scale 0101 mathematics Mathematics |
| Zdroj: | Discrete Mathematics. 341:2431-2441 |
| ISSN: | 0012-365X |
| Popis: | The distinguishing chromatic number of a graph, G , is the minimum number of colours required to properly colour the vertices of G so that the only automorphism of G that preserves colours is the identity. There are many classes of graphs for which the distinguishing chromatic number has been studied, including Cartesian products of complete graphs (Jerebic and Klavžar, 2010). In this paper we determine the distinguishing chromatic number of the complement of the Cartesian product of complete graphs, providing an interesting class of graphs, some of which have distinguishing chromatic number equal to the chromatic number, and others for which the difference between the distinguishing chromatic number and chromatic number can be arbitrarily large. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect