4-connected triangulations and 4-orderedness

详细信息    查看全文

• 作者：Raiji Mukae ; Kenta Ozeki
• 关键词：Triangulations of a surface ; 4-ordered
• 刊名：Discrete Mathematics
• 出版年：2010
• 出版时间：28 September 2010
• 年：2010
• 卷：310
• 期：17-18
• 页码：2271-2272
• 全文大小：214 K

文摘

For a positive integer k≥4, a graph G is called k-ordered, if for any ordered set of k distinct vertices of G, G has a cycle that contains all the vertices in the designated order. Goddard (2002) [3] showed that every 4-connected triangulation of the plane is 4-ordered. In this paper, we improve this result; every 4-connected triangulation of any surface is 4-ordered. Our proof is much shorter than the proof by Goddard.