Separating double rays in locally finite planar graphs

C. Paul Bonnington, Wilfried Imrich, Mark E. Watkins

Research output: Contribution to journalArticleResearchpeer-review

8 Citations (Scopus)

Abstract

The main aim of this paper is to characterize infinite, locally finite, planar, 1-ended graphs by means of path separation properties. Let Γ be an infinite graph, let Π be a double ray in Γ, and let d and dΠ denote the distance functions in Γ and in Π, respectively. One calls Π a quasi-axis if lim inf d(x, y)/dΠ(x, y) > 0, where x and y are vertices of Π and dΠ(x, y) → ∞. An infinite, locally finite, almost 4-connected, almost-transitive, 1-ended graph is shown to be planar if and only if the complement of every quasi-axis has exactly two infinite components. Let Γ be locally finite, planar, 3-connected, almost-transitive, and 1-ended. It is shown that no proper planar embedding of Γ has an infinite face and hence its covalences are bounded. If Γ has bounded covalences and if Π is any double ray in Γ, it is shown that Γ - Π has at most two infinite components, at most one on each side of Π. If, moreover, Π is a quasi-axis, then Γ - Π is shown to have exactly two infinite components. With the aid of a result of Thomassen (1992), the above-stated characterization of infinite, locally finite, planar, 1-ended graphs is then obtained.

Original languageEnglish
Pages (from-to)61-72
Number of pages12
JournalDiscrete Mathematics
Volume145
Issue number1-3
DOIs
Publication statusPublished - 13 Oct 1995
Externally publishedYes

Cite this