Skip to main content
Article
Long Path Lemma Concerning Connectivity and Independence Number
The Electronic Journal of Combinatorics
  • Shinya Fujita, Maebashi Institute of Technology
  • Alexander Halperin, Lehigh University
  • Colton Magnant, Georgia Southern University
Document Type
Article
Publication Date
1-1-2011
Disciplines
Abstract

We show that, in a k-connected graph G of order n with α(G)=α, between any pair of vertices, there exists a path P joining them with

|P|≥min{n,(k−1)(n−k)/α +k}.

This implies that, for any edge e∈E(G), there is a cycle containing e of length at least

min{n,(k−1)(n−k)/α +k}.

Moreover, we generalize our result as follows: for any choice S of s≤k vertices in G, there exists a tree T whose set of leaves is S with

|T|≥min{n,(k−s+1)(n−k)/α +k}.

Comments

Copyright of the article remains with the author. Article obtained from the Electronic Journal of Combinatorics.

Citation Information
Shinya Fujita, Alexander Halperin and Colton Magnant. "Long Path Lemma Concerning Connectivity and Independence Number" The Electronic Journal of Combinatorics Vol. 18 Iss. 1 (2011)
Available at: http://works.bepress.com/colton_magnant/32/