Cycles through specified vertices |
| |
| Authors: | Béla Bollobás Graham Brightwell |
| |
| Institution: | (1) Department of Pure Mathematics and Mathematical Statistics, University of Cambridge 16, Mill Lane, CB2 1SB Cambridge, England;(2) Dept. of Stat. and Math. Sciences, London School of Economics and Political Science, Houghton Street, WC2A 2AE London, England |
| |
| Abstract: | Recently, various authors have obtained results about the existence of long cycles in graphs with a given minimum degreed. We extend these results to the case where only some of the vertices are known to have degree at leastd, and we want to find a cycle through as many of these vertices as possible. IfG is a graph onn vertices andW is a set ofw vertices of degree at leastd, we prove that there is a cycle through at least
vertices ofW. We also find the extremal graphs for this property.Research supported in part by NSF Grant DMS 8806097 |
| |
| Keywords: | 05 C 38 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
