×

zbMATH — the first resource for mathematics

On paths in planar graphs. (English) Zbl 0880.05059
Let \(G\) be a 2-connected plane graph and let \(X_G\) be the circuit bounding the infinite face. This paper generalizes the following result by C. Thomassen [J. Graph Theory 7, 169-176 (1983; Zbl 0515.05040)], which in turn was an improvement of an earlier theorem by W. T. Tutte [Trans. Am. Math. Soc. 82, 99-116 (1956; Zbl 0070.18403)]. Let \(u\), \(v\) be two vertices and \(e\) be an edge of \(G\). If \(u\neq v\) and both \(u\) and \(e\) belong to \(X_G\), then \(G\) has a Tutte path from \(u\) to \(v\) containing \(e\). (Tutte paths are a generalization of Hamilton paths, see the paper for the definition.) The main result of this article removes the restriction on the location of \(u\), as follows. Let \(u\), \(v\) be two vertices and \(e\) be an edge of \(G\). If \(u\neq v\) and \(e\) belong to \(X_G\), then \(G\) has a Tutte path from \(u\) to \(v\) containing \(e\). Two corollaries follow. (i) Let \(G\) be 4-connected, \(u\), \(v\) be vertices and \(e\neq uv\) be an edge of \(G\). Then \(G\) has a Hamiltonian path from \(u\) to \(v\) through \(e\). (ii) Let \(G\) be 4-connected. Then \(G\) has a Hamiltonian cycle though any two of its edges.

MSC:
05C38 Paths and cycles
05C10 Planar graphs; geometric and topological aspects of graph theory
05C45 Eulerian and Hamiltonian graphs
PDF BibTeX XML Cite
Full Text: DOI