scientific article; zbMATH DE number 1002648

Publication date 22 April 1997

geodesics geodetic subgraph locally finite graphs planar graphs planarity shortest paths vertex-transitive graph

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Paths and cycles (05C38)

Review text

We prove the following result (the geodetic subgraph is just the union of all geodesics): Theorem 1.3. Let \(X\) be a simple, locally finite, 1-ended, vertex-transitive graph with a planar geodetic subgraph. If every geodesics bisects \(X\), then \(X\) is planar. The requirement of planarity for the geodetic subgraph can perhaps be dropped so that the original conjecture is proven---namely if the following conjecture holds: Conjecture 1.4 (Bonnington, Imrich, Seifter). Let \(X\) be a simple, locally finite, 1-ended, vertex-transitive graph which is bisected by every geodesic. Then the geodetic subgraph of \(X\) is planar. This conjecture is claimed as Theorem 6.1 in [\((*)\) \textit{C. P. Bonnington}, \textit{W. Imrich} and \textit{N. Seifter}, J. Comb. Theory, Ser. B 67, No. 1, 12-33, Art. No. 0031 (1996; Zbl 0856.05032)], where a proof of the conjecture ``a simple, locally finite, 1-ended, vertex-transitive graph \(X\) is planar if and only if every geodesic bisects \(X\) by Bonnington, Imrich and Watkins, using the planarity of the geodetic subgraph, is presented for the case that \(X\) has polynomial growth. But unfortunately, the proof of Theorem 6.1 has turned out to be wrong, and a correct proof could not be found so far. At least, it seems possible to confirm Conjecture 1.4 if \(X\) has polynomial growth. After introducing some terminology (Chapter 2), we present a few basic facts about geodesics in Chapter 3. Then, in Chapter 4, we turn towards geodesics in planar graphs and deal with Conjecture 3.3 of \((*)\): Conjecture 1.5 (Bonnington, Imrich, Seifter). Every edge of a 1-ended, vertex-transitive, planar graph belongs to a geodesic. In \((*)\) (Theorem 3.2) it is shown that this conjecture holds if \(X\) is bipartite. Bonnington, Imrich and Seifter also mention that Thomassen proved that every edge in an infinite, vertex-transitive, cubic graph belongs to a geodesic. Niemeyer proved the conjecture in the case that all faces and vertices have degree at least four without assuming transitivity (Theorem 4.34 of [\((**)\) \textit{P. Niemeyer}, J. Graph Theory 22, No. 4, 357-365 (1996; Zbl 0864.05042 below)]). We present two results, which cover all the partial results mentioned here except that of Thomassen (this will be proven as Theorem 5.30) and confirm a considerably stronger version of Conjecture 1.5. For this, we will have recourse to a theorem about tilings of the plane. The structure of the geodetic subgraph \(Y\) of a graph \(X\) is subject of our considerations in Chapter 5. Especially for an almost-transitive \(X\), we work out a set of conditions which suffice to prove that \(Y\) is connected, that every geodesic in \(Y\) is also a geodesic in \(X\), that \(Y\) has the same end structure as \(X\), or that \(X\) and \(Y\) are equal. We also present a result which might help to confirm Conjecture 1.4. Finally, we examine the relation between the d-fiber structure of \(Y\) and that of \(X\). We then combine our results about geodesics in planar graphs and those about the geodetic subgraph to a proof of Theorem 1.3 in Chapter 6. In Chapter 7, for a wide class of planar graphs, an iterative algorithm for finding shortest paths, starting from any given path, is presented. It has the property that in each step only information about vertices and faces visited by the path found so far is needed. As by-product, a classification of unique shortest paths comes up, generalizing a result of Niemeyer (Corollary 4.31 in \((**)\)).

Recommendations

Cited in

(7)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3130188)