×

On 3-simplicial vertices in planar graphs. (English) Zbl 1068.05018

Authors’ abstract: A vertex \(v\) in a graph \(G=(V,E)\) is \(k\)-simplicial if the neighborhood \(N(v)\) of \(v\) can be vertex-covered by \(k\) or fewer complete graphs. The main result of the paper states that a planar graph of order at least four has at least four 3-simplicial vertices of degree at most five. This result is a strengthening of the classical corollary of Euler’s formula that a planar graph of order at least four contains at least four vertices of degree at most five.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI