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 s...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.展开更多
基金The research is supported by the National Natural Science Foundation of China under Grant No. 60733030 and Foundation of Renmin University of China.
文摘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.
