论文标题
跨越树木包装和2个符号的边缘连接性
Spanning tree packing and 2-essential edge-connectivity
论文作者
论文摘要
如果$ g-x $具有两个至少$ r $ $边缘，则边缘（顶点）切割$ x $ $ g $是$ r $ - $ r $。图形$ g $是$ r $ - 本质上是$ k $ - edge连接（resp。$ k $ - 连接），如果它没有$ r $ - extental-Edge（sups。vertex）尺寸小于$ k $的剪切。如果$ r = 1 $，我们简单地称其为必不可少。 Recently, Lai and Li proved that every $m$-edge-connected essentially $h$-edge-connected graph contains $k$ edge-disjoint spanning trees, where $k,m,h$ are positive integers such that $k+1\le m\le 2k-1$ and $h\ge \frac{m^2}{m-k}-2$.在本文中，我们表明，每$ m $ - 连接和$ 2 $ - ESTERTY $ h $ - 边缘连接的图形不是$ k_5 $或多重的脂肪三角形，小于$ k $具有$ k $ k $ gedes-edge-edisech-disegint spanning树，其中$ k+k+k+1 \ le m \ le m \ le 2k-1 $ and $ \ le 2k-le 2k and $ h \ ge f（je） 2M+K-4+\ frac {K（2K-1）} {2M-2K-1}，＆m <k+\ \ \ \ \ \ \ \ \ \ \ \ \ \ sqrt {8K+1}} {4} {4}，\\ m+3K-4+\ frac {k^2} k+\ frac {1+ \ sqrt {8k+1}}} {4}。 \ end {case} $$扩展了Zhan的结果，我们还证明，每个3边缘连接基本上是5边连接的，并且$ 2 $ - 本质上是8边连接的图形都具有两个边缘 - 界线跨越树。作为一种应用，这为汉密尔顿连接线图提供了新的条件。 2012年，Kaiser和Vrána证明，至少6个最低度的每5个连接线图是汉密尔顿连接的。我们允许图形具有最低度5，并证明每5个相互连接的基本8连接线图是汉密尔顿连接的。
An edge (vertex) cut $X$ of $G$ is $r$-essential if $G-X$ has two components each of which has at least $r$ edges. A graph $G$ is $r$-essentially $k$-edge-connected (resp. $k$-connected) if it has no $r$-essential edge (resp. vertex) cuts of size less than $k$. If $r=1$, we simply call it essential. Recently, Lai and Li proved that every $m$-edge-connected essentially $h$-edge-connected graph contains $k$ edge-disjoint spanning trees, where $k,m,h$ are positive integers such that $k+1\le m\le 2k-1$ and $h\ge \frac{m^2}{m-k}-2$. In this paper, we show that every $m$-edge-connected and $2$-essentially $h$-edge-connected graph that is not a $K_5$ or a fat-triangle with multiplicity less than $k$ has $k$ edge-disjoint spanning trees, where $k+1\le m\le 2k-1$ and $$h\ge f(m,k)=\begin{cases} 2m+k-4+\frac{k(2k-1)}{2m-2k-1}, & m< k+\frac{1+\sqrt{8k+1}}{4}, \\ m+3k-4+\frac{k^2}{m-k}, & m\ge k+\frac{1+\sqrt{8k+1}}{4}. \end{cases}$$ Extending Zhan's result, we also prove that every 3-edge-connected essentially 5-edge-connected and $2$-essentially 8-edge-connected graph has two edge-disjoint spanning trees. As an application, this gives a new sufficient condition for Hamilton-connectedness of line graphs. In 2012, Kaiser and Vrána proved that every 5-connected line graph of minimum degree at least 6 is Hamilton-connected. We allow graphs to have minimum degree 5 and prove that every 5-connected essentially 8-connected line graph is Hamilton-connected.
