Article ID Journal Published Year Pages File Type
6874168 Information Processing Letters 2018 11 Pages PDF
Abstract
It is proved that (1) every maximal outer-1-planar graph of order at least k contains a path on k-vertices with all vertices of degree at most 2k+1 (being sharp for k≤3), and a path on k-vertices with degree sum at most 5k−1, and further, (2) every maximal outer-1-planar graph contains an edge xy with d(x)+d(y)≤7, and every outer-1-planar graph with minimum degree at least 2 contains an edge xy with d(x)+d(y)≤9. Here the bounds 7 and 9 are sharp.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,