图的奇数生成树

Odd spanning trees of a graph

摘要 Abstract

若图 $G=(V,E)$ 的任意顶点 $v\in V$ 的度数 $d_G(v)$ 均为奇数(或偶数),则称该图为奇数图(或偶数图)。显然,奇数图的阶数必为偶数。本文证明了每个 4-边连通的偶数阶图都存在一个连通的奇数因子。若生成树 $T$ 不包含度数为二的顶点,则称其为同胚不可约生成树(简称 HIST)。显然,奇数生成树必为 HIST。1990年,Albertson、Berman、Hutchinson 和 Thomassen 证明了任意阶为 $n$ 且最小度 $\delta(G)\geq \min\{\frac{n}{2}, 4\sqrt{2n}\}$ 的连通图都包含一个 HIST。我们证明了每个两部分均为偶数的完全二部图均不存在奇数生成树,从而对于任意可被 4 整除的偶数 $n$,存在一个阶数为 $n$ 且最小度为 $\frac{n}{2}$ 的图没有奇数生成树。此外,我们还证明了每个阶为 $n$ 且最小度 $\delta(G)\geq \frac{n}{2}+1$ 的图都存在奇数生成树,并进一步刻画了所有具有奇数生成树的分裂图。作为应用,对于任意直径至少为 4 的图 $G$,其补图 $\overline{G}$ 包含一个跨度奇数双星。最后,我们给出了一个三角形自由图 $G$ 的补图包含奇数生成树的充要条件。同时提出了一些相关开放问题。

A graph $G=(V,E)$ is said to be odd (or even, resp.) if $d_G(v)$ is odd (or even, resp.) for any $v\in V$. Trivially, the order of an odd graph must be even. In this paper, we show that every 4-edge connected graph of even order has a connected odd factor. A spanning tree $T$ of $G$ is called a homeomorphically irreducible spanning tree (HIST by simply) if $T$ contains no vertex of degree two. Trivially, an odd spanning tree must be a HIST. In 1990, Albertson, Berman, Hutchinson, and Thomassen showed that every connected graph of order $n$ with $\delta(G)\geq \min\{\frac n 2, 4\sqrt{2n}\}$ contains a HIST. We show that every complete bipartite graph with both parts being even has no odd spanning tree, thereby for any even integer $n$ divisible by 4, there exists a graph of order $n$ with the minimum degree $\frac n 2$ having no odd spanning tree. Furthermore, we show that every graph of order $n$ with $\delta(G)\geq \frac n 2 +1$ has an odd spanning tree. We also characterize all split graphs having an odd spanning tree. As an application, for any graph $G$ with diameter at least 4, $\overline{G}$ has a spanning odd double star. Finally, we also give a necessary and sufficient condition for a triangle-free graph $G$ whose complement contains an odd spanning tree. A number of related open problems are proposed.