Wilfried Imrich
(Montanuniversität Leoben, Austria)

Infinite Median Graphs with Two Ends
(joint work with Sandi Klavzar)

Abstract. Among infinite graphs there are some that are just bareley infinite - the graphs of polynomial, and in particular those of linear growth. But even the class of regular graphs with linear growth is very rich. For further classification one takes recourse to vertex transitivity and the number of ends.

For median graphs the situation is different. Median graphs are generalizations of trees and can be characterized as the retracts of hypercubes. For them regularity, two-endedness and linear growth alone, without vertex transitivity, impose a strong restriction on their structure.

It is thus shown that regular median graphs with two ends and linear growth are the Cartesian product of finite hypercubes by the two-way infinite path.

For cubic median graphs the condition of linear growth is not even necessary. There is only one cubic median graph with two ends - the Cartesian product of an edge by a two-sided infinite path.

For higher degree such a relaxation to two-ended graphs is not possible, as a median graph of degree four that has two ends, but nonlinear growth, shows.

This leads to several conjectures about the classification of regular median graphs, resp. vertex transitive median graphs, by growth rates and the number of ends.