Weight of 3-Paths in Sparse Plane Graphs

  • V. A. Aksenov
  • O. V. Borodin
  • A. O. Ivanova
Keywords: planar graph, girth, 3-path, weight

Abstract

We prove precise upper bounds for the minimum weight of a path on three vertices in several natural classes of plane graphs with minimum degree 2 and girth $g$ from 5 to 7. In particular, we disprove a conjecture by S. Jendrol' and M. Maceková concerning the case $g=5$ and prove the tightness of their upper bound for $g=5$ when no vertex is adjacent to more than one vertex of degree 2. For $g\ge8$, the upper bound recently found by Jendrol' and Maceková is tight.

Published
2015-08-28
Article Number
P3.28