Name
Abstract | ||
|---|---|---|
For a complete graph
$$K_n$$
of order n, an edge-labeling
$$c:E(K_n)\rightarrow \{ -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'))|\le \Delta (F)+1$$
, where
$$\Delta (F)$$
is the maximum degree of F. We conjecture that this bound can be improved to
$$|c(E(F'))|\le (\Delta (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. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/s00373-022-02539-2 | Graphs and Combinatorics |
Keywords | DocType | Volume |
Zero-sum subgraph, Zero-sum Ramsey theory | Journal | 38 |
Issue | ISSN | Citations |
5 | 0911-0119 | 0 |
PageRank | References | Authors |
0.34 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Elena Mohr | 1 | 0 | 0.34 |
| Johannes Pardey | 2 | 0 | 0.34 |
| Dieter Rautenbach | 3 | 946 | 138.87 |