Author/Authors :
Borodin، نويسنده , , Oleg V. and Ivanova، نويسنده , , Anna O.، نويسنده ,
Abstract :
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.
ine the tightness of Borodin–Woodall’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 M 5 s.
Keywords :
Planar graph , Structural Property , Plane map , STAR , Weight