Title of article
Describing 4-stars at 5-vertices in normal plane maps with minimum degree 5
Author/Authors
Borodin، نويسنده , , Oleg V. and Ivanova، نويسنده , , Anna O.، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2013
Pages
5
From page
1710
To page
1714
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
Journal title
Discrete Mathematics
Serial Year
2013
Journal title
Discrete Mathematics
Record number
1600387
Link To Document