Predavatelj: Wilfried Imrich
Regular median graphs with two ends
Joint work with S. Klavzar
Abstract
This talk is concerned with infinite median graphs. Many classes of infinite graphs are so rich that one is content to classify just the vertex transitive ones. In this talk examples are given, where regularity (isovalence) and two-endedness suffice, respectively regularity and linear growth.
It is thus shown that regular median graphs of linear growth are the Cartesian product of finite hypercubes by the two-way infinite path. Such graphs are Cayley graphs and have only two ends.
For cubic median graphs G the condition of linear growth can be replaced by the condition that G has two ends. For higher degree the relaxation to two-ended graphs is not possible, which we demonstrate by an example of a median graph of degree four that has two ends, but nonlinear growth.
The talk ends with conjectures about one-ended median graphs with quadratic, and more generally, with polynomial growth.
