| Maximum Genus of Strong Embeddings |
| |
| 作者姓名： | Er-lingWei Yan-peiLiu HanRen |
| |
| 作者单位： | [1]DepartmentofMathematics,RenmingUniversityofChina,Beijing100872,China [2]DepartmentofMathematics,NorthernJiaotongUniversity,Beijing100044,China [3]Departmentofmathematics,EastChinaNormalUniversity,Shanghai200062,China |
| |
| 基金项目： | the National Natural Sciences Foundation of China (No.10271048). |
| |
| 摘 要： | The strong embedding conjecture states that any 2-connected graph has a strong embedding on some surface. It implies the circuit double cover conjecture: Any 2-connected graph has a circuit double cover.Conversely, it is not true. But for a 3-regular graph, the two conjectures are equivalent. In this paper, a characterization of graphs having a strong embedding with exactly 3 faces, which is the strong embedding of maximum genus, is given. In addition, some graphs with the property are provided. More generally, an upper bound of the maximum genus of strong embeddings of a graph is presented too. Lastly, it is shown that the interpolation theorem is true to planar Halin graph.
|
| 关 键 词： | 强嵌入 极大亏格 Halin图 回路双覆盖 连通图 三次图 平面图 |
| 收稿时间： | 25 April 2001 |
Maximum Genus of Strong Embeddings |
| |
| Er-lingWei Yan-peiLiu HanRen.Maximum Genus of Strong Embeddings[J].Acta Mathematicae Applicatae Sinica,2003,19(3):437-446. |
| |
| Authors: | Er-ling Wei Yan-pei Liu Han Ren |
| |
| Institution: | (1) Department of Mathematics, Renming University of China, Beijing, 100872, China;(2) Department of Mathematics, Northern Jiaotong University, Beijing, 100044, China;(3) Department of mathematics, East China Normal University, Shanghai, 200062, China |
| |
| Abstract: | The strong embedding conjecture states that any 2-connected graph has a strong embedding on some surface. It implies the circuit double cover conjecture: Any 2-connected graph has a circuit double cover. Conversely, it is not true. But for a 3-regular graph, the two conjectures are equivalent. In this paper, a characterization of graphs having a strong embedding with exactly 3 faces, which is the strong embedding of maximum genus, is given. In addition, some graphs with the property are provided. More generally, an upper bound of the maximum genus of strong embeddings of a graph is presented too. Lastly, it is shown that the interpolation theorem is true to planar Halin graph. |
| |
| Keywords: | CDC Halin graph strong embedding genus surface |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
|
