×

Note on an existence of small degree vertices with at most one big degree neighbour in planar graphs. (English) Zbl 1150.05321

The local structure of planar graphs is investigated. Let the edge weight \(w(e)\) of an edge \(e=uv \in E(G)\) be defined as \(w(e) = {\operatorname {deg}}(u)+{\operatorname {deg}}(v)\). It is proved that each planar graph of minimum degree 3 and minimum edge weight at least 9 contains a vertex of degree \(d\), \(d \in \{3,4,5\}\), which is adjacent with at least \(d - 1\) vertices of degree at most 20. The planar complete bipartite graphs \(K_{1,r}\) and \(K_{2,r}\), \(r \geq 3\) show that the requirement on minimum degree is necessary. An example, the kleetope of an icosahedron, where each vertex of degree 3 is adjacent to vertices of degree 20, is presented to show that the bound 20 is the best possible. In the proof a nontrivial recharging method is applied.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite