Describing 4-stars at 5-vertices in normal plane maps with minimum degree 5

作者：Borodin Oleg V; Ivanova Anna O^*

来源：Discrete Mathematics, 2013, 313(17): 1710-1714.

DOI：10.1016/j.disc.2013.04.025

• Planar graph
• Plane map
• Structural property
• Star
• Weight

Lebesgue (1940) [13] proved that each plane normal map M-5 with minimum degree 5 has a 5-vertex such that the degree-sum (the weight) of its every four neighbors is at most 26. In other words, every M-5 has a 4-star of weight at most 31 centered at a 5-vertex. Borodin-Woodall (1998) [3] improved this 31 to the tight bound 30. %26lt;br%26gt;We refine the tightness of Borodin-Woodall%26apos;s bound 30 by presenting six M(5)s such that (1) every 4-star at a 5-vertex in them has weight at least 30 and (2) for each of the six possible types (5, 5, 5, 10), (5, 5, 6, 9), (5, 5, 7, 8), (5, 6, 6, 8), (5, 6, 7, 7), and (6, 6, 6, 7) of 4-stars with weight 30, the 4-stars of this type at 5-vertices appear in precisely one of these six M5S.

• 出版日期2013-9-6