A Census of Hamiltonian Polygons

W. T. Tutte

doi:10.4153/CJM-1962-032-x

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper we deal with trivalent planar maps in which the boundary of each country (or “face“) is a simple closed curve. One vertex is distinguished as the root and its three incident edges are distinguished as the first, second, and third major edges. We determine the average number of Hamiltonian polygons, passing through the first and second major edges, in such a “rooted map” of 2n vertices. Next we consider the corresponding problem for 3-connected rooted maps. In this case we obtain a functional equation from which the average can be computed for small values of n.

Crossref Citations

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Tutte, W. T. 1963. A Census of Planar Maps. Canadian Journal of Mathematics, Vol. 15, Issue. , p. 249.

Mullin, R.C. 1967. On the average activity of a spanning tree of a rooted map. Journal of Combinatorial Theory, Vol. 3, Issue. 2, p. 103.

Tutte, W. T. 1969. On the Enumeration of Four-Colored Maps. SIAM Journal on Applied Mathematics, Vol. 17, Issue. 2, p. 454.

Tutte, W. T. 1973. Chromatic Sums for Rooted Planar Triangulations, IV: The Case λ = ∞. Canadian Journal of Mathematics, Vol. 25, Issue. 5, p. 929.

TUTTE, W.T. 1973. A Survey of Combinatorial Theory. p. 437.

Richmond, L.B 1976. On Hamiltonian polygons. Journal of Combinatorial Theory, Series B, Vol. 21, Issue. 1, p. 81.

Tutte, W. T. 1978. Theory and Applications of Graphs. Vol. 642, Issue. , p. 590.

Rathie, Pushpa N. 1980. Combinatorial Mathematics, Optimal Designs and Their Applications. Vol. 6, Issue. , p. 281.

Wormald, Nicholas C. 1985. Enumeration of cyclically 4‐connected cubic graphs. Journal of Graph Theory, Vol. 9, Issue. 4, p. 563.

Gouyou-Beauchamps, Dominique 1986. Combinatoire énumérative. Vol. 1234, Issue. , p. 112.

Cori, Robert Dulucq, Serge and Viennot, Gérard 1986. Shuffle of parenthesis systems and baxter permutations. Journal of Combinatorial Theory, Series A, Vol. 43, Issue. 1, p. 1.

Bender, Edward A and Richmond, L.Bruce 1986. A survey of the asymptotic behaviour of maps. Journal of Combinatorial Theory, Series B, Vol. 40, Issue. 3, p. 297.

Arques, Didier 1986. Dénombrements de chemins dans $\mathbb {R}^2$ soumis à contraintes. RAIRO - Theoretical Informatics and Applications, Vol. 20, Issue. 4, p. 473.

Gouyou-Beauchamps, Dominique 1989. Standard Young Tableaux of Height 4 and 5. European Journal of Combinatorics, Vol. 10, Issue. 1, p. 69.

Boots, B. N. and Royle, Gordon F. 1991. A Conjecture on the Maximum Value of the Principal Eigenvalue of a Planar Graph. Geographical Analysis, Vol. 23, Issue. 3, p. 276.

Guy, Richard 1997. The Encyclopedia of Integer Sequences, by N. J. A. Sloane and Simon Plouffe. The American Mathematical Monthly, Vol. 104, Issue. 2, p. 180.

Ball, John and Welsh, Dominic 1998. Graph Theory as I Have Known It.

He, Xin Kao, Ming-Yang and Lu, Hsueh-I 1999. Algorithms - ESA’ 99. Vol. 1643, Issue. , p. 540.

Ren, Han and Liu, Yanpei 2001. 4-Regular Maps on the Klein Bottle. Journal of Combinatorial Theory, Series B, Vol. 82, Issue. 1, p. 118.

Ren, Han and Liu, Yanpei 2001. Enumerating near-4-regular maps on the sphere and the torus. Discrete Applied Mathematics, Vol. 110, Issue. 2-3, p. 273.

Download full list

Article contents

A Census of Hamiltonian Polygons

Extract

Save article to Kindle

Save article to Dropbox

Save article to Google Drive

Reply to: Submit a response

Your details

You have entered the maximum number of contributors

Conflicting interests