Geodesic
On Cycles and Connectivity in Planar Graphs
Canadian mathematical bulletin, Tome 16 (1973) no. 2, pp. 283-288

Voir la notice de l'article provenant de la source Cambridge University Press

Let G be a graph and ζ(G) be the greatest integer n such that every set of n points in G lies on a cycle [8]. It is clear that ζ(G)≥2 for 2-connected planar graphs. Moreover, it is easy to construct arbitrarily large 2-connected planar graphs for which ζ=2. On the other hand, by a well-known theorem of Tutte [5], [6], if G is planar and 4-connected, it has a Hamiltonian cycle, i.e., ζ(G)=|V(G)| for all 4-connected (and hence for all 5-connected) planar graphs. 
On Cycles and Connectivity in Planar Graphs. Canadian mathematical bulletin, Tome 16 (1973) no. 2, pp. 283-288. doi: 10.4153/CMB-1973-047-4
@misc{10_4153_CMB_1973_047_4,
     title = {On {Cycles} and {Connectivity} in {Planar} {Graphs}},
     journal = {Canadian mathematical bulletin},
     pages = {283--288},
     year = {1973},
     volume = {16},
     number = {2},
     doi = {10.4153/CMB-1973-047-4},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-1973-047-4/}
}
TY  - JOUR
TI  - On Cycles and Connectivity in Planar Graphs
JO  - Canadian mathematical bulletin
PY  - 1973
SP  - 283
EP  - 288
VL  - 16
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-1973-047-4/
DO  - 10.4153/CMB-1973-047-4
ID  - 10_4153_CMB_1973_047_4
ER  - 
%0 Journal Article
%T On Cycles and Connectivity in Planar Graphs
%J Canadian mathematical bulletin
%D 1973
%P 283-288
%V 16
%N 2
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-1973-047-4/
%R 10.4153/CMB-1973-047-4
%F 10_4153_CMB_1973_047_4

[1] 1. Barnette, D. and Jucovič, E., Hamiltonian circuits on 3-polytopes, J. Combinatorial Theory 9 (1970), 54–59. Google Scholar

[2] 2. Dirac, G., Généralisations du théorème de Menger, C. R. Acad. Sci. Paris, 250 (1960), 4252- 4253. Google Scholar

[3] 3. Dirac, G., In abstrakten Graphen vorhandene vollstandige 4-Graphen und ihre unterteilungen, Math. Nachr., 22 (1960), 61–85. Google Scholar

[4] 4. Harary, F., Graph theory, Addison-Wesley, Reading, Mass., 1969. Google Scholar

[5] 5. Ore, O., The four-color problem, Academic Press, New York, (1967), 68–74. Google Scholar

[6] 6. Tutte, W. T., A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956), 99–116. Google Scholar

[7] 7. Watkins, M. E., On the existence of certain disjoint arcs in graphs, Duke Math. J., 35 (1968), 231–246. Google Scholar

[8] 8. Watkins, M. E. and Mesner, D. M., Cycles and connectivity in graphs, Canad. J. Math., 19 (1967), 1319–1328. Google Scholar

Cité par Sources :