STRONG EMBEDDING OF HP-GRAPHS ON SURFACE WITH HIGHER GENUS

作     者：Erling WEI Yanpei LIU 

作者机构：Department of Mathematics Renmin University of China Beijing 100872 China. Department of Mathematics Northern Jiaotong University Beijing 100044 China. 

出 版 物：《Journal of Systems Science & Complexity》 (系统科学与复杂性学报（英文版）)

年 卷 期：2006年第19卷第3期

页      面：441-446页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：The research is supported by the National Natural Science Foundation of China under Grant No. 60733030 and Foundation of Renmin University of China 

主　　题：CDC embedding genus HP-graph surface. 

摘      要：In 1990, Bondy posed the small circuit double cover （SCDC） conjecture： Every 2-connected graph has a circuit double cover （CDC） with the number of circuits less than ｜v｜ （the order of the vertex set V）. The strong embedding conjecture states that every 2-connected graph has a strong embedding on some surface in which the boundary of each face is a circuit. In this paper, HP-graph is defined as the graph which has a strong embedding on the projective plane with one face of valence ｜V｜ and the other faces of valence 3. And it is proved that the HP-graph has a strong embedding with ｜V｜ - 1 or less faces on some surface, which confirms both the SCDC conjecture and the strong embedding conjecture.