关于几类图的嵌入分布研究
|
摘要
已知一个连通图G和一个闭曲面S(无边缘的紧2-维流形),若存在一个1-1连续映射h：G→S,使得S-h(G)的每个连通分支均是一个2-胞腔,则称G在S上有一个胞腔嵌入。若曲面S是可定向的,则嵌入是可定向嵌入；若曲面S是不可定向的,则嵌入是不可定向嵌入。图G在曲面S上的两个嵌入h：G→S和g：G→S是等价的当且仅当存在一个同胚f：S→S使得fοh=g.图的曲面嵌入问题是拓扑图论的一个重要的研究分支,它主要是研究图的可嵌入理论和嵌入计数理论。
每一个图都可以嵌入到某个曲面上,使得一个图G可以嵌入到亏格为k的曲面Sk的最小非负正整数k称为是G的亏格。那么图在各种不同亏格的曲面上各有多少个不等价的嵌入呢?这就是图的嵌入亏格分布问题。
图在曲面上的嵌入分布作为拓扑图论的一个重要研究问题,目前为止所得结果仍然很少。对它的研究的方法从如下方面开展：对于一些具有对称性的图,根据旋与嵌入的对应关式,对其循环置换群的圈结构的分解进行计数；基于Ringle-White加边的组合拓扑方法；Mohar B提出的覆盖矩阵以及近年来的刘彦佩教授提出的嵌入的联树模型。总体而言,每种方法解决某些图的嵌入亏格分布都有一定的局限性。
另外,组合序列的(强)单峰性一直组合数学家关注的一个课题。迄今为止,图的可定向嵌入分布序列的(强)单峰性对已知的几类图是成立的。图的不可定向嵌入分布序列的(强)单峰性还没有类似的结果。总之,图的(不)可定向嵌入分布序列的(强)单峰性猜想至今还是一个谜。此外,单峰点的位置的求解也是一个热门的研究方向。
在本论文中,我们首先根据Chebyshev第二类多项式的性质,得到了一类含有两个参数的齐次和非齐次的递推关系的解的解析式。其次,我们利用B.Mohar的覆盖矩阵方法,得到了Closed-end ladders和Cobblestone path两类图的精确的可定向亏格分布和完全亏格分布表达式；再者,对于任意的自然数对(r,s),通过程序计算,我们发现(r,s)型necklaces不可定向亏格分布是单峰的,并且猜测了它的单峰点的具体位置。进一步研究,我们发现其单峰点位置与图的平均亏格之间存在一定的联系,于是我们提出了一个关于单峰点与平均亏格的猜想。
Given a connected graph G and a surface S(a compact closed 2-dimensional manifold without boundary), if there exists a homeomorphism h:G→S, such that each connected component of S→h(G) is a 2-cell, then h(G) is an embedding (in early reference called 2-cell embedding)on S. If S is orientable, then the embed-ding is orientable; else if S is nonorientable, then the embedding is non-orientable. Two embeddings h:G→S and g:G→S of G on a surface S are said to be equivalent if there is a homeomorphism f:S→S, such that f(?)h=g. The embedding theory of graph is one of the most important branches in topological graph theory and it studies mainly on embeddability and counting theory.
Each graph can be embedded onto some surface and the genus of a graph G is the smallest non-positive integer k, such that G can be embedded on the surface Sk with the genus k. Then how many distinct embeddings dose a graph have on surfaces with different genus? This is the problem of embedding genus distribution for a graph.
The classification for the graph embedding onto the surface is an important research direction of the topological graph, the results obtained in such field are still very few and the research techniques are mainly as follows:the combinatorial enumeration formulae of Jackson D.M;the topological method by adding edges; the overlap-matrix method by Mohar.B and the joint tree model introduced by Y.P.Liu recently. On the whole, each method has its limitation to study the embedding distribution for the embedding of some class of graph.
In addition, the (strongly) unimodal enumerative sequence is a hot topic stud-ied by the combinatorists. Up to now, the (strong) unimodality of the orientable embedding distribution for some known graph has been verified, whereas there is still not any similar result for the non-orientable embedding distribution. On the whole, the conjecture that the embedding sequence is (strongly)unimodal is still a riddle. In addition, the solution of the mode is also a hot research field.
In this thesis, firstly, by the property of the Chebyshev polynomials of the second kind, we obtain the solutions for a class of constant coefficient homogeneous and non-homogenous recurrence relations with two indices; Secondly, using the overlap-matrix method, we obtain the explicit formulaes of the orientable and the total embedding distribution for the two classes of graphs:Closed-end ladders and Cobblestone path. Furthermore, by computation, we verify the unimodality for' the non-orientable embedding distribution for the (r,s) necklaces and derive the mode of it. By further study, we discover that there exists some relation between the mode and the average genus for such graph embedding, which makes us to pose one conjecture on the relation for the mode and the average genus in general case.
每一个图都可以嵌入到某个曲面上,使得一个图G可以嵌入到亏格为k的曲面Sk的最小非负正整数k称为是G的亏格。那么图在各种不同亏格的曲面上各有多少个不等价的嵌入呢?这就是图的嵌入亏格分布问题。
图在曲面上的嵌入分布作为拓扑图论的一个重要研究问题,目前为止所得结果仍然很少。对它的研究的方法从如下方面开展：对于一些具有对称性的图,根据旋与嵌入的对应关式,对其循环置换群的圈结构的分解进行计数；基于Ringle-White加边的组合拓扑方法；Mohar B提出的覆盖矩阵以及近年来的刘彦佩教授提出的嵌入的联树模型。总体而言,每种方法解决某些图的嵌入亏格分布都有一定的局限性。
另外,组合序列的(强)单峰性一直组合数学家关注的一个课题。迄今为止,图的可定向嵌入分布序列的(强)单峰性对已知的几类图是成立的。图的不可定向嵌入分布序列的(强)单峰性还没有类似的结果。总之,图的(不)可定向嵌入分布序列的(强)单峰性猜想至今还是一个谜。此外,单峰点的位置的求解也是一个热门的研究方向。
在本论文中,我们首先根据Chebyshev第二类多项式的性质,得到了一类含有两个参数的齐次和非齐次的递推关系的解的解析式。其次,我们利用B.Mohar的覆盖矩阵方法,得到了Closed-end ladders和Cobblestone path两类图的精确的可定向亏格分布和完全亏格分布表达式；再者,对于任意的自然数对(r,s),通过程序计算,我们发现(r,s)型necklaces不可定向亏格分布是单峰的,并且猜测了它的单峰点的具体位置。进一步研究,我们发现其单峰点位置与图的平均亏格之间存在一定的联系,于是我们提出了一个关于单峰点与平均亏格的猜想。
Given a connected graph G and a surface S(a compact closed 2-dimensional manifold without boundary), if there exists a homeomorphism h:G→S, such that each connected component of S→h(G) is a 2-cell, then h(G) is an embedding (in early reference called 2-cell embedding)on S. If S is orientable, then the embed-ding is orientable; else if S is nonorientable, then the embedding is non-orientable. Two embeddings h:G→S and g:G→S of G on a surface S are said to be equivalent if there is a homeomorphism f:S→S, such that f(?)h=g. The embedding theory of graph is one of the most important branches in topological graph theory and it studies mainly on embeddability and counting theory.
Each graph can be embedded onto some surface and the genus of a graph G is the smallest non-positive integer k, such that G can be embedded on the surface Sk with the genus k. Then how many distinct embeddings dose a graph have on surfaces with different genus? This is the problem of embedding genus distribution for a graph.
The classification for the graph embedding onto the surface is an important research direction of the topological graph, the results obtained in such field are still very few and the research techniques are mainly as follows:the combinatorial enumeration formulae of Jackson D.M;the topological method by adding edges; the overlap-matrix method by Mohar.B and the joint tree model introduced by Y.P.Liu recently. On the whole, each method has its limitation to study the embedding distribution for the embedding of some class of graph.
In addition, the (strongly) unimodal enumerative sequence is a hot topic stud-ied by the combinatorists. Up to now, the (strong) unimodality of the orientable embedding distribution for some known graph has been verified, whereas there is still not any similar result for the non-orientable embedding distribution. On the whole, the conjecture that the embedding sequence is (strongly)unimodal is still a riddle. In addition, the solution of the mode is also a hot research field.
In this thesis, firstly, by the property of the Chebyshev polynomials of the second kind, we obtain the solutions for a class of constant coefficient homogeneous and non-homogenous recurrence relations with two indices; Secondly, using the overlap-matrix method, we obtain the explicit formulaes of the orientable and the total embedding distribution for the two classes of graphs:Closed-end ladders and Cobblestone path. Furthermore, by computation, we verify the unimodality for' the non-orientable embedding distribution for the (r,s) necklaces and derive the mode of it. By further study, we discover that there exists some relation between the mode and the average genus for such graph embedding, which makes us to pose one conjecture on the relation for the mode and the average genus in general case.
引文
[1]Ringel G. Non-existence of Graph Embedding, In "Theory and Applications of Graphs". Lecture Notes Math.,Berlin:Springer-Verlag,1978,642:465-476
[2]Stahl S. Generalized Embedding Schemes. J. Graph Theory,1978,2:41-52
[3]Hoffman P, Richter B. Embedding graphs in surfaces. J.Combin.Theory Ser.B, 1984,36:65-84
[4]Edmonds J R. A Combinatorial Representation For Polyhedral Surfaces. No-tices Amer.Math.Soc.,1960,7:646
[5]Heawood P J. Map-color Theorem. Quart. J. Pure. Appl. Math.,1890,24:332-338
[6]Gross J L, Tucker T W. Topological Graph Theory. New York:Wiley Inter-science,1987
[7]Robertson N, Zha X Y,Zhao Y. On The Flexibility of Toroidal Embeddings. J.Combin.Theory Ser.B,2008,98(1):43-61
[8]Gross J L, Furst M L. Hierarchy of Imbedding Distribution Invariants of Graph. J.Graph Theory,1987,11:205-220
[9]刘彦佩.组合地图进阶.北京：北京交通大学出版社,2003
[10]刘彦佩.图的代数原理.北京：高等教育出版社,2006
[11]Chen J, Gross J, Rieper R G. Overlap Matrices And Total Embeddings. Dis-crete Math,1994,128:73-94
[12]Kwak J H, Shim S H. Total Embedding Distributions for Bounquets of Circles. Discrete Math,2002,248:93-108
[13]Chen Y C, Liu Y P, Wang T. The Total Embedding Distributions of Cacti And Necklaces. Acta Mathematica Sinica,2006,22(5):1583-1590
[14]Li L F, Liu Y P. Genus Distribution of Embeddings for A Type of A 3-Regular Graph. J.Beijing Jiaotong Univ.,2004,28(6):39-42
[15]Liu Y P. Embeddability In Graphs. Dordrecht, Boston, London:Kluwer Aca-demic Publisher,1995
[16]Deng M, Ren H. Flexibility Of Embeddings Of Wheel Graphs On The Torus.华东师范大学学报(自然科学版),2006,1：57-62
[17]Gary Chartrand, Zhang P. Introduction To Graph Theory. Beijing:Posts and Telecom Press,2007
[18]Mohar B, Thomassen C. Graphs On Surfaces. Baltimore:The Johns Hopkins University Press,2001
[19]Furst M, Gross J, Statman R. Genus Distributions For Two Classes Of Graphs. J. Combin. Ser. B,1989,46:22-36
[20]Mansour T, Schork M. The Solution Of The Recurrence Relation fn(t)= an(t)fn-1(t)-bn(t)((?)/(?)t)fn-1(t), J.Diff. Eq. Appl.,2009 15(7):679-691
[21]余长安.两个参数的递推公式的解公式.武汉大学学报(自科版),1990,(1)：1-6
[22]余长安.一类系数依赖于双指标的非齐次递推式之解.应用数学学报,1997,20(2)：316-320
[23]余长安.一类带双指标常系数齐次递推关系的显示解.应用数学学报,1997,20(1)：119-127
[24]余长安.关于一类两个指标的齐次递推关系的解的结构.数学物理学报,2002,22A(1)：55-60
[25]Mansour T. Combinatorial Methods And Recurrence Relation With Two In-dices. J. Diff. Eq. Appl.,2006,12(6):555-563
[26]Mansour T. Recurrence Relations With Two Indices And Even Trees. J. Diff. Eq. Appl.,2007,13(1):47-61
[27]Mansour T, Song C W. Kernel Method And System Of Functional Equations, J. Compu. App. Math,22(4):133-139
[28]Andrews G E. The Theory of Partitions. Cambridge:Cambridge University Press,1984
[29]Stanley R P. Enumerative Combinatorics. Cambridge:Cambridge University Press, vol.1,second printing,1996
[30]Andrews G E, Askey R, Roy R. Special Functions. Cambridge:Cambridge University Press,2000
[31]Th. Rivlin. Chebyshev polynomials:From Approximation Theory To Algebra And Number Theory. New York:John Wiley,1990
[32]Chen Y C,T.Manour, Zou Q.On The Total Embedding Distribution for Four Types of Graphs. Submitted
[33]Archdeacon D. Calculations On The Average Genus And Genus Distribution Of Graphs.Congr. Numer.1988,67:114-124
[34]Gross J L, Robbins D P, Tucker T W. Genus Distributions for Bouquets of Circles. J.Combin.Theory Ser. B,1989,47:292-306
[35]Kwak J H, Lee J. Genus Polynomials of Dipoles. Kyungpook Math. Journal,1993,33:115-125
[36]Tesar E H. Genus Distributions for Ringel Ladders. Discrete Math. J.,2000,216(1):235-252
[37]Li D M. Genus Distribution of Circular Ladders. Northeast Math. J. 2000,16(2):181-189
[38]Li D M. Genus Distribution of Mobius Ladders. Northeast Math. J. 2005,21(1):70-80
[39]赵喜梅,刘彦佩.类树图的嵌入多项式.北京交通大学学报,2004,28(3)：7-11
[40]Yang Y, Hao R X. Classification of Embeddings of Fan Graph on Surfaces. Acta Math Appli Sinica.,2008,31(5):792-798
[41]Hao R X, Liu Y P. The Genus Distributions of Directed Antiladders in Ori-entable Surfaces. Appl.Math. Lett.,2008,21 (2):161-164
[42]Wan L X, On Orientable Embedding Genus Distribution of A Graph:[ Ph.D.Dissertation].Beijing:Beijing JiaoTong University,2006
[43]Wan L X, Liu Y P. Orientable Embedding Genus Distribution For Certain Types of Graphs. J. Comb. Theory, Ser. B,2008,98(1):19-32
[44]Jackson D.M. Counting Cycles in Permutations by Group Characters, with An Application to A Topological Prolbem. Trans.Amer.Math. Soc,1987,299:785-801
[45]Mohar B. An Obstuction To Embedding Graphs in Surfaces. Discrete Math, 1989,78:135-142
[46]Chen J, Gross J, R.G.Rieper. Lower Bounds for The Average Genus. J.Graph Theory,1995,19:281-296
[47]Chen Y C. Remarks On The Lower Bounds For The Average Genus. Manuscript
[48]Chen Y C, Liu Y P. A Tight Lower Bound for the Average Crosscap Num-ber.Submitted
[49]Coratet.L. Advanced combinatorics. Boston:Reidel Publication company,1974
[50]Stahl.S. On The Zeros Of Some Polynomial. Can. J. Math.,1996,49:617-640
[51]赵喜梅,刘彦佩.类树图亏格分布的单峰性.山西大学学报(自然科学版)2006,29(3)：242-244
[52]Stanley. R. P. Log-concave And Unimodal Sequences In Algebra. Combina-torics And Gometry, Ann. New York Acad.Sci.,1980,576:500-534
[53]Wang Y, Yeh.Y.N. Proof of A Conjecture On Unimodality. European J.Combin.2006,26:617-627
[54]Wang Y,Yeh.Y.N. Log-concavity and LC-positivity. J.Combin.Theory Ser.A. 2007,114:195-120
[55]Chen Y C,Liu Y P.On The Average Crosscap Number of A Graph.Manuscript.
[56]Yang Y, Liu Y P. Number of Embeddings of Wheel Graphs on Surfaces of Small Genus. Accepted by Ars Combin.
[2]Stahl S. Generalized Embedding Schemes. J. Graph Theory,1978,2:41-52
[3]Hoffman P, Richter B. Embedding graphs in surfaces. J.Combin.Theory Ser.B, 1984,36:65-84
[4]Edmonds J R. A Combinatorial Representation For Polyhedral Surfaces. No-tices Amer.Math.Soc.,1960,7:646
[5]Heawood P J. Map-color Theorem. Quart. J. Pure. Appl. Math.,1890,24:332-338
[6]Gross J L, Tucker T W. Topological Graph Theory. New York:Wiley Inter-science,1987
[7]Robertson N, Zha X Y,Zhao Y. On The Flexibility of Toroidal Embeddings. J.Combin.Theory Ser.B,2008,98(1):43-61
[8]Gross J L, Furst M L. Hierarchy of Imbedding Distribution Invariants of Graph. J.Graph Theory,1987,11:205-220
[9]刘彦佩.组合地图进阶.北京：北京交通大学出版社,2003
[10]刘彦佩.图的代数原理.北京：高等教育出版社,2006
[11]Chen J, Gross J, Rieper R G. Overlap Matrices And Total Embeddings. Dis-crete Math,1994,128:73-94
[12]Kwak J H, Shim S H. Total Embedding Distributions for Bounquets of Circles. Discrete Math,2002,248:93-108
[13]Chen Y C, Liu Y P, Wang T. The Total Embedding Distributions of Cacti And Necklaces. Acta Mathematica Sinica,2006,22(5):1583-1590
[14]Li L F, Liu Y P. Genus Distribution of Embeddings for A Type of A 3-Regular Graph. J.Beijing Jiaotong Univ.,2004,28(6):39-42
[15]Liu Y P. Embeddability In Graphs. Dordrecht, Boston, London:Kluwer Aca-demic Publisher,1995
[16]Deng M, Ren H. Flexibility Of Embeddings Of Wheel Graphs On The Torus.华东师范大学学报(自然科学版),2006,1：57-62
[17]Gary Chartrand, Zhang P. Introduction To Graph Theory. Beijing:Posts and Telecom Press,2007
[18]Mohar B, Thomassen C. Graphs On Surfaces. Baltimore:The Johns Hopkins University Press,2001
[19]Furst M, Gross J, Statman R. Genus Distributions For Two Classes Of Graphs. J. Combin. Ser. B,1989,46:22-36
[20]Mansour T, Schork M. The Solution Of The Recurrence Relation fn(t)= an(t)fn-1(t)-bn(t)((?)/(?)t)fn-1(t), J.Diff. Eq. Appl.,2009 15(7):679-691
[21]余长安.两个参数的递推公式的解公式.武汉大学学报(自科版),1990,(1)：1-6
[22]余长安.一类系数依赖于双指标的非齐次递推式之解.应用数学学报,1997,20(2)：316-320
[23]余长安.一类带双指标常系数齐次递推关系的显示解.应用数学学报,1997,20(1)：119-127
[24]余长安.关于一类两个指标的齐次递推关系的解的结构.数学物理学报,2002,22A(1)：55-60
[25]Mansour T. Combinatorial Methods And Recurrence Relation With Two In-dices. J. Diff. Eq. Appl.,2006,12(6):555-563
[26]Mansour T. Recurrence Relations With Two Indices And Even Trees. J. Diff. Eq. Appl.,2007,13(1):47-61
[27]Mansour T, Song C W. Kernel Method And System Of Functional Equations, J. Compu. App. Math,22(4):133-139
[28]Andrews G E. The Theory of Partitions. Cambridge:Cambridge University Press,1984
[29]Stanley R P. Enumerative Combinatorics. Cambridge:Cambridge University Press, vol.1,second printing,1996
[30]Andrews G E, Askey R, Roy R. Special Functions. Cambridge:Cambridge University Press,2000
[31]Th. Rivlin. Chebyshev polynomials:From Approximation Theory To Algebra And Number Theory. New York:John Wiley,1990
[32]Chen Y C,T.Manour, Zou Q.On The Total Embedding Distribution for Four Types of Graphs. Submitted
[33]Archdeacon D. Calculations On The Average Genus And Genus Distribution Of Graphs.Congr. Numer.1988,67:114-124
[34]Gross J L, Robbins D P, Tucker T W. Genus Distributions for Bouquets of Circles. J.Combin.Theory Ser. B,1989,47:292-306
[35]Kwak J H, Lee J. Genus Polynomials of Dipoles. Kyungpook Math. Journal,1993,33:115-125
[36]Tesar E H. Genus Distributions for Ringel Ladders. Discrete Math. J.,2000,216(1):235-252
[37]Li D M. Genus Distribution of Circular Ladders. Northeast Math. J. 2000,16(2):181-189
[38]Li D M. Genus Distribution of Mobius Ladders. Northeast Math. J. 2005,21(1):70-80
[39]赵喜梅,刘彦佩.类树图的嵌入多项式.北京交通大学学报,2004,28(3)：7-11
[40]Yang Y, Hao R X. Classification of Embeddings of Fan Graph on Surfaces. Acta Math Appli Sinica.,2008,31(5):792-798
[41]Hao R X, Liu Y P. The Genus Distributions of Directed Antiladders in Ori-entable Surfaces. Appl.Math. Lett.,2008,21 (2):161-164
[42]Wan L X, On Orientable Embedding Genus Distribution of A Graph:[ Ph.D.Dissertation].Beijing:Beijing JiaoTong University,2006
[43]Wan L X, Liu Y P. Orientable Embedding Genus Distribution For Certain Types of Graphs. J. Comb. Theory, Ser. B,2008,98(1):19-32
[44]Jackson D.M. Counting Cycles in Permutations by Group Characters, with An Application to A Topological Prolbem. Trans.Amer.Math. Soc,1987,299:785-801
[45]Mohar B. An Obstuction To Embedding Graphs in Surfaces. Discrete Math, 1989,78:135-142
[46]Chen J, Gross J, R.G.Rieper. Lower Bounds for The Average Genus. J.Graph Theory,1995,19:281-296
[47]Chen Y C. Remarks On The Lower Bounds For The Average Genus. Manuscript
[48]Chen Y C, Liu Y P. A Tight Lower Bound for the Average Crosscap Num-ber.Submitted
[49]Coratet.L. Advanced combinatorics. Boston:Reidel Publication company,1974
[50]Stahl.S. On The Zeros Of Some Polynomial. Can. J. Math.,1996,49:617-640
[51]赵喜梅,刘彦佩.类树图亏格分布的单峰性.山西大学学报(自然科学版)2006,29(3)：242-244
[52]Stanley. R. P. Log-concave And Unimodal Sequences In Algebra. Combina-torics And Gometry, Ann. New York Acad.Sci.,1980,576:500-534
[53]Wang Y, Yeh.Y.N. Proof of A Conjecture On Unimodality. European J.Combin.2006,26:617-627
[54]Wang Y,Yeh.Y.N. Log-concavity and LC-positivity. J.Combin.Theory Ser.A. 2007,114:195-120
[55]Chen Y C,Liu Y P.On The Average Crosscap Number of A Graph.Manuscript.
[56]Yang Y, Liu Y P. Number of Embeddings of Wheel Graphs on Surfaces of Small Genus. Accepted by Ars Combin.