Minimal vertex degree sum of a 3-path in plane maps. (English) Zbl 0906.05017

Borodin, O. V.

Discuss. Math., Graph Theory 17, No. 2, 279-284 (1997).

A plane map is normal if every face and every vertex of the map is incident with at least three edges. Let \(w_k\) be the minimum degree sum, in a graph \(G\), of the vertices on a path of order \(k\) in \(G\). The author shows that, for normal plane maps: (1) If \(w_2= 6\), then \(w_3\) can be arbitrarily large. (2) If \(w_2> 6\), then either \(w_3\leq 18\) or there is a vertex of degree at most 15 adjacent to two vertices of degree 3. (3) If \(w_2>7\), then \(w_3\leq 17\).

Reviewer: A.T.White (Kalamazoo)

MSC:

05C10	Planar graphs; geometric and topological aspects of graph theory
05C38	Paths and cycles

Keywords:

plane map; minimum degree sum; path