DIMACS TR: 2001-32
On 3-Simplicial Vertices in Planar Graphs
Authors: Endre Boros, Robert E. Jamison, Renu Laskar and Henry Martyn Mulder
ABSTRACT
A vertex $v$ in a graph $G = (V,E)$ is {\em $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.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-32.ps.gz
DIMACS Home Page