Geodesic
Longest Cycles in 3-Connected 3-Regular Graphs
Canadian journal of mathematics, Tome 32 (1980) no. 4, pp. 987-992

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

In this paper, we study the following question: How long a cycle must there be in a 3-connected 3-regular graph on n vertices? For planar graphs this question goes back to Tait [6], who conjectured that any planar 3-connected 3-regular graph is hamiltonian. Tutte [7] disproved this conjecture by finding a counterexample on 46 vertices. Using Tutte's example, Grunbaum and Motzkin [3] constructed an infinite family of 3-connected 3-regular planar graphs such that the length of a longest cycle in each member of the family is at most nc, where c = 1 – 2–17 and n is the number of vertices. The exponent c was subsequently reduced by Walther [8, 9] and by Grùnbaum and Walther [4]. 
Bondy, J. A.; Simonovits, M. Longest Cycles in 3-Connected 3-Regular Graphs. Canadian journal of mathematics, Tome 32 (1980) no. 4, pp. 987-992. doi: 10.4153/CJM-1980-076-2
@article{10_4153_CJM_1980_076_2,
     author = {Bondy, J. A. and Simonovits, M.},
     title = {Longest {Cycles} in {3-Connected} {3-Regular} {Graphs}},
     journal = {Canadian journal of mathematics},
     pages = {987--992},
     year = {1980},
     volume = {32},
     number = {4},
     doi = {10.4153/CJM-1980-076-2},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1980-076-2/}
}
TY  - JOUR
AU  - Bondy, J. A.
AU  - Simonovits, M.
TI  - Longest Cycles in 3-Connected 3-Regular Graphs
JO  - Canadian journal of mathematics
PY  - 1980
SP  - 987
EP  - 992
VL  - 32
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1980-076-2/
DO  - 10.4153/CJM-1980-076-2
ID  - 10_4153_CJM_1980_076_2
ER  - 
%0 Journal Article
%A Bondy, J. A.
%A Simonovits, M.
%T Longest Cycles in 3-Connected 3-Regular Graphs
%J Canadian journal of mathematics
%D 1980
%P 987-992
%V 32
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1980-076-2/
%R 10.4153/CJM-1980-076-2
%F 10_4153_CJM_1980_076_2

[1] 1. Barnette, D., Trees in polyhedral graphs, Can. J. Math. 18 (1966), 731–736. Google Scholar

[2] 2. Bondy, J. A. and Entringer, R. C., Longest cycles in 2-connected graphs with prescribed maximum degree, Can. J. Math., to appear. Google Scholar | DOI

[3] 3. Grünbaum, B. and Motzkin, T. S., Longest simple paths in polyhedral graphs, J. London Math. Soc. 37 (1962), 152–160. Google Scholar

[4] 4. Grünbaum, B. and Walther, H., Shortness exponents of families of graphs, J. Combinatorial Theory Ser. A. 14 (1973), 364–385. Google Scholar

[5] 5. Lang, R. and Walther, H., Über längste Kreise in reguldren Graphen, Beitrage zur Graphentheorie (Kolloquium, Manebach, 1967). Teubner, Leipzig (1968), 91–98. Google Scholar

[6] 6. Tait, P. G., Remarks on colouring of maps, Proc. Royal Soc. Edinburgh Ser. A. 10 (1880), 729. Google Scholar

[7] 7. Tutte, W. T., On hamiltoman circuits, J. London Math. Soc. 21 (1946), 98–101. Google Scholar

[8] 8. Walther, H., Über die Anzahl der Knotenpunkte eines längsten Kreises in planaren, kubischen dreifach knotenzusammenhdngenden Graphen, Studia Sci. Math. Hungar. 2 (1967), 391–398. Google Scholar

[9] 9. Walther, H., Über Extremalkreise in reguldren Landkarten, Wiss. Z. Techn. Hochsch. Ilmenau 15 (1969), 139–142. Google Scholar

Cité par Sources :