Projekte pro Jahr

## Abstract

If a graph G has distinguishing number 2, then there exists a partition of its vertex set into two parts, such that no nontrivial automorphism of G fixes setwise the two parts. Such a partition is called a 2-distinguishing coloring of G, and the parts are called its color classes. If G admits such a coloring, it is often possible to find another in which one of the color classes is sparse in a certain sense. In this case we say that G has 2-distinguishing density zero. An extreme example of this would be an infinite graph admitting a 2-distinguishing coloring in which one of the color classes is finite. The Infinite Motion Conjecture is a well-known open conjecture about 2-distinguishability. A graph G is said to have infinite motion if every nontrivial automorphism of G moves infinitely many vertices, and the conjecture states that every connected, locally finite graph with infinite motion is 2-distinguishable. In this paper we show that for many classes of graphs for which the Infinite Motion Conjecture is known to hold, the graphs have 2-distinguishing density zero.

Originalsprache | englisch |
---|---|

Aufsatznummer | 103139 |

Seitenumfang | 10 |

Fachzeitschrift | European Journal of Combinatorics |

Jahrgang | 89 |

DOIs | |

Publikationsstatus | Veröffentlicht - 2020 |

## ASJC Scopus subject areas

- Diskrete Mathematik und Kombinatorik

## Fields of Expertise

- Information, Communication & Computing

## Fingerprint

Untersuchen Sie die Forschungsthemen von „Distinguishing density and the Distinct Spheres Condition“. Zusammen bilden sie einen einzigartigen Fingerprint.## Projekte

- 1 Abgeschlossen