We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Zero-Sum Copies of Spanning Forests in Zero-Sum Complete Graphs.
- Authors
Mohr, Elena; Pardey, Johannes; Rautenbach, Dieter
- Abstract
For a complete graph K n of order n, an edge-labeling c : E (K n) → { - 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 ′)) | ≤ Δ (F) + 1 , where Δ (F) is the maximum degree of F. We conjecture that this bound can be improved to | c (E (F ′)) | ≤ (Δ (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.
- Subjects
COMPLETE graphs; RAMSEY theory; LOGICAL prediction; GRAPH labelings; RAMSEY numbers
- Publication
Graphs & Combinatorics, 2022, Vol 38, Issue 5, p1
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-022-02539-2