摘要
本文主要研究图在曲面上的2-胞腔嵌入与交叉数问题，讨论了广义置换图与广义Petersen图的最大亏格问题，确定了两类广义Petersen图的Euler亏格，利用循环图在环面上的2-胞腔嵌入给出了它的交叉数的上界，并且确定了几类循环图的交叉数，具体结果如下：
1．证明了如果一个广义置换图G(n,k)至多有两个奇长的次圈，那末它是上可嵌入的。
2．证明了当k→∞时，广义置换图G(n,k)最大亏格不小于[β(G(n,k))/3]+1的概率趋于1。
3．证明了广义Petersen图P(n,m)是上可嵌入的。
4．确定了广义Petersen图P(2m+1,m)(m≥3)的Euler亏格是1。
5．确定了广义Petersen图P(2m+2,m)(m＞4)的Euler亏格为2。
6．利用循环图在环面上的2-胞腔嵌入给出了它的交叉数的上界。
7．确定了循环图C(2m,m)(m≥3)，C(2m+1,m)，C(2m+2,m)(m≥3)的交叉数分别是1，1，m+1。
This paper mainly studies embeddings of graphs and their crossing numbers.
Chapter 1 is devoted to basic concepts of embeddings and crossing numbers of graphs.
In chapter 2, we prove the generalized permutation graph G(n, k) with no more than two subcycles whose length are odd number is upper embeddable, and show the probability that the maximum genus of G(n, k) is no less than tends to 1 when k - .
In chapter 3, we prove the generalized Peter sen graph P(n, m) is upper embeddable, and show that the Euler genus of P(2m + 1,m)(m > 3) is 1. Also, we show that the Euler genus of P(2m + 2,m)(m > 4) is 2.
Chapter 4 provides an upper bound for crossing number of circular graphs using their 2-cell embeddings in the torus. Simultaneously, crossing numbers of circular graphs C(2m, m)(m > 3), C(2m +1, m) and C(2m + 2, m)(m > 3) are determined as 1,1 and m + 1, respectively.
引文
[1] M.Ajtai, V.Chv(?)tal, M.Newborn, E. Szemer(?), Crossing-free subgraphs, Ann. Discrete Math. 12 (1982) 9-12.
[2] B.Alspach, The classification of Hamiltonian generalized Petersen graphs, J. Combin. Theory Series B 34, 293-312 (1983).
[3] D.Archdeacon, Topological graph theory: a survey, Congr.Numer 115 (1996) 5-54.
[4] D.Archdeacon, R.B. Richter, On the parity of crossing numbers, J. Graph Theory, vol. 12, No. 3, 307-310 (1988).
[5] K.Bannai, Hamiltonian cycles in generalized Petersen graphs, J. Combin. Theory Ser. B 24 (1978), 181-188.
[6] J. A. Bondy, U.S.Murty, Graph Theory with Application, The Macmillan Press Ltd, 1979.
[7] J. A. Bondy, Variations on the Hamiltonian Theme, J. Can. Math. Bull, 1972, 15, 57-62.
[8] L.W.Beineke, R.D.Ringeisen, On the crossing number of products of cycles and graphs of order four, J.Graph Theory, 4 (1980),145-155.
[9] F.Castagna, G.Prins, Every generalized Petersen graph has a Tait coloring, Pacific J.Math. 40 (1972), 53-58.
[10] J.Chen, D.Archdeacon, J.L.Gross, Maximum genus and connectivity, Discrete Mathematics 149(1996) 19-29.
[11] G.Exoo, F.Harary, J.Kabell, The crossing numbers of some generalized Petersen graphs, Math. Scand, 1981, 48, 184-188.
[12] S.Fiorini, On the crossing number of generalized Petersen graphs, Ann. Discrete Math.,1986 vol. 30, 225-242.
[13] M.R. Garey, D.S.Johnson, Crossing number is NP-complete, SIAM J.Alg. Disc. Math. 1(1983),312-316.
[14] J.L.Gross, T.W.Tucker, Topological Graph Theory, (Wiley-Intersciece, New York, 1987).
[15] R.Guy, The decline and fall of Zarankiewicz's theorem, Proof Techniques in Graph Theory (F.Harary Ed.), Academic Press, New York (1969) 63-69.
[16] F．哈拉里著(李慰萱译)，图论，上海科学技术出版社(1980)．
[17] F.Harary, P.C.Kainen, A.J.Schwenk, Toroidal graphs with arbitrarily high crossing number, Nant Math, 6 (1973), 58-67.
[18] Rongxia Hao, Yanpei Liu, New Upper Bounds On Crossing Number Of Circular Graph,运筹学报(1999)第3卷第3期：1-6．
[19] D.A.Holton, J.Sheehan, The Petersen Graph, Cambridge University Press 1993.
[20] Yuanqiu Huang, Yanpei Liu, The maximum genus of graphs with diameter three,Discrete Mathematics 194(1999) 139-149.
[21] D.J. Kleitman, The crossing number of K_(5,n), J. Combin. Theory 9 (1971), 315-323.
[22] S.Kundu, Bounds on the number of disjoint spanning trees, J. Combin. Theory Series B 17(1974)199-203.
[23] Tongyin Liu, Yanpei Liu, On the crossing number of circular graph, 运筹学报(1998)第2卷第4期：32～38
[24] B. Mohar, C. Thomassen, Graphs on surfaces, Johns Hopkins University Press, 2001.
[25] L.Nebesk(?), A new characterization of the maximum genus of a graph, Czechoslovak Math. J. 31(1981) 604-613.
[26] S.Negami, Crossing number of gragph embedding pairs on closed surfaces, Graph theory (2001) Vol.36: 8-23.
[27] R.B.Richter, G.Salazar, The crossing number of P(N,3), Graphs and Combinatorics, 2002, 18,381-394.
[28] R.B.Richter, G.Salazar, The crossing number of C_6×C_n, Austral. J. Combin. 23 (2001) 135-144.
[29] R.D.Ringeisen, L.W.Beineke, The crossing number of C_3×C_n, J. Combin. Theory,24 (1978),134-136.
[30] F.Shahrokhi, O.S(?)kora, L.A.Sz(?)kely, I. Vrto, Crossing number : bounds and applications, Intuitive Geometry, Bolyai Society Mathematical Studies,vol.6, J(?)nos Bolyai Mathematical Society, Budapest,1997,pp. 179-206.
[31] 田丰，马仲蕃，图与网络流理论，科学出版社(1987)．
[32] M.E.Watkins, A theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combin. theory 6 (1969), 152-164.
[33] N.H.Xuong, How to determine the maximum genus of a graph, J.Combin. Theory B 26, (1979) 217-225.
[34] N.H.Xuong, Upper embeddable graph and related topics, J.Combin. Theory B 26, (1979) 226-232.