Weight of 3-Paths in Sparse Plane Graphs

V. A. Aksenov, O. V. Borodin, A. O. Ivanova

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.


Keywords


planar graph, girth, 3-path, weight

Full Text: PDF