Kirszbraun-type theorems for graphs

Abstract: The classical Kirszbraun theorem says that all

1

-Lipschitz functions

f : A l o n g r i g h t a r r o w m a t h b b R^{n}

,

A s u b s e t m a t h b b R^{n}

, with the Euclidean metric have a

1

-Lipschitz extension to

m a t h b b R^{n}

. For metric spaces

X, Y

we say that

Y

is

X

-Kirszbraun if all

1

-Lipschitz functions

f : A l o n g r i g h t a r r o w Y

,

A s u b s e t X

, have a

1

-Lipschitz extension to~

X

. We analyze the case when

X

and

Y

are graphs with the usual path metric. We prove that

m a t h b b Z^{d}

-Kirszbraun graphs are exactly graphs that satisfies a certain Helly property. We also consider complexity aspects of these properties.

Recommendations

Cites work

Cited in

(19)

This page was built for publication: Kirszbraun-type theorems for graphs