关于图的最大亏格的一些新研究
|
摘要
拓扑图论最初是研究怎样把图画在曲面上使得任何两条边互不相交,这个直观的几何问题随着其它数学分支,特别是代数拓扑、群论、组合计数理论以及算法分析等的介入而变得丰富多彩.目前拓扑图论的研究领域可分为两个主流:一是研究图在曲面上嵌入的性质;另一个研究地图计数问题.本文研究属第一个方面,即研究图的嵌入的最大亏格问题.
连通图G在紧的闭曲面S上的嵌入指存在一个同胚映射Φ:G→S使得S-Φ(G)的每个连通分支都同胚于一个开圆盘,这样的嵌入称为胞腔嵌入.根据S是可定向曲面或者是不可定向曲面,这样的嵌入又分别称为可定向嵌入或不可定向嵌入.图G的最大亏格指图G所能嵌入曲面的亏格中最大的那一个.因为图的任何嵌入必至少含有一个面,由欧拉公式易得图的最大亏格的一个上界:其中符号[α]指不超过α的最大整数,|E(G)|-|V(G)|+1被称为图G=(V(G).E(G))的Betti数并用符号β(G)表示.如果γ_M(G)=[(?)],则图G被称为上可嵌入的.最大亏格问题起源于Nordhaus、Stewart和White1971年的文章[31],刘彦佩[21]和Xuong[38]于1979年分别独立地得到了关于图的嵌入的最大亏格的经典定理,随后,由于诸多学者对这一问题的关注与研究使得这一问题取得重大进展.其研究分为两个方面:一是图的上可嵌入性的研究;二是对非上可嵌入图的最大亏格的界的研究.因为任意图在不可定向曲面上总是上可嵌入的,因此最大亏格问题只讨论图在可定向曲面上的嵌入.
在本论文中,一方面,借助已有的研究成果对图的最大亏格问题进行了深入地研究,得出了一些新结果,改进了一些已知结果;另一方面,借助刘彦佩提出的联树法,对最大亏格问题从另一个方面进行了一些尝试性的研究,并取得一些初步进展.本文可分为以下几个部分:
第一章介绍图的最大亏格问题的背景知识以及一些基本概念和术语.
第二章研究了直径-3图中的加边运算与最大亏格.
第三章结合图的围长以及相邻顶点或非邻顶点的度和研究图的上可嵌入性.
第四章研究非上可嵌入图的最大亏格的下界问题.
第五章借助联树模型研究图的最大亏格.
第六章介绍了一些需要进一步研究的问题.
To study the drawing of a graph on a surface such that no two edges cross, which is an intuitive geometric problem, is the primitive objective of topological graph theory. Armed with other mathematical branches such as algebraic topology and group theory, and enumerative combinatorics, and the analysis of algorithms. topological graph theory has been becoming more and more meaningful.There are two fields in topological graph theory: one is the study of the properties of graph embedding. and the other is the enumerative theory of maps. This paper concerns the maximum genus of graphs which belongs to the first field.
The embedding of a graph G on a surface S is such a homeomorphismΦ:G→S that each connected component of S-Φ(G) is homeomorphic to a open disk. According to S is orientable or nonoricntable surface, the embeddingΦof G on S is called orientable embedding or nonorientable embedding respectively. The maximum genusγ_M(G) of a connected graph G is the maximum integer k such that there exists an embedding of G into the orientable surface of genus k. Since any embedding must have at least one face, the Euler characteristic for one face leads to an upper bound on the maximum genuswhere the number |E(G)|- |V(G)|+1 is known as the Betti number (or cycle rank) of the connected graph G and is denoted byβ(G). A graph G is said to be up-embeddable ifγ_M(G)=(?).The idea of the maximum genusγ_M/(G) of a connected graph G was introduced by Nordhaus. Stewart and White [31] in 1971. In 1979, Liu[21] and Xuong|38] obtained the classical Theorem on the maximum genus independently. From then on. many researchers have studied the problem and obtained many interesting results. The research on maximum genus is mainly focused on two aspects: one is the study of the up-embeddability of graphs, and the other is the lower bound on the maximum genus of non-up-embeddable graphs. Because every graph is up-embeddable on non-orient able surfaces, the maximum genus problem only study orientable embeddings.
This thesis consists of two parts: one is the deeper study of the maximum genus via the results obtained in the foretime: the other is an attempt on the studying of the maximum genus through joint tree, which is established by Liu Yanpei. The thesis are composed of the following six chapters:
In chapter 1, the background of the maximum genus and some definitions and terminologies are provided.
In chapter 2, the relation between the maximum genus and the edge-adding operation on graphs of diameter 3 are discussed.
Chapter 3 is focused on the study of up-embeddability of graphs via girth and the degree-sum of adjacent vertices or nonadjacent vertices.
In chapter 4 the lower bound of the maximum genus of graphs non-upembeddablc is discussed.
Chapter 5 focuses on the study of the maximum genus of graphs via joint tree model.
Chapter 6 consists of some problems worth studying further.
连通图G在紧的闭曲面S上的嵌入指存在一个同胚映射Φ:G→S使得S-Φ(G)的每个连通分支都同胚于一个开圆盘,这样的嵌入称为胞腔嵌入.根据S是可定向曲面或者是不可定向曲面,这样的嵌入又分别称为可定向嵌入或不可定向嵌入.图G的最大亏格指图G所能嵌入曲面的亏格中最大的那一个.因为图的任何嵌入必至少含有一个面,由欧拉公式易得图的最大亏格的一个上界:其中符号[α]指不超过α的最大整数,|E(G)|-|V(G)|+1被称为图G=(V(G).E(G))的Betti数并用符号β(G)表示.如果γ_M(G)=[(?)],则图G被称为上可嵌入的.最大亏格问题起源于Nordhaus、Stewart和White1971年的文章[31],刘彦佩[21]和Xuong[38]于1979年分别独立地得到了关于图的嵌入的最大亏格的经典定理,随后,由于诸多学者对这一问题的关注与研究使得这一问题取得重大进展.其研究分为两个方面:一是图的上可嵌入性的研究;二是对非上可嵌入图的最大亏格的界的研究.因为任意图在不可定向曲面上总是上可嵌入的,因此最大亏格问题只讨论图在可定向曲面上的嵌入.
在本论文中,一方面,借助已有的研究成果对图的最大亏格问题进行了深入地研究,得出了一些新结果,改进了一些已知结果;另一方面,借助刘彦佩提出的联树法,对最大亏格问题从另一个方面进行了一些尝试性的研究,并取得一些初步进展.本文可分为以下几个部分:
第一章介绍图的最大亏格问题的背景知识以及一些基本概念和术语.
第二章研究了直径-3图中的加边运算与最大亏格.
第三章结合图的围长以及相邻顶点或非邻顶点的度和研究图的上可嵌入性.
第四章研究非上可嵌入图的最大亏格的下界问题.
第五章借助联树模型研究图的最大亏格.
第六章介绍了一些需要进一步研究的问题.
To study the drawing of a graph on a surface such that no two edges cross, which is an intuitive geometric problem, is the primitive objective of topological graph theory. Armed with other mathematical branches such as algebraic topology and group theory, and enumerative combinatorics, and the analysis of algorithms. topological graph theory has been becoming more and more meaningful.There are two fields in topological graph theory: one is the study of the properties of graph embedding. and the other is the enumerative theory of maps. This paper concerns the maximum genus of graphs which belongs to the first field.
The embedding of a graph G on a surface S is such a homeomorphismΦ:G→S that each connected component of S-Φ(G) is homeomorphic to a open disk. According to S is orientable or nonoricntable surface, the embeddingΦof G on S is called orientable embedding or nonorientable embedding respectively. The maximum genusγ_M(G) of a connected graph G is the maximum integer k such that there exists an embedding of G into the orientable surface of genus k. Since any embedding must have at least one face, the Euler characteristic for one face leads to an upper bound on the maximum genuswhere the number |E(G)|- |V(G)|+1 is known as the Betti number (or cycle rank) of the connected graph G and is denoted byβ(G). A graph G is said to be up-embeddable ifγ_M(G)=(?).The idea of the maximum genusγ_M/(G) of a connected graph G was introduced by Nordhaus. Stewart and White [31] in 1971. In 1979, Liu[21] and Xuong|38] obtained the classical Theorem on the maximum genus independently. From then on. many researchers have studied the problem and obtained many interesting results. The research on maximum genus is mainly focused on two aspects: one is the study of the up-embeddability of graphs, and the other is the lower bound on the maximum genus of non-up-embeddable graphs. Because every graph is up-embeddable on non-orient able surfaces, the maximum genus problem only study orientable embeddings.
This thesis consists of two parts: one is the deeper study of the maximum genus via the results obtained in the foretime: the other is an attempt on the studying of the maximum genus through joint tree, which is established by Liu Yanpei. The thesis are composed of the following six chapters:
In chapter 1, the background of the maximum genus and some definitions and terminologies are provided.
In chapter 2, the relation between the maximum genus and the edge-adding operation on graphs of diameter 3 are discussed.
Chapter 3 is focused on the study of up-embeddability of graphs via girth and the degree-sum of adjacent vertices or nonadjacent vertices.
In chapter 4 the lower bound of the maximum genus of graphs non-upembeddablc is discussed.
Chapter 5 focuses on the study of the maximum genus of graphs via joint tree model.
Chapter 6 consists of some problems worth studying further.
引文
[1] D. Archdeacon. J. Chen. Y. Huang, S.P. Kanchi. D. Li, Y. Liu. R. Nedela, and M. Skoviera, Maximum genus, connectivity, and Nebesky's Theorem, To appear in Discrete Math.
[2] J.A. Bondy, U.S.R. Murty. Graph Theory with Applications. Macmillan, London, 1976.
[3] J. Chen, D. Archdeacon, and J.L. Gross, Maximum genus and connectivity, Discrete Math., 149(1996), 19-29.
[4] J. Chen, S.P. Kanchi. and J.L. Gross, A tight lower bound on the maximum genus of a simplicial graph. Discrete Math., 156(1996), 83-102.
[5] H. Fu. M. Tasi, The maximum genus of diameter three graphs, Australation J. Combin.,14(1996), 187-197.
[6] H. Fu, M. Tasi, and N.H. Xuong ,The decay number and the maximum genus of diameter 2 graphs. Discrete Math., 226(2001), 191-197.
[7] M. Furst, J.L. Gross, and L.A. McMeoch, Finding a maximum-genus graph imbedding. J. Assoc.Comput. Mach., 35(1988), 507-537.
[8] J.L. Gross, T.W. Tucker, Topological Graph Theory. Wiley-Inter science. New York. 1987.
[9] W. He, Y. Liu. For a new condition on up-embeddability of graphs, OR Transactions. 7(3) (2003). 92-96.
[10] W. He, Y. Liu, A note on the maximum genus of graph G3. J. Syst Sci and Infor. 1(4)(2003). 615-619.
[11] Y. Huang, Y. Liu. Maximum genus and maximum nonseparating independent set of a 3-regular graph, Discrete Math.. 176(1997). 149-158.
[12] Y. Huang, Y. Liu. The degree sum of nonadjacent vertices and upper embcddability of graphs. Chin Ann of Math., 5(19A)(1998). 651-656 (in Chinese).
[13] Y. Huang, Y. Liu, Maximum genus of graphs with diameter three. Discrete Math.. 194(1999), 139-203.
[14] Y. Huang. Y. Liu, Face size and the maximum genus of a graph, J Combin. Theory Ser B., 80(2000). 356-370.
[15] Y. Huang, The maximum genus on a 3-vcrtex-connected graph, Graphs and Combinatorics., 16(2001), 159-164.
[16] Y. Huang. Maximum genus and chromatic number of graphs. Discrete Math.. 271(2003). 117-127.
[17] F. Jaeger, C. Payan. N.H. Xuong. A classes of upper embeddable graphs. J. Graph Theory.. 3(1979). 387-391.
[18] M. Jungerment, A characterization of upper embeddable graphs, Trans. Math. Soc.,241(1979). 401-406.
[19] S. Kundu. Bounds on number of disjoint spanning trees. J. Combin. Theory Ser B.,17(1974), 199-203.
[20] D. Li and Y. Liu, Maximum genus, girth and connectivity, Europ. J. Combin., 21(2000), 651-657.
[21] Y. Liu, The maximum orientable genus of a graph. Scientia Sinical (Special Issue).(Ⅱ)(1979), 41-55.
[22] Y. Liu, The nonorientable maximum genus of a graph (in Chinese), Scientia Sinical(Special Issue on Math ), (Ⅰ)(1979). 191-201.
[23] Y. Liu, Embcddability in Graphs. Kluwer Academic. Dordrecht, Boston. London. 1995.
[24] Y. Liu,组合地图进阶,北方交通大学出版社.北京,2003.
[25] Y. Liu,地图的代数原理,高等教育出版社,北京,2006.
[26] Y. Liu, Theory of Polyhedra. Science Press. Beijing. 2008.
[27] Y. Liu, Topological Theory on Graphs, USTC Press, Hefei, 2008.
[28] U.S.R. Murty. On some extremal graphs. Acad Sci Hung., 19(1969). 69-74.
[29] U.S.R. Murty, Extremal nonseparable graphs of diameter 2. in: F.Harary (Ed.), Proof Techniques in Graph Theory. New York. Academic Press. (1969), 111-118.
[30] L. Nebesk(?), A new characterization of the maximum genus of a graph. Czechoslova Math. J., 31(106)(1981). 604-613.
[31] E.A. Nordhause, B.M. Stewart, A.T. White. On the maximum genus of a graph, J. Combin. Theory.. 11(1971), 258-267.
[32] Z.D. Ouyang, Y. Huang. Q. Zhang, Upper embeddability of graphs and independent number, the degree sum of nonadjacent vertices. Acta Mathematicae Applicatae Sinica, 2007, 30(4):689-698(in Chinese).
[33] R. Ringciscn. The maximum genus of a graph, Ph. D. Thesis. Michigan State Univ., 1970.
[34] R. Ringeiscn. Upper and lower cmbeddable graphs, Graph Theory and Applications. Lecture Notes in Math., Springer-Verlag, Berlin and New York. 303(1972).
[35] R. Ringeisen. Determining all compact orientable 2-manifolds upon which K_(m,n) has 2-cell imbeddings, J. Combin. Theory., 12(1974), 101-104.
[36] M. Skoviera, The maximum genus of graphs diameter two, Discrete Math., 87(1991), 175-180.
[37] A.T. White, Graphs, Groups, and Surfaces. Amsterdam, North-Holland. 1984.
[38] N.H. Xuong, How to determine the maximum genus of a graph. J. Combin. Theory Ser B., 26(1979). 217-225.
[2] J.A. Bondy, U.S.R. Murty. Graph Theory with Applications. Macmillan, London, 1976.
[3] J. Chen, D. Archdeacon, and J.L. Gross, Maximum genus and connectivity, Discrete Math., 149(1996), 19-29.
[4] J. Chen, S.P. Kanchi. and J.L. Gross, A tight lower bound on the maximum genus of a simplicial graph. Discrete Math., 156(1996), 83-102.
[5] H. Fu. M. Tasi, The maximum genus of diameter three graphs, Australation J. Combin.,14(1996), 187-197.
[6] H. Fu, M. Tasi, and N.H. Xuong ,The decay number and the maximum genus of diameter 2 graphs. Discrete Math., 226(2001), 191-197.
[7] M. Furst, J.L. Gross, and L.A. McMeoch, Finding a maximum-genus graph imbedding. J. Assoc.Comput. Mach., 35(1988), 507-537.
[8] J.L. Gross, T.W. Tucker, Topological Graph Theory. Wiley-Inter science. New York. 1987.
[9] W. He, Y. Liu. For a new condition on up-embeddability of graphs, OR Transactions. 7(3) (2003). 92-96.
[10] W. He, Y. Liu, A note on the maximum genus of graph G3. J. Syst Sci and Infor. 1(4)(2003). 615-619.
[11] Y. Huang, Y. Liu. Maximum genus and maximum nonseparating independent set of a 3-regular graph, Discrete Math.. 176(1997). 149-158.
[12] Y. Huang, Y. Liu. The degree sum of nonadjacent vertices and upper embcddability of graphs. Chin Ann of Math., 5(19A)(1998). 651-656 (in Chinese).
[13] Y. Huang, Y. Liu, Maximum genus of graphs with diameter three. Discrete Math.. 194(1999), 139-203.
[14] Y. Huang. Y. Liu, Face size and the maximum genus of a graph, J Combin. Theory Ser B., 80(2000). 356-370.
[15] Y. Huang, The maximum genus on a 3-vcrtex-connected graph, Graphs and Combinatorics., 16(2001), 159-164.
[16] Y. Huang. Maximum genus and chromatic number of graphs. Discrete Math.. 271(2003). 117-127.
[17] F. Jaeger, C. Payan. N.H. Xuong. A classes of upper embeddable graphs. J. Graph Theory.. 3(1979). 387-391.
[18] M. Jungerment, A characterization of upper embeddable graphs, Trans. Math. Soc.,241(1979). 401-406.
[19] S. Kundu. Bounds on number of disjoint spanning trees. J. Combin. Theory Ser B.,17(1974), 199-203.
[20] D. Li and Y. Liu, Maximum genus, girth and connectivity, Europ. J. Combin., 21(2000), 651-657.
[21] Y. Liu, The maximum orientable genus of a graph. Scientia Sinical (Special Issue).(Ⅱ)(1979), 41-55.
[22] Y. Liu, The nonorientable maximum genus of a graph (in Chinese), Scientia Sinical(Special Issue on Math ), (Ⅰ)(1979). 191-201.
[23] Y. Liu, Embcddability in Graphs. Kluwer Academic. Dordrecht, Boston. London. 1995.
[24] Y. Liu,组合地图进阶,北方交通大学出版社.北京,2003.
[25] Y. Liu,地图的代数原理,高等教育出版社,北京,2006.
[26] Y. Liu, Theory of Polyhedra. Science Press. Beijing. 2008.
[27] Y. Liu, Topological Theory on Graphs, USTC Press, Hefei, 2008.
[28] U.S.R. Murty. On some extremal graphs. Acad Sci Hung., 19(1969). 69-74.
[29] U.S.R. Murty, Extremal nonseparable graphs of diameter 2. in: F.Harary (Ed.), Proof Techniques in Graph Theory. New York. Academic Press. (1969), 111-118.
[30] L. Nebesk(?), A new characterization of the maximum genus of a graph. Czechoslova Math. J., 31(106)(1981). 604-613.
[31] E.A. Nordhause, B.M. Stewart, A.T. White. On the maximum genus of a graph, J. Combin. Theory.. 11(1971), 258-267.
[32] Z.D. Ouyang, Y. Huang. Q. Zhang, Upper embeddability of graphs and independent number, the degree sum of nonadjacent vertices. Acta Mathematicae Applicatae Sinica, 2007, 30(4):689-698(in Chinese).
[33] R. Ringciscn. The maximum genus of a graph, Ph. D. Thesis. Michigan State Univ., 1970.
[34] R. Ringeiscn. Upper and lower cmbeddable graphs, Graph Theory and Applications. Lecture Notes in Math., Springer-Verlag, Berlin and New York. 303(1972).
[35] R. Ringeisen. Determining all compact orientable 2-manifolds upon which K_(m,n) has 2-cell imbeddings, J. Combin. Theory., 12(1974), 101-104.
[36] M. Skoviera, The maximum genus of graphs diameter two, Discrete Math., 87(1991), 175-180.
[37] A.T. White, Graphs, Groups, and Surfaces. Amsterdam, North-Holland. 1984.
[38] N.H. Xuong, How to determine the maximum genus of a graph. J. Combin. Theory Ser B., 26(1979). 217-225.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |