Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Long path lemma concerning connectivity and independence number. | Long path lemma concerning connectivity and independence number Shinya Fujita Alexander Halperin Colton Magnant Submitted May 10 2010 Accepted Nov 26 2011 Published Jul 22 2011 Mathematics Subject Classification 05C35 Abstract We show that in a k-connected graph G of order n with a G a between any TAAir of cvisl R A TjAf II p idininơ fhpm wit II I Pl min II b n id -I- k ppex l to v jl 7s jl 7 7 x s s ex poex j o It 1-i g vv m . I n a I This implies that for any edge e G E G there is a cycle containing e of length pt mill J Ì1 - 1 n I Ị A TiNrorwor W0 rtnr roQiilf QC frJlrvnrQ frtr ex eas 444 44 I n a I or ẹọ v 34 vv ex z to Lur r js Lu exs vv s o-L any choice S of s k vertices in G there exists a tree T whose set of leaves is S with T min tn k-s f n-k kj a 1 Introduction In this work we present a tool which we believe will be useful in many applications. Much work has been devoted to finding long paths and cycles in graphs. In particular in 4 O West and Wu recently proved a conjecture by Fouquet and Jolivet 3 stated as follows. Theorem 1 4 Let k 2 and let G be a k-connected graph of order n with a G a. Then there is a cycle in G of length at least min n fc ra a-fc In various situations including this work it often becomes necessary to find a long path between a chosen pair of vertices. For this reason O West and Wu proved the following theorem which they used in their proof of the conjecture. Theorem 2 4 Let G be a k-connected graph for k 1. If H c G and u and v are distinct vertices in G then G contains a u v-path P such that V H c V P or a H - P a H - k - 1 . Department of Mathematics Gunma National College of Technology 580 Toriba Maebashi Gunma Japan 371-8530 Supported by JSPS Grant No 20740068 Department of Mathematics Lehigh University Bethlehem PA 18015 USA Department of Mathematical Sciences Georgia Southern University Statesboro GA 30460 USA THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P149 1 We also use this theorem and .
