Journal
INFORMATION PROCESSING LETTERS
Volume 136, Issue -, Pages 83-89Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ipl.2018.04.008
Keywords
Outerplanar graph; Outer-l-planar graph; Light subgraph; Combinatorial problems
Categories
Funding
- Natural Science Basic Research Plan in Shaanxi Province of China [2017JM1010, 2017JM1030, 2017JM1031]
- Fundamental Research Funds for the Central Universities [JB170706]
- National Natural Science Foundation of China [11301410, 11626181, 11701440, 61672025]
Ask authors/readers for more resources
It is proved that (1) every maximal outer-l-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. (C) 2018 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available