On the number of vertices of positively curved planar graphs

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

For a connected simple graph embedded into a 2-sphere, we show that the number of vertices of the graph is less than or equal to 380 if the degree of each vertex is at least three, the combinatorial vertex curvature is positive everywhere, and the graph is different from prisms and antiprisms. This gives a new upper bound for the constant brought up by DeVos and Mohar in their paper from 2007. We also show that if a graph is embedded into a projective plane instead of a 2-sphere but satisfies the other properties listed above, then the number of vertices is at most 190.

Original languageEnglish
Pages (from-to)1300-1310
Number of pages11
JournalDiscrete Mathematics
Volume340
Issue number6
DOIs
StatePublished - 2017 Jun 1

Keywords

  • Combinatorial curvature
  • Discharging method
  • Planar graph

Fingerprint Dive into the research topics of 'On the number of vertices of positively curved planar graphs'. Together they form a unique fingerprint.

Cite this