Long Path Lemma concerning Connectivity and Independence Number

  • Shinya Fujita
  • Alexander Halperin
  • Colton Magnant

Abstract

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\}.$$

Published
2011-07-22
Article Number
P149