Long Path Lemma concerning Connectivity and Independence Number
Long Path Lemma concerning Connectivity and Independence Number
复制标题
DOI：
10.37236/636
复制
发表时间：
2011-07
期刊：
影响因子：
--
通讯作者：
S. Fujita;Alexander Halperin;Colton Magnant
中科院分区：
文献类型：
--
作者：
S. Fujita;Alexander Halperin;Colton Magnant
证明了：在阶为$n$且$\α(G)=\α$的$k$-连通图$G中，任意两个顶点之间存在一条路径$P，将它们与$$|P|\geq\min\Left\n，FRAC{(k-1)(n-k)}{\α}+k\Right\}连接在一起。$$这意味着，对于E(G)$中的任何边$e，都存在一个包含至少$$\min\Left\{n，进一步地，我们将我们的结果推广如下：对于$G$中任一选择$S的$S\leq k$顶点，存在一棵树$T$，它的叶集为$S$，其中$|T|\geq\min\lec{(k-S+1)(n-k)}{\α}+k\右\}
We show that, in a $k$-connected graph $G$ of order $n$ with $\alpha(G) = \alpha$, between any pair of vertices, there exists a path $P$ joining them with $$|P| \geq \min \left\{ n, \frac{(k - 1)(n - k)}{\alpha} + k \right\}.$$ This implies that, for any edge $e \in E(G)$, there is a cycle containing $e$ of length at least $$\min \left\{ n, \frac{(k - 1)(n - k)}{\alpha} + k \right\}.$$ Moreover, we generalize our result as follows: for any choice $S$ of $s \leq k$ vertices in $G$, there exists a tree $T$ whose set of leaves is $S$ with $$|T| \geq \min \left\{ n, \frac{(k - s + 1)(n - k)}{\alpha} + k \right\}.$$