Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648880 | Discrete Mathematics | 2010 | 7 Pages |
Abstract
A graph GG is said to have property P(2,k)P(2,k) if given any k+2k+2 distinct vertices a,b,v1,…,vka,b,v1,…,vk, there is a path PP in GG joining aa and bb and passing through all of v1,…,vkv1,…,vk. A graph GG is said to have property C(k)C(k) if given any kk distinct vertices v1,…,vkv1,…,vk, there is a cycle CC in GG containing all of v1,…,vkv1,…,vk. It is shown that if a 4-connected graph GG is embedded in an orientable surface ΣΣ (other than the sphere) of Euler genus eg(G,Σ)eg(G,Σ), with sufficiently large representativity (as a function of both eg(G,Σ)eg(G,Σ) and kk), then GG possesses both properties P(2,k)P(2,k) and C(k)C(k).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ken-ichi Kawarabayashi, Michael D. Plummer,