On the maximum order of graphs embedded in surfaces
详细信息    查看全文
文摘
The maximum number of vertices in a graph of maximum degree Δ≥3 and fixed diameter k≥2 is upper bounded by (1+o(1))(Δ−1)k. If we restrict our graphs to certain classes, better upper bounds are known. For instance, for the class of trees there is an upper bound of (2+o(1))(Δ−1)⌊k/2⌋ for a fixed k. The main result of this paper is that graphs embedded in surfaces of bounded Euler genus g behave like trees, in the sense that, for large Δ, such graphs have orders bounded from above by
View the MathML source
where c is an absolute constant. This result represents a qualitative improvement over all previous results, even for planar graphs of odd diameter k. With respect to lower bounds, we construct graphs of Euler genus g, odd diameter k  , and order View the MathML source for some absolute constant c>0. Our results answer in the negative a question of Miller and Širáň (2005).

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700