Long path lemma concerning connectivity and independence number
type: Item
instance of: scholarly article
title: Long path lemma concerning connectivity and independence number
zbMATH Open document ID: 1226.05137
author: Shinya Fujita
author: Alexander Halperin
author: Colton Magnant
published in: The Electronic Journal of Combinatorics
publication date: 2011-07-29T00:00:00Z
full work available at URL: https://eudml.org/doc/232906
full work available at URL: v18i1p149.html
review text: Summary: 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,{(k-1)(n- k)\over \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,{(k- 1)(n- k)\over\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,{(k-s+1)(n-k)\over\alpha}+ k\right\}\).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 5933972
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5933972