Zero-sum copies of spanning forests in zero-sum complete graphs

Abstract: For a complete graph

K_{n}

of order

n

, an edge-labeling

c : E (K_{n}) o - 1, 1

satisfying

c (E (K_{n})) = 0

, and a spanning forest

F

of

K_{n}

, we consider the problem to minimize

| c (E (F^{'})) |

over all isomorphic copies

F^{'}

of

F

in

K_{n}

. In particular, we ask under which additional conditions there is a zero-sum copy, that is, a copy

F^{'}

of

F

with

c (E (F^{'})) = 0

. We show that there is always a copy

F^{'}

of

F

with

| c (E (F^{'})) | l e q D e l t a (F) + 1

, where

D e l t a (F)

is the maximum degree of

F

. We conjecture that this bound can be improved to

| c (E (F^{'})) | l e q (D e l t a (F) - 1) / 2

and verify this for

F

being the star

K_{1, n - 1}

. Under some simple necessary divisibility conditions, we show the existence of a zero-sum

P_{3}

-factor, and, for sufficiently large

n

, also of a zero-sum

P_{4}

-factor.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Zero-sum copies of spanning forests in zero-sum complete graphs