| CYCLE SPACES OF GRAPHS ON THE SPHERE AND THE PROJECTIVE PLANE |
| |
| 作者姓名： | 任韩 刘彦佩 马登举 卢俊杰 |
| |
| 作者单位： | [1]DepartmentofMathematics,EastChinaNormalUiversity,Shanghai200062,China [2]DepartmentofMathematics,NorthernJiaotongUniversity,Beijing.100044,China |
| |
| 基金项目： | 国家自然科学基金，国家自然科学基金 |
| |
| 摘 要： | Cycle base theory of a graph has been well studied in abstract mathematical field such matroid theory as Whitney and Tutte did and found many applications in pratical uses such as electric circuit theory and structure analysis, etc. In this paper graph embedding theory is used to investigate cycle base structures of a 2-(edge)-connected graph on the sphere and the projective plane and it is shown that short cycles do generate the cycle spaces in the case of ““““small face-embeddings““““. As applications the authors find the exact formulae for the minimum lengthes of cycle bases of some types of graphs and present several known results. Infinite examples shows that the conditions in their main results are best possible and there are many 3-connected planar graphs whose minimum cycle bases can not be determined by the planar formulae but may be located by re-embedding them into the projective plane.
|
| 关 键 词： | 循环空间 图形嵌入 球 投影平面 |
| 收稿时间： | 25 April 2002 |
CYCLE SPACES OF GRAPHS ON THE SPHERE AND THE PROJECTIVE PLANE |
| |
| REN Han,Liu Yanpei,Ma Dengju,LU Junjie.CYCLE SPACES OF GRAPHS ON THE SPHERE AND THE PROJECTIVE PLANE[J].Acta Mathematica Scientia,2005,25(1):41-49. |
| |
| Authors: | REN Han Liu Yanpei Ma Dengju LU Junjie |
| |
| Institution: | 1. Department of Mathematics, The Ohio State University, Columbus, OH, USA;2. Department of Mathematical Sciences, State University of New York at Binghamton, Binghamton, NY, USA;3. Department of Mathematics, Wright State University, Dayton, OH, USA;1. Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30323, USA;2. School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA;1. Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA;2. Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508-090 São Paulo, Brazil;3. Department of Mathematics, Duksung Women''s University, Seoul 01369, South Korea;4. School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel;5. Trinity College, Cambridge CB2 1TQ, UK;1. Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India;2. Department of Informatics, University of Bergen, Norway;1. Department of Mathematics, Institute for Advanced Studies in Basic Sciences, Zanjan 45137-66731, Iran;2. Department of Pure Math., Faculty of Math. and Computer Sci., Amirkabir University of Technology (Tehran Polytechnic), 424, Hafez Ave., Tehran 15914, Iran;3. Department of Mathematics, Qom University of Technology, Qom, Iran |
| |
| Abstract: | Cycle base theory of a graph has been well studied in abstract mathematical field such matroid theory as Whitney and Tutte did and found many applications in pratical uses such as electric circuit theory and structure analysis, etc. In this paper graph embedding theory is used to investigate cycle base structures of a 2-(edge)-connected graph on the sphere and the projective plane and it is shown that short cycles do generate the cycle spaces in the case of "small face-embeddings". As applications the authors find the exact formulae for the minimum lengthes of cycle bases of some types of graphs and present several known results. Infinite examples shows that the conditions in their main results are best possible and there are many 3-connected planar graphs whose minimum cycle bases can not be determined by the planar formulae but may be located by re-embedding them into the projective plane. |
| |
| Keywords: | Cycle base facial cycle graph embedding |
| 本文献已被 CNKI 维普 万方数据 ScienceDirect 等数据库收录！ |
|
