Projects per year

## Abstract

Let c and c
^{′} be edge or vertex colourings of a graph G. The stabiliser of c is the set of automorphisms of G that preserve the colouring. We say that c
^{′} is less symmetric than c if the stabiliser of c
^{′} is contained in the stabiliser of c. We show that if G is not a bicentred tree, then for every vertex colouring of G there is a less symmetric edge colouring with the same number of colours. On the other hand, if T is a tree, then for every edge colouring there is a less symmetric vertex colouring with the same number of colours. Our results can be used to characterise those graphs whose distinguishing index is larger than their distinguishing number.

Original language | English |
---|---|

Article number | 111959 |

Number of pages | 8 |

Journal | Discrete Mathematics |

Volume | 343 |

Issue number | 9 |

DOIs | |

Publication status | Published - 2020 |

## Keywords

- Distinguishing index
- Distinguishing number
- Graph automorphism
- Graph colouring

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fields of Expertise

- Information, Communication & Computing

## Projects

- 1 Finished