Distinguishing density and the Distinct Spheres Condition

Publikationen: Beitrag in FachzeitschriftArtikelForschung(peer-reviewed)

Standard

Distinguishing density and the Distinct Spheres Condition. / Imrich, Wilfried; Lehner, Florian; Smith, Simon M. .

in: European journal of combinatorics, Jahrgang 89.2020, Nr. October, 103139, 10.2020.

Publikationen: Beitrag in FachzeitschriftArtikelForschung(peer-reviewed)

Author

Imrich, Wilfried ; Lehner, Florian ; Smith, Simon M. . / Distinguishing density and the Distinct Spheres Condition. in: European journal of combinatorics. 2020 ; Jahrgang 89.2020, Nr. October.

Bibtex - Download

@article{3f0326244b994dccbe15204b7c0f32f3,
title = "Distinguishing density and the Distinct Spheres Condition",
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.",
author = "Wilfried Imrich and Florian Lehner and Smith, {Simon M.}",
year = "2020",
month = oct,
doi = "10.1016/j.ejc.2020.103139",
language = "English",
volume = "89.2020",
journal = "European journal of combinatorics",
issn = "0195-6698",
publisher = "Academic Press Inc.",
number = "October",

}

RIS (suitable for import to EndNote) - Download

TY - JOUR

T1 - Distinguishing density and the Distinct Spheres Condition

AU - Imrich, Wilfried

AU - Lehner, Florian

AU - Smith, Simon M.

PY - 2020/10

Y1 - 2020/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85083880136&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2020.103139

DO - 10.1016/j.ejc.2020.103139

M3 - Article

VL - 89.2020

JO - European journal of combinatorics

JF - European journal of combinatorics

SN - 0195-6698

IS - October

M1 - 103139

ER -