Long path lemma concerning connectivity and independence number

Shinya Fujita ; Alexander Halperin ; Colton Magnant

The electronic journal of combinatorics, Tome 18 (2011) no. 1

Résumé

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

Détail

DOI : 10.37236/636

Classification : 05C35, 05C40, 05C69