论文标题
在跨越树的边缘图
On spanning tree edge denpendences of graphs
论文作者
论文摘要
令$τ（g）$和$τ_g（e）$为连接图$ g $的跨越树的数量，以及包含edge $ e $的$ g $的生成树的数量。比率$ d_ {g}（e）=τ_{g}（e）/τ（g）$称为$ e $的生成树边缘密度，或简单的$ e $密度。最大密度$ \ mbox {dep}（g）= \ max \ limits_ {e \ in E（g）} d_ {g}（e）$称为$ g $的分布树边缘依赖性，或简单地依赖$ g $。给定（0,1）$中的有理数$ p/q \，如果存在图$ g $，而e（g）$中的edge $ e \则$ d_ {g}（e）= p/q $，那么我们说密度$ p/q $是构造的。更特别地，如果存在图$ g $，则$ \ mbox {dep}（g）= p/q $，那么我们说依赖关系$ p/q $是可构建的。 2002年，费拉拉（Ferrara），古尔德（Gould）和萨普尔（Suffel）提出了一个开放的问题，这些问题是理性密度和依赖性是可构建的。在2016年，Kahl提供了显示所有理性密度和依赖性的结构。此外，他表明，即使$ g $仅限于二分图或平面图，所有理性密度都是可构造的。因此，他猜想即使$ g $仅限于两部分图（猜想1）或平面图（猜想2），也可以构造所有理性依赖。在本文中，通过组合和电网方法，首先，我们证明了所有合理依赖性都是通过两部分图构造的，这证实了Kahl的第一个猜想。其次，我们表明所有理性依赖性均可用于平面多编码，这证实了Kahl对Planar Multigraphs的第二个猜想。但是，对于（简单）平面图，我们通过证明任何平面图的依赖性大于$ \ frac {1} {3} $来反驳Kahl的第二个猜想。另一方面，我们构建了一个平面图系列，该系列显示了所有理性依赖$ p/q> \ frac {1} {2} $是通过平面图构造的。
Let $τ(G)$ and $τ_G(e)$ be the number of spanning trees of a connected graph $G$ and the number of spanning trees of $G$ containing edge $e$. The ratio $d_{G}(e)=τ_{G}(e)/τ(G)$ is called the spanning tree edge density of $e$, or simply density of $e$. The maximum density $\mbox{dep}(G)=\max\limits_{e\in E(G)}d_{G}(e)$ is called the spanning tree edge dependence of $G$, or simply dependence of $G$. Given a rational number $p/q\in (0,1)$, if there exists a graph $G$ and an edge $e\in E(G)$ such that $d_{G}(e)=p/q$, then we say the density $p/q$ is constructible. More specially, if there exists a graph $G$ such that $\mbox{dep}(G)=p/q$, then we say the dependence $p/q$ is constructible. In 2002, Ferrara, Gould, and Suffel raised the open problem of which rational densities and dependences are constructible. In 2016, Kahl provided constructions that show all rational densities and dependences are constructible. Moreover, He showed that all rational densities are constructible even if $G$ is restricted to bipartite graphs or planar graphs. He thus conjectured that all rational dependences are also constructible even if $G$ is restricted to bipartite graphs (Conjecture 1), or planar graphs (Conjecture 2). In this paper, by combinatorial and electric network approach, firstly, we show that all rational dependences are constructible via bipartite graphs, which confirms the first conjecture of Kahl. Secondly, we show that all rational dependences are constructible for planar multigraphs, which confirms Kahl's second conjecture for planar multigraphs. However, for (simple) planar graphs, we disprove the second conjecture of Kahl by showing that the dependence of any planar graph is larger than $\frac{1}{3}$. On the other hand, we construct a family of planar graphs that show all rational dependences $p/q>\frac{1}{2}$ are constructible via planar graphs.
