Paths of low weight in planar graphs
Igor Fabrici, Jochen Harant, Stanislav Jendrol′ · Discussiones Mathematicae Graph Theory · 2008
The existence of subgraphs of low degree sum of their vertices in planar graphs is investigated. Let K1;3 , a subgraph of a graph G, be an (x; a; b; c)-star, a star with a central vertex of degree x and three leaves of degrees a, b and c in G. The main results of the paper are: 1. Every planar graph G of minimum degree at least 3 contains an (x; a; b; c)-star with a b c and (i) x = 3, a 10, or (ii) x = 4, a = 4, 4 b 10, or (iii) x = 4, a = 5, 5 b 9, or (iv) x = 4, 6 a 7, 6 b 8, or (v) x = 5, 4 a 5, 5 b 6 and 5 c 7, or (vi) x = 5 and a = b = c = 6.