|
This work is centered around the
distinguishing number of graphs, which
was formally introduced in 1996 by Albertson and Collins.
It is the least number of colors needed in a coloring which is not preserved by any non-trivial automorphism. We are investigating the status of
Tucker's infinite motion conjecture (a locally finite graph whose non-trivial automorphisms all move infinitely many vertices has distinguishing number 2).
We also consider generalisations of Tucker's conjecture, e.g. to endomorphism monoids and graphs which are not locally finite. This research has been carried
out in the period 2011–2015, and again 2017–2019,
in cooperation with W.
Imrich (Univ. Leoben), under the auspices of the Doctoral college
Discrete Mathematics
which is funded by the Austrian Science Fund.
|
-
S. Hüning, W. Imrich, J. Kloas, H. Schreiber, and T. Tucker.
Distinguishing graphs of maximum valence 3.
Electronic J. Combinatorics 26 (2019), #P4.36,1-26.
[arxiv: 1709.05797].
-
T. Boiko, J. Cuno, W. Imrich, F. Lehner, and C. E. van de Woestijne.
The Cartesian product
of graphis with loops.
Ars Math. Contemporanea 11 (2016), 1-9.
[MR].
-
F. Lehner and R. G. Möller.
Local finiteness, distinguishing numbers, and Tucker's conjecture.
Electronic Journal of Combinatorics 22/4 (2015), (Research paper
#19).
[MR], [arxiv: 1412.0881].
-
F. Lehner.
Random colorings and automorphism breaking in locally finite graphs.
Combinatorics, Probability and Computing 22/6 (2013), 885-909.
[Zbl], [MR], [doi], [arxiv: 1304.6642].
-
F. Lehner.
Pursuit evasion on
infinite graphcs.
Theoretical Computer Science 655, Part A (2016), 30-40.
[MR], [doi], [arxiv: 1410.8412].
-
F. Lehner and C. Temmel.
Clique trees of infinite locally finite chordal graphs, 2013.
submitted.
[arxiv: 1311.7001].
-
W. Imrich, R. Kalinowski, F. Lehner, and M. Pilśniak.
Endomorphism breaking in graphs.
Electronic Journal of Combinatorics 21 (2014), P1.16, 13pp.
[Zbl], [MR].
-
F. Lehner.
Distinguishing graphs with intermediate growth.
Combinatorica 36 (2016), 333-347.
[MR], [doi], [arxiv: 1301.0393].
-
J. Cuno, W. Imrich, and F. Lehner.
Distinguishing graphs with infinite motion and nonlinear growth.
Ars Mathematica Contemporanea 7/1 (2014), 201-213.
[Zbl], [MR].
-
M. Hamann, F. Lehner, and J. Pott.
Extending cycles locally to Hamilton cycles.
Electronic J. Combinatorics 23/1 (2016), #P1.49, 17pp.
[MR].
-
F. Lehner.
On spanning tree packings of highly edge connected graphs.
J. Comb. Theory, Series B 105 (2014), 93-126.
[Zbl], [MR], [doi], [arxiv: 1109.6787].
-
F. Lehner.
The line graph of every locally finite 6-edge-connected graph with finitely
many ends is Hamiltonian.
Master's thesis, Technische Universität Graz, 2011.
|
