Nonseparating Cycles Avoiding Specific Vertices |
| |
Authors: | Yanmei Hong Liying Kang Xingxing Yu |
| |
Affiliation: | 1. COLLEGE OF MATHEMATICS AND COMPUTER SCIENCE, FUZHOU UNIVERSITY, FUJIAN, CHINA;2. DEPARTMENT OF MATHEMATICS, SHANGHAI UNIVERSITY, SHANGHAI, CHINA;3. SCHOOL OF MATHEMATICS, GEORGIA INSTITUTE OF TECHNOLOGY, ATLANTA, GA |
| |
Abstract: | Thomassen proved that every ‐connected graph G contains an induced cycle C such that is k‐connected, establishing a conjecture of Lovász. In general, one could ask the following question: For any positive integers , does there exist a smallest positive integer such that for any ‐connected graph G, any with , and any , there is an induced cycle C in such that and is l‐connected? The case when is a well‐known conjecture of Lovász that is still open for . In this article, we prove and . We also consider a weaker version: For any positive integers , is there a smallest positive integer such that for every ‐connected graph G and any with , there is an induced cycle C in such that is l‐connected? The case when was studied by Thomassen. We prove and . |
| |
Keywords: | connectivity nonseparating cycle k‐contractible edge |
|
|