论文标题
在零和跨越树木和零和连接
On zero-sum spanning trees and zero-sum connectivity
论文作者
论文摘要
我们考虑$ 2 $ -Colourings $ f：e（g）\ rightArrow \ {-1，1 \} $ a Graph $ g $带有颜色$ -1 $和$ 1 $ in $ \ mathbb {z} $的$ 1 $的边缘。如果$ f $ f $ f（h）：= \ sum_ {e（h）} f（e）f（e）= 0 $，则$ g $ of $ g $的子图$ h $ of $ g $ of $ g $ $ g $ sub $ g $。我们研究以下类型的问题，在某些情况下获得最佳结果：在$ | f（g）上的哪些条件下，我们可以保证存在$ g $的零和跨越树吗？我们认为的$ g $的类型是完整的图形，$ k_3 $ - free Graphs，$ d $ -trees和最大平面图。我们还回答了一个问题，即任何这样的着色何时包含零和跨越路径或零和跨直径树的最多$ 3 $，这表明直径 - $ 3 $条件是最好的。最后，我们给出了$ g = k_n $的$ | f（k_n）| $，强迫一个有趣的零和连接属性，即，最多4 $的零和长度的零和长度路径加入了任何两个顶点。 本文的一个特征是插值引理的证明，导致了主定理，以上许多结果从中遵循并具有独立感兴趣。
We consider $2$-colourings $f : E(G) \rightarrow \{ -1 ,1 \}$ of the edges of a graph $G$ with colours $-1$ and $1$ in $\mathbb{Z}$. A subgraph $H$ of $G$ is said to be a zero-sum subgraph of $G$ under $f$ if $f(H) := \sum_{e\in E(H)} f(e) =0$. We study the following type of questions, in several cases obtaining best possible results: Under which conditions on $|f(G)|$ can we guarantee the existence of a zero-sum spanning tree of $G$? The types of $G$ we consider are complete graphs, $K_3$-free graphs, $d$-trees, and maximal planar graphs. We also answer the question of when any such colouring contains a zero-sum spanning path or a zero-sum spanning tree of diameter at most $3$, showing in passing that the diameter-$3$ condition is best possible. Finally, we give, for $G = K_n$, a sharp bound on $|f(K_n)|$ by which an interesting zero-sum connectivity property is forced, namely that any two vertices are joined by a zero-sum path of length at most $4$. One feature of this paper is the proof of an Interpolation Lemma leading to a Master Theorem from which many of the above results follow and which can be of independent interest.
