特殊图G与路与圈以及与孤立点的联图的交叉数
|
摘要
图的交叉数问题起源于二战时期Pual Turán在砖厂碰到的一个实际问题,后来逐渐发展成为图论学科中非常活跃的一个分支,吸引着大批国内外学者的关注和研究,其理论在电路板设计,草图识别与重画以及生物DNA的图示等领域有广泛的应用.但是,k确定一般图类的交叉数问题已经被证明是一个NP-完全问题.因此,至今为止有关图的交叉数问题的结果还非常少,且己被确定交叉数的图类大多数都是一些比较特殊的图类,故很多方法都不能推广到一般情况.甚至有的时候找出图的交叉数的一个比较好的上界或下界也很困难.本文运用归纳法的思想以及反正法确定了两个特殊图类的交叉数：一个六阶图H与路Pn的联图的交叉数以及一个四阶不连通图G与路,圈联图的交叉数本文一共由五个章节组成.
第一章主要介绍了交叉数的起源,交叉数研究的理论与实际意义,目前关于交叉数的一些研究现状,同时本章节还简要的介绍了本文主要结构.
第二章介绍了阅读本文时所必须的一些关于交叉数方面的基本概念以及一些重要结果.
第三章,本章节主要得到关于图H与n个孤立点nK1的联图的交叉数,以及此图与路Pn的联图的交叉数及与圈的联图的交叉数的上下界.
第四章,本章主要介绍一个四阶不连通图G与路,圈的联图的交叉数.
第五章,给出本文的总结.
The research on crossing numbers of graphs is originated in World War Ⅱ, when Pual Turan encountered a practical problem in a brick factory. It gradually developed into a very active branch of the disciplines of graph theory, attracting a large number of scholars'attention domestic and overseas. Besides, its theory has a wide range of applications in circuit board design, sketch recog-nition and redraw, and the graphic representations of the biological DNA, etc. However, to determine the crossing numbers of general classes of graphs have proven to be a NP-complete problem. Therefore, achievements on the crossing numbers of graphs are very few so far, and most of the graphs which crossing numbers are identified are special classes of graphs, therefore a lot of methods cannot be applied to the general classes of graphs, and what's more, sometimes it is very difficult to find a proper upper or lower boundary of the crossing num-bers of graphs. By using inductive method and reduction-to-absurdity method, this paper determines the crossing numbers of two special classes of graphs:The crossing number of join the special of H with six vertices path and cycle,and not connected graph of G with four vertices path and cycle.
This paper consists of five parts:
The first chapter mainly introduces the origin of the crossing numbers, theoretical and practical significance of researches on the crossing numbers of graphs, and current status of researches on it. Moreover, the main structure of this paper is briefly described.
The second chapter discusses some basic concepts and important achieve-ments of the crossing numbers, which are required in reading this thesis.
The third chapter illustrates the crossing number of join the special of H with six vertices path and upper or lower boundary of cycle.
The fourth chapter introduces the crossing numbers of not connected graph of G with four vertices path and cycle.
The last chapter is the conclusion part.
第一章主要介绍了交叉数的起源,交叉数研究的理论与实际意义,目前关于交叉数的一些研究现状,同时本章节还简要的介绍了本文主要结构.
第二章介绍了阅读本文时所必须的一些关于交叉数方面的基本概念以及一些重要结果.
第三章,本章节主要得到关于图H与n个孤立点nK1的联图的交叉数,以及此图与路Pn的联图的交叉数及与圈的联图的交叉数的上下界.
第四章,本章主要介绍一个四阶不连通图G与路,圈的联图的交叉数.
第五章,给出本文的总结.
The research on crossing numbers of graphs is originated in World War Ⅱ, when Pual Turan encountered a practical problem in a brick factory. It gradually developed into a very active branch of the disciplines of graph theory, attracting a large number of scholars'attention domestic and overseas. Besides, its theory has a wide range of applications in circuit board design, sketch recog-nition and redraw, and the graphic representations of the biological DNA, etc. However, to determine the crossing numbers of general classes of graphs have proven to be a NP-complete problem. Therefore, achievements on the crossing numbers of graphs are very few so far, and most of the graphs which crossing numbers are identified are special classes of graphs, therefore a lot of methods cannot be applied to the general classes of graphs, and what's more, sometimes it is very difficult to find a proper upper or lower boundary of the crossing num-bers of graphs. By using inductive method and reduction-to-absurdity method, this paper determines the crossing numbers of two special classes of graphs:The crossing number of join the special of H with six vertices path and cycle,and not connected graph of G with four vertices path and cycle.
This paper consists of five parts:
The first chapter mainly introduces the origin of the crossing numbers, theoretical and practical significance of researches on the crossing numbers of graphs, and current status of researches on it. Moreover, the main structure of this paper is briefly described.
The second chapter discusses some basic concepts and important achieve-ments of the crossing numbers, which are required in reading this thesis.
The third chapter illustrates the crossing number of join the special of H with six vertices path and upper or lower boundary of cycle.
The fourth chapter introduces the crossing numbers of not connected graph of G with four vertices path and cycle.
The last chapter is the conclusion part.
引文
[1]Adamsson, J. and R. B. Richter, Arrangements, circular arrangements, and the crossing number of C7 x Cn[J], J. Combin. Theory Scr. B,90 (2004),21-39.
[2]Ajtai, M., V. Chvdtal, M. Newborn, E. Szemeredi, Crossing-free subgraphs, in: Theory and Practice of Combinatorics, in:North-Holland and Math. Stud.[J], vol.60, Elsevier, Amsterdam,1982,9-12.
[3]Anderson, M. S., R. B. Richter, P. Rodney, Crossing number of C6×C6[J], Congressus Numerantium,118 (1996),97-107.
[4]Anderson, M. S., R. B. Richter, P. Rodney, The crossing number of C6×C6[J], Cong Numer.,125 (1997),97-117.
[5]Asano, K., The crossing number of K1,3,n andK2,3,n[J], J.Graph Theory,10 (1986),1-8.
[6]Bhatt, S. N. and F. T. Leighton, A framework for solving VLSI graph layout problems[J], J. Comput. System Sci.,28 (1984),300-343.
[7]Bokal, D., On the crossing numbers of Cartesian products with paths[J], J. Combin. Theory Ser B.,97 (2007),381-384.
[8]Bokal, D., On the crossing numbers of Cartesian products with trees [J], J. Graph Theory,56 (2007),287-300.
[9]Brodsky, A., Stephane Durocher, Ellen Gethner, Toward the rectilinear cross-ing number of Kn:new drawings, upper bounds, and asymptotics[J], Discrete Mathematics,262 (2003),59-77.
[10]Cimikowski, R., Topological properties of some interconnection network graphs [J], Proc.27th. Southeastern Intl. Conf. Comb. Graph Theory and Computing (Baton Rouge, LA,1996). Congr. Numerantium,121 (1996),19-32.
[11]Cimikowski, R., Crossing number bounds for the mesh of trees[J], Proc.29th. Southeastern Intl. Conf. Comb. Graph Theory and Computing (Baton Rouge, LA,1998). Congr. Numcrantium,134 (1998),107-116.
[12]Dean, A. M. and R. B. Richter, The crossing number of C4×C4[J], J. Graph Theory,19 (1995),125-129.
[13]Eggleton, R. B. and R. P. Guy, The crossing number of the n-cube[J], Amer. Math. Soc. Notices,17 (1970),757.
[14]Erdos, P. and R. K. Guy, Crossing number problems [J], Am. Math. Month.,80 (1973),52-58.
[15]Faria, L., C. M. H. de Figueiredo, On Eggleton and Guy conjectured upper bound for the crossing number of the n-cube[J], Mathematica Slovaca,50 (2000),271-287.
[16]Fiorini, S., On the crossing number of generalized Petersen graphs[J], Ann. Dis-rete Math.,30 (1986),221-242.
[17]Garary, M. R. and D. S. Johnson, Crossing number is NP-complcte[J], SIAM J. Algebric Discrete Methods,4 (1993),312-316.
[18]Glebsky, L. Y. and G. Salazar, The crossing number of Cm×Cn is as conjectured for n≥m(m+1)[J], J.Graph Theory,47 (2004),53-72.
[19]Guy, R. K., The decline and fall of Zarankiewicz's theorem in Proof Techniques in Graph Theory [J], Academic Press, New York,1969,63-69.
[20]Guy, R. K., Crossing numbers of graphs [J], In Graph Theory and Applications, Lecture Notes in Mathematics, vol.303, Spring-Verlag, Heidelberg, Berlin, New York, May 1972,111-124.
[21]Guy, R. K. and T. A. Jenkyns, The toroidal crossing number of Km,n[J], J. Combin. Theory,6 (1969),235-250.
[22]Hao, R. and Y. Liu, New upper bounds on crossing number of circular graphs [J], OR Transactions,3 (1999),1-6.
[23]Harary, F., P.C.Kainen, A.J.Schwenk, Toroidal graphs with arbitrarily high crossing numbers[J], Nana Math.,6 (1973),58-67.
[24]Harary, F., Graph Theory[M], Addision-Wesley, Reading, MA,1969.
[25]Harborth, H., Uber die Kreuzungszahl vollstandiger, n-geteilter Graphen[J], Math. Nachr.,48 (1971),179-188.
[26]何小年,关于图的交叉数研究[D],硕士学位论文,湖南师范大学,(2006).
[27]何小年,黄元秋,一类笛卡尔积图的交叉数[J],吉首大学学报(自然科学版),26(1)(2005),8-11.
[28]Ho, P. T., The crossing number of K1,m,n[J], Discrete Mathematics,308 (2008), 5996-6002.
[29]Ho, P. T., The crossing number of some complete multipartite graphs [J], Util. Math., (in press).
[30]Ho, P. T., The crossing number of K4,n on the real projective plane [J], Discrete Mathematics.304 (2005),23-33.
[31]Ho, P. T., The toroidal crossing number of K4,n[J], Discrete Mathematics, (2008), doi:10.1016/j.disc.2008.09.029.
[32]Huang, Y. and T. Zhao, The crossing number of K1,4,n[J],Discrete Mathematics, 308 (2008),1634-1638.
[33]黄元秋,赵霆雷,关于完全3-部图K1,6,n的交叉数[J],应用数学学报,29(6)(2006),1046-1053.
[34]Huang, Y. and T. Zhao, On the crossing number of the complete tripartite graph K1,8,n[J], Acta Mathematica Scientia,26A (7) (2006),1115-1122.
[35]Huang, Y., and T. Zhao, The crossing number of the line graphs[J], Submitted.
[36]Jendrol',S. and M. Scerbova, On the crossing numbers of Sm×Pn and Sm× Cn[J], Cas. Pest. Mat.,107 (1982),225-230.
[37]Jozef Siran, Infinite families of crossing-critical graphs with a given crossing number[J], Discrete Mathematics,48 (1984),129-132.
[38]Juarez, H. A. and G. Salazar, Drawings of Cm×Cn with one disjoint family Ⅱ[J], Journal of Combinatorial Theory, Series B,82 (2001),161-165.
[39]Kleitman, D. J., The crossing number of K5,n[J], J.Comb.Theory,9 (1970),315-323.
[40]Kleitman, D. J., A note on the parity of the number of crossings of a graph[J], J. Combinatorial Theory, Series B,21 (1976),88-89.
[41]Klerk, E. D., J. Maharry, D. V. Pasechnik, R. Bruce Richter, G. Salazar, Im-proved bounds for the crossing numbers of Kmn and.Kn[J], SIAM Discrete Math.,20 (1) (2006),189-202.
[42]Klerk, E. D., D. V. Pasechnik, A. Schrijver, Reduction of symmetric semidifinite programs using the regular*-representation[J], Math Prograph,109 (2007), no. 2-3, Ser. B.613-624.
[43]Klesc, M., The crossing numbers of certain Cartesian products[J], Discuss. Math.-Graph Theory,15 (1995),5-10.
[44]Klesc, M., The crossing number of Cartesian products of paths with 5-vertex graphs[J], Discrete Math.,233 (2001),353-359.
[45]Klesc, M., On the crossing numbers of Cartesian products of stars and paths or cycles [J], Math. Slovaca,41 (1991),113-120.
[46]Klesc, M. and A. Kocurova, The crossing numbers of products of 5-vertex graphs with cycles [J], Discrete Math.,307 (2007),1395-1403.
[47]Klesc, M., The join of graphs and crossing number,Eletronic Notes in Discrete Mathematics,28(2007),349-355.
[48]Leighton, F. T., New lower bound techniques for VLSI[J], Math. System Theory, 17 (1984),47-70.
[49]Liu, T. and Y. Liu, On the crossing number of circular graphs[J], OR Transac-tions,4 (1998),31-38.
[50]Lovrecic Sarazin, M., The crossing number of the generalized Petersen graph P(10,4) is four[J], Math. Slovaca,47 (2) (1997),189-192.
[51]Ma, D., H. Ren, J. Lu, The crossing number of the circular graph C(2m+2,m)[J], Discrete Mathematics,304 (2005),88-93.
[52]马登举,任韩,卢俊杰,广义Petersen图G(2m+1,m)的交叉数[J],华东师范大学学报,1(2005),34-39.
[53]Martin Kochol, Construcion of crossing-critical graphs[J], Discrete Mathematics, 66 (1987),311-313.
[54]Montaron, B., An improvement of the crossing number bound [J], J Graph The-ory,50 (2005),43-54.
[55]Oporowski, B. and David Zhao, Coloring graphs with crossings [J], Discrete Mathematics, (2008), doi:10.1016/j.disc.2008.07.040.
[56]欧阳章东,关于图的交叉数问题研究[D],博士学位论文,湖南师范大学(2011).
[57]Pach, J., R. Radoicic, G. Tardos, G. Toth, Improving the Crossing Lemma by finding more crossings in sparse graphs[J], Discrete Comput. Geom.,36 (2006), 527-552.
[58]Pelsmajer, M. J., Marcus Schaefer, Daniel Sefankovic, Odd crossing number and crossing number are not the same[J], Discrete Comput. Geom.,39 (2008), 442-454.
[59]Peng, Y. H. and Y. C. Yiew, The crossing number of P(3,1)×Pn[J], Discrete Math.,306 (2006),1941-1946.
[60]Richter, R. B. and C. Thomassen, Minimal graphs with crossing number at least k, Journal of Combinatorial Theory [J], Series B,58 (1993),217-224.
[61]Richter, R. B. and C. Thomassen, Relations between crossing numbers of com-plete and complete bipartite graphs[J], The American Mathematical Monthly, 104(2) (1997),137-137.
[62]Richter, R. B. and C. Thomassen, Intersection of curve systems and the crossing number of C5×C5[J], Discrete and Computational Geometry,13 (1995),149-159.
[63]Richter, R. B. and G. Salazar, The crossing number of C6×Cn[J], Australas. J. Combin.,23 (2001),135-143.
[64]Richter, R. B. and G. Salazar, The crossing number of P(N,3)[J], Graphs and Combinatorics,18 (2002),381-394.
[65]Riskin, A., On the nonembeddability and crossing numbers of some Kleinical polyhedral maps on the torus [J], Graphs and Combinatorics,21 (2005),131-135.
[66]Salazar, G., On the crossing number of Cm×Cn.[J], J. Graph Theory,28 (1998), 163-170.
[67]Salazar, G., A lower bound for the crossing number of Cm×Cn[J], J Graph Theory,35 (2000),222-226.
[68]Salazar, G., Drawings of Cm×Cn with one disjoint family[J], Journal of Com-binatorial Theory, Series B,76 (1999),129-135.
[69]Salazar, G., Infinite families of crossing-critical graphs with given average degree, Discrete Mathematics[J],271 (2003),343-350.
[70]Shahrokhi, F., O. Sykora, L. A. Szekely, I. Vrto, Intersection of curves and crossing number of Cm×Cn on surfaces[J], Discrete Comput Geom.,19 (2) (1998),237-247.
[71]Shengjun, P. and R. Bruce Richter, The crossing number of K11 is 100[J], J. Graph Theory,56 (2007),128-134.
[72]Sykora, O. and I. Vrt'o, On the crossing number of the hypercube and cube connected cycles [J], BIT,33 (1993),232-237.
[73]Szekely, L. A., A successful concept for measuring non-planarity of graphs:The crossing number [J], Discrete Math.,276 (2004),331-352.
[74]Tang, L., J. Wang, Y. Huang, The crossing number of the join of Cm and Pn[J], International J. Math. Com.,1 (2007),110-116.
[75]Turdn, P., A note of welcome[J], J.Graph Theory,1 (1977),7-9.
[76]Tutte, W. T., Toward a theory of crossing numbers[J], J.Combinatorial Theory, 8 (1970),45-53.
[77]王晶,黄元秋,完全3-部图K1,10,n的交叉数[J],高校应用数学学报,23(3)(2008),349-356.
[78]王晶,关于一些图类的交叉数[D],硕士学位论文,湖南师范大学,(2006).
[79]王晶,黄元秋,K2,4×Rn的交叉数[J],数学物理学报,28A(2008),251-255.
[80]Wang, J. and Y. Huang, The crossing number of the Cartesian products of paths with some 6-vertex graphs [J],吉首大学学报(自然科学版),26(2)(2005),9-13.
[81]Woodall, D. R., Cyclic-order graphs and Zarankiewicz's crossing number con-jecture [J], J. Graph Theory,17 (1993),657-671.
[82]肖文兵,黄元秋,一类笛卡尔积图的交叉数[J],湖南师范大学学报(自然科学版),4(2004),3-7.
[83]Yang, Y., X. Lin, J. Lu, X. Hao, The crossing number of C(n;{1,3})[J], Discrete Math.,289 (2004),107-118.
[84]于平,黄元秋,Pm与Wn的笛卡尔积图的交叉数[J],湖南师范大学学报(自然科学版),1(2005)),14-16.
[85]袁梓瀚,黄元秋,刘金旺,7阶图C(7,2)与Pn的笛卡尔积的交叉数[J]数学进展,37(2)(2008)),245-253.
[86]郑敦勇,图的交叉数的研究[D],硕士学位论文,湖南师范大学,(2011).
[2]Ajtai, M., V. Chvdtal, M. Newborn, E. Szemeredi, Crossing-free subgraphs, in: Theory and Practice of Combinatorics, in:North-Holland and Math. Stud.[J], vol.60, Elsevier, Amsterdam,1982,9-12.
[3]Anderson, M. S., R. B. Richter, P. Rodney, Crossing number of C6×C6[J], Congressus Numerantium,118 (1996),97-107.
[4]Anderson, M. S., R. B. Richter, P. Rodney, The crossing number of C6×C6[J], Cong Numer.,125 (1997),97-117.
[5]Asano, K., The crossing number of K1,3,n andK2,3,n[J], J.Graph Theory,10 (1986),1-8.
[6]Bhatt, S. N. and F. T. Leighton, A framework for solving VLSI graph layout problems[J], J. Comput. System Sci.,28 (1984),300-343.
[7]Bokal, D., On the crossing numbers of Cartesian products with paths[J], J. Combin. Theory Ser B.,97 (2007),381-384.
[8]Bokal, D., On the crossing numbers of Cartesian products with trees [J], J. Graph Theory,56 (2007),287-300.
[9]Brodsky, A., Stephane Durocher, Ellen Gethner, Toward the rectilinear cross-ing number of Kn:new drawings, upper bounds, and asymptotics[J], Discrete Mathematics,262 (2003),59-77.
[10]Cimikowski, R., Topological properties of some interconnection network graphs [J], Proc.27th. Southeastern Intl. Conf. Comb. Graph Theory and Computing (Baton Rouge, LA,1996). Congr. Numerantium,121 (1996),19-32.
[11]Cimikowski, R., Crossing number bounds for the mesh of trees[J], Proc.29th. Southeastern Intl. Conf. Comb. Graph Theory and Computing (Baton Rouge, LA,1998). Congr. Numcrantium,134 (1998),107-116.
[12]Dean, A. M. and R. B. Richter, The crossing number of C4×C4[J], J. Graph Theory,19 (1995),125-129.
[13]Eggleton, R. B. and R. P. Guy, The crossing number of the n-cube[J], Amer. Math. Soc. Notices,17 (1970),757.
[14]Erdos, P. and R. K. Guy, Crossing number problems [J], Am. Math. Month.,80 (1973),52-58.
[15]Faria, L., C. M. H. de Figueiredo, On Eggleton and Guy conjectured upper bound for the crossing number of the n-cube[J], Mathematica Slovaca,50 (2000),271-287.
[16]Fiorini, S., On the crossing number of generalized Petersen graphs[J], Ann. Dis-rete Math.,30 (1986),221-242.
[17]Garary, M. R. and D. S. Johnson, Crossing number is NP-complcte[J], SIAM J. Algebric Discrete Methods,4 (1993),312-316.
[18]Glebsky, L. Y. and G. Salazar, The crossing number of Cm×Cn is as conjectured for n≥m(m+1)[J], J.Graph Theory,47 (2004),53-72.
[19]Guy, R. K., The decline and fall of Zarankiewicz's theorem in Proof Techniques in Graph Theory [J], Academic Press, New York,1969,63-69.
[20]Guy, R. K., Crossing numbers of graphs [J], In Graph Theory and Applications, Lecture Notes in Mathematics, vol.303, Spring-Verlag, Heidelberg, Berlin, New York, May 1972,111-124.
[21]Guy, R. K. and T. A. Jenkyns, The toroidal crossing number of Km,n[J], J. Combin. Theory,6 (1969),235-250.
[22]Hao, R. and Y. Liu, New upper bounds on crossing number of circular graphs [J], OR Transactions,3 (1999),1-6.
[23]Harary, F., P.C.Kainen, A.J.Schwenk, Toroidal graphs with arbitrarily high crossing numbers[J], Nana Math.,6 (1973),58-67.
[24]Harary, F., Graph Theory[M], Addision-Wesley, Reading, MA,1969.
[25]Harborth, H., Uber die Kreuzungszahl vollstandiger, n-geteilter Graphen[J], Math. Nachr.,48 (1971),179-188.
[26]何小年,关于图的交叉数研究[D],硕士学位论文,湖南师范大学,(2006).
[27]何小年,黄元秋,一类笛卡尔积图的交叉数[J],吉首大学学报(自然科学版),26(1)(2005),8-11.
[28]Ho, P. T., The crossing number of K1,m,n[J], Discrete Mathematics,308 (2008), 5996-6002.
[29]Ho, P. T., The crossing number of some complete multipartite graphs [J], Util. Math., (in press).
[30]Ho, P. T., The crossing number of K4,n on the real projective plane [J], Discrete Mathematics.304 (2005),23-33.
[31]Ho, P. T., The toroidal crossing number of K4,n[J], Discrete Mathematics, (2008), doi:10.1016/j.disc.2008.09.029.
[32]Huang, Y. and T. Zhao, The crossing number of K1,4,n[J],Discrete Mathematics, 308 (2008),1634-1638.
[33]黄元秋,赵霆雷,关于完全3-部图K1,6,n的交叉数[J],应用数学学报,29(6)(2006),1046-1053.
[34]Huang, Y. and T. Zhao, On the crossing number of the complete tripartite graph K1,8,n[J], Acta Mathematica Scientia,26A (7) (2006),1115-1122.
[35]Huang, Y., and T. Zhao, The crossing number of the line graphs[J], Submitted.
[36]Jendrol',S. and M. Scerbova, On the crossing numbers of Sm×Pn and Sm× Cn[J], Cas. Pest. Mat.,107 (1982),225-230.
[37]Jozef Siran, Infinite families of crossing-critical graphs with a given crossing number[J], Discrete Mathematics,48 (1984),129-132.
[38]Juarez, H. A. and G. Salazar, Drawings of Cm×Cn with one disjoint family Ⅱ[J], Journal of Combinatorial Theory, Series B,82 (2001),161-165.
[39]Kleitman, D. J., The crossing number of K5,n[J], J.Comb.Theory,9 (1970),315-323.
[40]Kleitman, D. J., A note on the parity of the number of crossings of a graph[J], J. Combinatorial Theory, Series B,21 (1976),88-89.
[41]Klerk, E. D., J. Maharry, D. V. Pasechnik, R. Bruce Richter, G. Salazar, Im-proved bounds for the crossing numbers of Kmn and.Kn[J], SIAM Discrete Math.,20 (1) (2006),189-202.
[42]Klerk, E. D., D. V. Pasechnik, A. Schrijver, Reduction of symmetric semidifinite programs using the regular*-representation[J], Math Prograph,109 (2007), no. 2-3, Ser. B.613-624.
[43]Klesc, M., The crossing numbers of certain Cartesian products[J], Discuss. Math.-Graph Theory,15 (1995),5-10.
[44]Klesc, M., The crossing number of Cartesian products of paths with 5-vertex graphs[J], Discrete Math.,233 (2001),353-359.
[45]Klesc, M., On the crossing numbers of Cartesian products of stars and paths or cycles [J], Math. Slovaca,41 (1991),113-120.
[46]Klesc, M. and A. Kocurova, The crossing numbers of products of 5-vertex graphs with cycles [J], Discrete Math.,307 (2007),1395-1403.
[47]Klesc, M., The join of graphs and crossing number,Eletronic Notes in Discrete Mathematics,28(2007),349-355.
[48]Leighton, F. T., New lower bound techniques for VLSI[J], Math. System Theory, 17 (1984),47-70.
[49]Liu, T. and Y. Liu, On the crossing number of circular graphs[J], OR Transac-tions,4 (1998),31-38.
[50]Lovrecic Sarazin, M., The crossing number of the generalized Petersen graph P(10,4) is four[J], Math. Slovaca,47 (2) (1997),189-192.
[51]Ma, D., H. Ren, J. Lu, The crossing number of the circular graph C(2m+2,m)[J], Discrete Mathematics,304 (2005),88-93.
[52]马登举,任韩,卢俊杰,广义Petersen图G(2m+1,m)的交叉数[J],华东师范大学学报,1(2005),34-39.
[53]Martin Kochol, Construcion of crossing-critical graphs[J], Discrete Mathematics, 66 (1987),311-313.
[54]Montaron, B., An improvement of the crossing number bound [J], J Graph The-ory,50 (2005),43-54.
[55]Oporowski, B. and David Zhao, Coloring graphs with crossings [J], Discrete Mathematics, (2008), doi:10.1016/j.disc.2008.07.040.
[56]欧阳章东,关于图的交叉数问题研究[D],博士学位论文,湖南师范大学(2011).
[57]Pach, J., R. Radoicic, G. Tardos, G. Toth, Improving the Crossing Lemma by finding more crossings in sparse graphs[J], Discrete Comput. Geom.,36 (2006), 527-552.
[58]Pelsmajer, M. J., Marcus Schaefer, Daniel Sefankovic, Odd crossing number and crossing number are not the same[J], Discrete Comput. Geom.,39 (2008), 442-454.
[59]Peng, Y. H. and Y. C. Yiew, The crossing number of P(3,1)×Pn[J], Discrete Math.,306 (2006),1941-1946.
[60]Richter, R. B. and C. Thomassen, Minimal graphs with crossing number at least k, Journal of Combinatorial Theory [J], Series B,58 (1993),217-224.
[61]Richter, R. B. and C. Thomassen, Relations between crossing numbers of com-plete and complete bipartite graphs[J], The American Mathematical Monthly, 104(2) (1997),137-137.
[62]Richter, R. B. and C. Thomassen, Intersection of curve systems and the crossing number of C5×C5[J], Discrete and Computational Geometry,13 (1995),149-159.
[63]Richter, R. B. and G. Salazar, The crossing number of C6×Cn[J], Australas. J. Combin.,23 (2001),135-143.
[64]Richter, R. B. and G. Salazar, The crossing number of P(N,3)[J], Graphs and Combinatorics,18 (2002),381-394.
[65]Riskin, A., On the nonembeddability and crossing numbers of some Kleinical polyhedral maps on the torus [J], Graphs and Combinatorics,21 (2005),131-135.
[66]Salazar, G., On the crossing number of Cm×Cn.[J], J. Graph Theory,28 (1998), 163-170.
[67]Salazar, G., A lower bound for the crossing number of Cm×Cn[J], J Graph Theory,35 (2000),222-226.
[68]Salazar, G., Drawings of Cm×Cn with one disjoint family[J], Journal of Com-binatorial Theory, Series B,76 (1999),129-135.
[69]Salazar, G., Infinite families of crossing-critical graphs with given average degree, Discrete Mathematics[J],271 (2003),343-350.
[70]Shahrokhi, F., O. Sykora, L. A. Szekely, I. Vrto, Intersection of curves and crossing number of Cm×Cn on surfaces[J], Discrete Comput Geom.,19 (2) (1998),237-247.
[71]Shengjun, P. and R. Bruce Richter, The crossing number of K11 is 100[J], J. Graph Theory,56 (2007),128-134.
[72]Sykora, O. and I. Vrt'o, On the crossing number of the hypercube and cube connected cycles [J], BIT,33 (1993),232-237.
[73]Szekely, L. A., A successful concept for measuring non-planarity of graphs:The crossing number [J], Discrete Math.,276 (2004),331-352.
[74]Tang, L., J. Wang, Y. Huang, The crossing number of the join of Cm and Pn[J], International J. Math. Com.,1 (2007),110-116.
[75]Turdn, P., A note of welcome[J], J.Graph Theory,1 (1977),7-9.
[76]Tutte, W. T., Toward a theory of crossing numbers[J], J.Combinatorial Theory, 8 (1970),45-53.
[77]王晶,黄元秋,完全3-部图K1,10,n的交叉数[J],高校应用数学学报,23(3)(2008),349-356.
[78]王晶,关于一些图类的交叉数[D],硕士学位论文,湖南师范大学,(2006).
[79]王晶,黄元秋,K2,4×Rn的交叉数[J],数学物理学报,28A(2008),251-255.
[80]Wang, J. and Y. Huang, The crossing number of the Cartesian products of paths with some 6-vertex graphs [J],吉首大学学报(自然科学版),26(2)(2005),9-13.
[81]Woodall, D. R., Cyclic-order graphs and Zarankiewicz's crossing number con-jecture [J], J. Graph Theory,17 (1993),657-671.
[82]肖文兵,黄元秋,一类笛卡尔积图的交叉数[J],湖南师范大学学报(自然科学版),4(2004),3-7.
[83]Yang, Y., X. Lin, J. Lu, X. Hao, The crossing number of C(n;{1,3})[J], Discrete Math.,289 (2004),107-118.
[84]于平,黄元秋,Pm与Wn的笛卡尔积图的交叉数[J],湖南师范大学学报(自然科学版),1(2005)),14-16.
[85]袁梓瀚,黄元秋,刘金旺,7阶图C(7,2)与Pn的笛卡尔积的交叉数[J]数学进展,37(2)(2008)),245-253.
[86]郑敦勇,图的交叉数的研究[D],硕士学位论文,湖南师范大学,(2011).