论文标题
完全独立的跨越线图中的树
Completely Independent Spanning Trees in Line Graphs
论文作者
论文摘要
完全独立的跨越图$ g $的树是$ g $的树，因此，对于$ g $的任何两个不同的顶点，它们在跨越树中的路径是成对的边缘 - 二十一个和内部顶点disjoint。在本文中，我们在$ l（g）$中的最大独立跨越树的最大范围内提出了一个紧密的下限，其中$ l（g）$表示图$ g $的线图。基于与$ k $完全独立的跨越树的新图表的新特征，我们还表明，对于任何完整的图形$ k_n $ of cold $ n \ geq 4 $，都有$ \ lfloor \ lfloor \ frac {n+1} {2} {2} \ rfloor $完全独立的树在$ l（k_n）$ $ \ lfloor \ lfloor \ lfloor \ lflo \ lflor \ lflor \ lflo \ lflo \ lflor \ \rfloor$ is optimal, such that $\lfloor \frac{n+1}{2} \rfloor$ completely independent spanning trees still exist in the graph obtained from $L(K_n)$ by deleting any vertex (respectively, any induced path of order at most $\frac{n}{2}$) for $n = 4$ or odd $n \geq 5$ （分别，甚至$ n \ geq 6 $）。关于连接性和完全独立的树木的数量，我们还显示以下内容，其中$δ（g）$表示$ g $的最低度。 $ \ $ $ \ bullet $每个$ 2K $连接的线图$ l（g）$具有$ k $完全独立的跨越树，如果$ g $不是超级边缘连接或$δ（g）\ geq 2k $。 $ \ $ $ \ $ \ bullet $每个$（4K-2）$ - 连接的线图$ l（g）$具有$ k $完全独立的跨越树，如果$ g $是常规的。 $ \ $ $ \ $ \ bullet $ every $（k^2+2k-1）$ - 连接的线图$ l（g）$，$δ（g）\ geq k+1 $具有$ k $完全独立的跨越树。
Completely independent spanning trees in a graph $G$ are spanning trees of $G$ such that for any two distinct vertices of $G$, the paths between them in the spanning trees are pairwise edge-disjoint and internally vertex-disjoint. In this paper, we present a tight lower bound on the maximum number of completely independent spanning trees in $L(G)$, where $L(G)$ denotes the line graph of a graph $G$. Based on a new characterization of a graph with $k$ completely independent spanning trees, we also show that for any complete graph $K_n$ of order $n \geq 4$, there are $\lfloor \frac{n+1}{2} \rfloor$ completely independent spanning trees in $L(K_n)$ where the number $\lfloor \frac{n+1}{2} \rfloor$ is optimal, such that $\lfloor \frac{n+1}{2} \rfloor$ completely independent spanning trees still exist in the graph obtained from $L(K_n)$ by deleting any vertex (respectively, any induced path of order at most $\frac{n}{2}$) for $n = 4$ or odd $n \geq 5$ (respectively, even $n \geq 6$). Concerning the connectivity and the number of completely independent spanning trees, we moreover show the following, where $δ(G)$ denotes the minimum degree of $G$. $\ $ $\bullet$ Every $2k$-connected line graph $L(G)$ has $k$ completely independent spanning trees if $G$ is not super edge-connected or $δ(G) \geq 2k$. $\ $ $\bullet$ Every $(4k-2)$-connected line graph $L(G)$ has $k$ completely independent spanning trees if $G$ is regular. $\ $ $\bullet$ Every $(k^2+2k-1)$-connected line graph $L(G)$ with $δ(G) \geq k+1$ has $k$ completely independent spanning trees.
