摘要
图的交叉数问题是在近代图论中发展起来的一个重要概念,是表征一个图的非平面性的一个重要参数.是拓扑图论中的前沿难题.它起源于上世纪五十年代Turan在砖厂碰到的一个实际应用问题(Tu-rairs Brickyard Problem).逐渐发展成为图论学科中非常活跃的一个分支.其理论在电路板设计.草图识别与重画以及生物工程DNA的图示等领域有广阔的应用.因而吸引着国内外许多学者的关注.它研究的主要是如何把一个图画在平面上或曲面上.使其产生的交叉数目最少.通常采用的是纯数学方法的证明.一般地，确定图的交叉数是十分困难的.事实上.Garey和Johnson已经证明了确定一般图的交叉数是一个NP-完全问题.目前.能确定交叉数的图类很少.确定图类的交叉数主要集中在一些特殊图类上,如完全图Kn,完全2-部图Km,n完全3-部图Kl,m,n,简单的图之间的笛卡尔积,循环图等.本文尝试应用并创新某些新的方法.主要研究了如广义Petersen图.联图.笛卡尔积图等
一些典型图类的交叉数.其主要结构如下：
一.交代了图的交叉数的起源、研究背景、研究工作的理论与实际意义.以及较为详细介绍目前交叉数的研究在国内外的发展动态.
二.给出了图的基本概念及本文常要用到的引理和性质.
三.研究了与联图有关的图的交叉数.主要研究了一个典型有两条悬挂边的六阶图与路和圈的联图的交叉数.
四.证明了一个特殊六阶图与路和圈的联图的交叉数..
五.探讨了与轮图有关的交叉数问题,在假定著名的Zarankiewicz猜想对m=7的情形成立的基础上,确定了6-轮W6与路Pn的联图的交叉数和6-轮W6与星图Sn的笛卡尔积图的交叉数.
六.讨论了一类Petensen图的交叉数.主要确定了当k≥3时.广义Petensen图P[3k-1，k]交叉数的上界和下界.七.给出了本文的总结和对未来工作的展望.
The crossing number of graphs is a vital concept in modern graph theory and a characterization of a graph of non-plane of an important parameter. It is difficulty in the forefront, of topological graph theory. The crossing number of graphs comes from the Pual Turdn's brick factory problem during in the fifties of the J9th century, and it becomes a very active branch in Graph Theory, whose theory has widespread applications in many fields, such as the design of electronic circuits, and the identification and repaint of sketch, and the graphical representation of DMA in biology engineer and so on. Many authors at home and aborad have engaged in the investigation on this area. It mainly studied how to take a. graph in the plane or curved surface, to make its crossing number at least, usually used the pure mathematical method to proof it. Generally, it is difficultly to determine the crossing number of graph. In fact. Garev and Johnson have proved that in general the problem of determining the crossing number of a graphs is NP-complete.At present. the classes of graphs whose crossing number have been determined are very scarce, and there are only some special graphs whose crossing numbers are known. For example, these included the complete graph Kn. the complete bipartite graph Km,n. the complete tripartite graph Kl.m.n, Some Cartesian product between some simply graphs, certain Petersen graph and so on. In this paper, we study the crossing number of some special graphs, such as the generalized Petersen graph, the join product, the Cartesian product, etc,with some new methods. The details are as follows:
One. We introduce the origins and backgrounds of the crossing number. its theorical and practical meanings, its development around the world.
Two. Introduce some basic concepts as well as some lemma and proper-ties,which associated with the graph.
Three. Focusing on the crossing number of join product, determines that the crossing number of the join product of a typical six vertices graphs with two hangs edges with Path and Cycle.
Four. Proof the crossing number of the join product of a special graphs with six vertices with Path and Cycle.
Five. Studies the crossing number of the Wheel, determines the crossing numbers of wheel-W3join with path Pn and Cartesian products of wheel-W6with Sn.provided that Zarankiewiez's conjecture holds for the ease m-7.
Six. Studies the crossing number of a type of Petensen graph. determined the upper and lower bounds of the generalized Petersen graph P (3k1k) for arbitrary k>3.
Seven. We make some conclusions of our research work and put forward one relative problems which we will go ahead.
引文
[1]Turdn, P., A note of welcome [J],J.Graph Theory, 1 (1977), 7-9.
[2]Bhatt, S. N. and F. T. Leighton, A framework for solving VLSI graph layout problems [J].,J. Comput. System Sci., 28 (1984), 300-343.
[3]Cimikowski, R., Topological properties of some interconnection network graphs [J]. Proc. 27th. Southeastern Intl. Conf. Comb. Giaph Theory and Computing (Bacon Rouge, LA, 1996). Congr. Numerantium, 121 (1996). 19-32.
[4]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. Numerantium, 134 (1998), 107-116.
[5]Leighton. F. T.. New lower bound techniques for VLSI[.J], Math. System The-ory. 17 (1984). 47-70.
[G]Harary. F.. Graph Theory[M]. Addision-Wesley. Reading. MA. 1969.
[7]Bondy, J.A., Murty, U.S.R., Graph Theory With Applications, Published in Great Britain: The Macmillan Press Ltd., 1976, 135.
[8]Erdos, P. and R. K. Guy. Crossing number problems[.T], Am. Math. Month., 80 (1973), 52-58.
[9]Guy, R. K., The decline and fall of Zarankiewiez's theorem in Proof Techniques in Graph Theory [J], Academic Press, New York. 1969, 63-69.
[10]Szekely, L. A., A successful concept for measuring non-planarity of graphs: The crossing number[J], Discrete Math., 276 (2004), 331-352.
[11]Tutte. W. T.. Toward a theory of crossing uumbers[J]. .J.Combinatorial Theor\ 8 (1970), 45-53.
[12]Garary. M. It. and D. S. Johnson. Crossing number is NP-complete[.I|. S1AM J. Algebrie Discrete Methods. 4 (1993). 312-316.
[13]Dean, A. M. and R.B. Riehter. The crossing number of C4×C4[J].J. Graph Theory. 19 (1995). 125-129.
[14]Eggleton. R.B. and R. P. Guy. The crossing number of the n cube[J]. Amei Math. Soe. Notices. 17 (1970). 757.
[ 1 5]Kuratowski.K . Sur le probleme desconrbes ganches on topologie.Eund. Mat h. 15 (1930). 271-283.
[16]Guy.R. K.. Grossing numbers of graphs[J]. In Graph Theory and Applications Lecture Notes in Mathematies, vol. 303. Spring-Verlag. Heidelberg. Berlin. New York. .Mav 1972.111-124.
[17]Shengjnn.P. and R. Bruce Richter. The crossing number of K11 is 100[J].J. Graph Theory, 56 (2007). 128-134.
[18]Zaraukiewicz K. On a Problem of P.Turan Concerning Ciraphs.Found Math., 41 (1954), 137-145.
[19]Kleitnan D.J. The crossing number of K5,n.J.Combinatorial Theory, 9 (1970). 315-323.
[20]Woodall D R. Cyclic-order graphs an Zn.rankiewicz's crossing number conjec-ture.J Graph Theory. 17(6) (1993). 657-671.
[21]Asano, K., The crossing number of K1,3n and K2,3n[J], J. Graph Theory, 10 (1986), 1-8.
[22]Huang, Y. and T. Zhao, The crossing number of K1,4,n[J], Discrete Mathemat-ics, 308 (2008), 1634-1638.
[23]Huang, Y. and T. Zhao, The crossing number of K2,4,n[J],已投稿.
[24]Mei, H. and Y. Huang, The crossing number of K1,5,n[J], International Journal of Mathematical combinatorics. 1 (2007), 33-44.
[25]黄元秋,赵霆雷.关于完全3部图K1,6,n的交叉数[J].应用数学学报,29(6)(2006)1046-1053.
[26]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.
[27]王晶.黄元秋.完全3-部图K1.10.n的交叉数[J].高校应用数学学报.23(3)(2008).349-356.
[28]王晶.关于一些图类的交叉数[D].硕士学位论文.湖南师范大学.(2006).
[29]Ho. P. T., The crossing number of K1,m,n[J], Discrete Mathematics, 308 (2008). 5996-6002.
[30]Ho, P. T., The crossing number of some complete multipartite graphs[J], Util. Math., (in press).
[31]Harary, F., P.C.Kainen, A.J.Schwenk, Toroidal graphs with arbitrarily high crossing numbers[J], Nana Math., 6 (1973), 58-67.
[32]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.
[33]Anderson. M. S.. R. B. Richter, P. Rodney- Crossing number of C6×c6[J]. Congressus Nunierantiuni. 118(1996). 97-107.
[34]Anderson. M. S.. R.B. Richter. P. Rodney. The crossing number of C7×c7[J]. Cong Numet.. 125 (1997). 97-117.
[35]Glebsky. L. Y and G. Salazar. The crossing number of Cm×Cn is as conjectured for n> m(m+1)[J].J.Craph Theory. 47 (2001). 53-72.
[36]Beiueke.L.W. and R.D. Riugeisen. On the crossing numbers of products of cycles and graphs of order four[J].J. Graph Theory, 4 (1980), 145-155.
[37]Jendrol. S. and M. .Scerbova.On the crossing numbers of ,Sm×Pn and ,Sn, Cn[J].Cas. Pest. Mat.. 107 ;(1982). 225-230.
[38]Klesc.M.. On t he crossing numbers of Cartesian produets of stars and paths or cycles[J]. Math. Slovaca. 41 (1991), 113-120.
[39]Klesc. M.. The crossing numbers of products of paths and stars with 4-vertex graphs[J].J. Graph Theory. 18 (1994). 605-614.
[40][40 Kle.sr. M.. The crossing numbers of certain Cartesian products[J]. Discuss Alath.-Graph Theory, 15 (1995), 5-10.
[41]Klesc, M.. The crossing nuiuber of K2.3×Pn and K2.3×Sn[J], Tatra Montains Math. Publ.,9 (1996). 51-56.
[42]Klesc, M., The crossing numbers of products of 5-vertex graphs with paths and cycles, Discussiones Mathematieae-Graph.Theory. 19 (1999), 59-69.
[43]Kle.sc, M., The crossing number of K5×Pn,[J], Tatra Moutains Math. Publ., 18 (1999), 63-68.
[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 products of stars and graphs of order five[J], Graphs and Combinatorics, 17 (2001). 289-294.
[46]Klesc. M., The crossing number of A2,3×C3[J]. Discrete Math., 251 (2002), 109-117.
[47]肖文兵.黄元秋,一类笛卡尔积图的交叉数[J],湖南师范大学学报(自然科学版),4(2004),3-7.
[IS]Klesc, M. and A. Kocurova. The crossing numbers of products of 5-vertex graphs with cycles[.J]. Discrete Math.. 307 (2007). 1395-1-103.
[49]Peng, Y. H. and Y. C. Yiew, The crossing number of P(3.1)×Pn[J], Discrete Math., 306 (2006), 1941-1946.
[50]马祖强,蔡俊亮.W5×Sn的交叉数.应用数学学报,31(4)(2008),615-623.
[51]Zheng, W., X. Lin, Y. Yang, C. Cui, On the crossing number of Km×Pn[J], Graphs and Combinatorics, 23 (2007), 327-336.
[52]王晶,黄元秋,K2,4×Pn的交叉数[J],数学物理学报,28A(2008),251-255.
[53]吕胜祥,黄元秋,K2,A×Sn的交叉数[J],系统科学与数学,30(7)(2010),929-935.
[54]Bokal. D., On the crossing numbers of Cartesian products with paths[J].J. Combin. Theory Ser B., 97 (2007), 381-384.
55] Tang, L., S. Lv, Y. Huang, The crossing number of Cartesian products of complete bipartite graphs K2.m with paths Pn[J]. Graphs and ('ombinatories 23 (2007). G59-GGG.
[56]Zheng. W.. X. Lin. Y. Yang. The crossing number of K2.m×Pn[J].Discrete Math., 308 (2008). 6639-6644.
[57]Yang. Y.. X. Lin. J. Lu. X. Hao. The crossing number of C(n:{1.3})[J]. Discrete Math.. 289 ('2001). 107-l18.
[58]Lin, X.. Y. Yang.J. Lu. X. Hao. The crossing number of C(mk;{1,k})[J]. Graphs and Combinatorics. 21 (2005). 89-9G.
[59]Lin. X.. Y. Yang. J. Lu. X. Hao. The crossing number of C(n:{ 1.|n/2|1})[J]. Util. Math.. 71 (200G). 24-255.
[60]Ma, D., H. Ren.J. Lu, The crossing number of the circular graph C(2m) 2,m)[J], Discrete Mathematics, 304 (2005). 88-93.
[61]Ho, P. T.. The crossing number of C(3k 1: { 1,k})[J]. Discrete Math.,307 (2007), 2771-2774.
[62]Jing Wang, Yuanqiu Huang. The Crossing Number of the Cireulant Graph C(3k-1: l.k)[J], International .LMath. Gonibiu. Vol.3 (2008), 79-81.
[63]Sala.zar, G., On the crossing numbers of loop networks and generalized Peterson graphs[J], Diserete Math., 302 (2001), 243-253.
[64]Jager P de,J.W.Ren. Phase portraits for quadratic systems with a higher order singularity.Rroeeedings ICTAM, 87 (1987),75-87.
[65]Fiorini, S., On the crossing number of generalized Petersen graphs[J], Ann. Disrete Math.. 30 (1986), 221-242.
[66]Mcquillan, D. and R. B. Richter, On the crossing number of certain generalized Petersen graphs[J],Ann. Discrete Math., 104 (1992), 311-320.
[67]Richter, R. R. and G. Salazar,The crossing number of P(N,3)[J], Graphs and Combinatorics, 18 (2002). 381-394.
[68]Lovrecic Sarazin, M., The crossing number of the generalized Petersen graph P(10.4) is four[J]. Math. Slovaca. 47 (2) (1997). 189-192.
[69]Hao, R. and Y. Liu. New upper bounds on crossing number of circular graphs [J], OR Transactions. 3 (1999). 1-6.
[70]Liu,T. and Y. Liu. On the crossing number of circular graphs[J]. OR Transac-tions. 4(1998). 31-38.
[71]卢俊杰,任韩,马登举.C(m,3)的交叉数[J],系统科学与数学,24(4)(2004),504-512.
[72]Ma, D., H. Ren, J. Lu, New results of the crossing number of circular graphs[J], J. of Nanhua University, 17 (4) (2003), 17-20.
[73]马登举,任韩,卢俊杰,广义Petersen图G(2m+1,m)的交叉数[J],华东师范大学学报,1(2005),34-39.
[74]Guy, R. P., Latest results on crossing numbers, In Proc. Recent Trends in Graph Theory[J], Lecture Notes in Mathematics, 186 (1971), 143-156.
[75]Madej. T.. Hounds for the crossing number of the n cube[J].J. Graph Theory. 15 (1991). 81-97.
[76]Sykora, 0. and I. Vrt'o, On the crossing number of the hypercube and cube connected c,ycles[Jl, BIT. 33 (1993). 232-2:57.
[77]Faria, L.,C. M. H. de Figueiredo. On Fggleton and Guy conjectured upper bound for the crossing number of the n cube[J]. Mathiematica Slovaca.50 (20()0). 271-287.
[78]Faria, L., Colina Miraglia Herrera. de Figueiredo. Oudrej Sykora.Imrich Vrt'o. An improved upper hound on the crossing number of the hypercube[J] J. Graph Theory. (200S). doi.10.1002/jg.20330.
[79]Oporowski, B. and David Zhao. Coloring graphs with crossings[J]. Discrete Mathematics. (2008). doi:10. 1016/j.disc.2008.07.010.
[80]Klese The join of graphs and crossing numbers, Electronic Notes in Distices and Mathematics. 2S (2007). 349-355.
[81]KlesrcM. The crossing numbers of join of the special graph on six vertices with path and cycle. Discrete Mathematics.310(2010). 1475-1481.
[82]Guy. R3,T..Jenkyns. .J.Sehaer.The toroidal crossing number of the complete graph[J],J. Combin. Theory, 4 (1968), 376-390.
[83]R.iskin. A., The genus 2 crossing number of K9[J]. Discrete Mathematics. 145 (1995), 211-227.
[84]Gross, J. L. and T. W. Tucker, Topological Graph Theory|M], Wiley-Interscience Publication, New York, pp: 19-20, (1987).
[85]Guy, R. K. and T. A. Jenkyns, The toroidal crossing number of Km,n[J], J. Combin. Theory, 6 (1969), 235-250.
[86]Richter,R.B. and J. Siran, The crossing number of K3,n in a surface[J], Journal of Graph Theory, 21 (1996), 51-54.
[87]Ho, P. T.,The crossing number of K4,n on the real projective plane[J], Discrete Mathematics,304 (2005),23-33.
[88]Ho,P. T.,The toroidal crossing number of K4,n[J], Discrete Mathematics (2008). doi:10.1016/.j.disc.2008.09.029.
[89]Lv, S., L. Tang, Y. Huang, The toroidal crossing number of K4.n[J],已投稿
[90]Carcia-Moreno. E. and G. Salazar. Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree [J], J. Graph Theory,36 (2001), 168-173.
[91]Juarez.H. A. and G. Salazar. Optimal meshes of curves in the Klein bottle[J]. Journal of Combinatorial Theory. Series B. 88 (2003). 185-188.
[92]Riskin, A., On the nonembeddability and crossing numbers of some Kleinical polyhedral maps on the torus[J], Graphs and Combinatorics, 21 (2005), 131-135.
[93]Ajtai, M., V. Chvatal, 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.
[94]Pach, J., J. Spencer, G. Toth, New bounds on crossing numbers[J], Discrete Comput. Geom., 24 (2000), 623-644.
[95]Pach,J.,R.Radoirir. G. Tardos, G. Toth. Improving the Crossing Lemma by finding' more crossings in sparse graphs[J], Discrete Comput. Ceom..36 (2006). 527-552. [96] Fox, J and C. D. Toth, On the decay of crossing numbers[J].Jonnial of Com-binatorial Theory. Series B. 08 (2008). 33-42.
[97]Montaron. B.. An improvement of the crossing number bound[J]. J Grapl Theory. 50 (2005), 13-54. [98] Pach. J. and G. Toth Graphs drawn with few crossings per edge[J]. Combina-torica. 17 (3) (1997). 427-439.
[99]Jozef Siran, Infinite families of erossing-eritical graphs with a given crossing number[J]. Discrete- Mathematics. 18 (1081). 129-132.
[100]Martin Kochol. Const rucion of crossing-critical graphs[J].Discrete Mathemat-ics. 66 (1987). 311-313.
[101]Richt.er, R. B. and C. Thomassen. Minimal graphs with crossing number at least, k, Journal of Combinatorial Theory[J].Series B.58 (1993). 217-224.
[102]Salazar. G., On a crossing number result of Hichter and Thomassen[J].Journal of Combinatorial Theory, Series B. 70 (2000). 98-99.
[103]Salazar, G., Infinite families of crossing-critical graphs with given average de-gree, Discrete Matheinatics(J], 271 (2003). 313-350.
[104]Hlincny, P., Crossing-number critical graphs have bounded path-widt h[J]. Jour-nal of Combinatorial Theory, Series B, 88 (2003). 347-367.
[105]Richter, R. B., Cubic graphs with crossing number two[J], Journal of Graph Theory, 12 (3) (1988), 363-374.
[106][106] McQuillan, D. and R. Bruce Richter, On 3-regular graphs having crossing number at least 2[J], Jouranl of Graph Theory. 18 (8) (1994), 831-839.
[107]Hlineny. P., Crossing number is hard for cubic graphs[J], Journal of Combina-torial Theory, Series B, 90 (2006), 455-471.
[108]Jendrol, S. and Marian Klese, On the graphs whoso line graphs have crossing member one[J], Journal of Graph Theory. 37 (2001). 181-188.
[109]Sedlaeek. J.. Some properties of interchange graphs. Theory of Graphs and its Applications[M]. M. Fiedler. (Editor). Academic Press. New York.(1962). 145-150.
[110]Kulli, V. R... D. G. Akka, L. W. Beineke, On the line graphs with crossing number 1[J], J. Graph theory. 3 (1979). 87-90.
[111]Akka, D. G.. S. Jendrol, M. Klesc and S. V. Panshetty, On line graphs with crossing number 2[J]. Univ. Beograd Publ. Elektrotehn Fak-Ser Math., 8 (1997), 3-8.
[112]Huang, Y., and T. Zhao, The crossing number of the line graphs [J], Submitted.
[113]Bienstock, D. and N. Dean, Bounds for rectilinear crossing numbers[J], J. Graph Theory, 17 (1993), 333-348.
[114]Brodsky, A., S. Durocher, E. Genthner, The rectilinear crossing number of K10 is 62[J], The Electronic J. Combinatorics 8, Research paper 23 (2001).
[115]Aichholzer. O. Graz.F. Aureiihanimer Graz. H. Krassor Graz, On the crossing number of complete graphs[J]. Coniput ing. 70 (2000), 105-170.
[116]Abrego, B. M. and Silva Fernandez-Merchant. A lower bound for the rectilinear crossing number[J].Graphs and Combinatorics. 21 (2005). 293-300.
[117]Brodsky. A.. Stephane Durocher.Ellen Gethner. Toward the rectilinear cross ing number of Kn: new drawings, upper hounds, and asymptot ies[J]. Discrete Mathematies. 202 (2003). 59-77.
[118]Pach. J., Which crossing number is it anyway?[J],Journal of Comiinatorial Theory. Series B. 80 (2000). 225-246.
[119]Kohnan. P. and J(?) Matousek. Crossing number. pair-crossing number. and expansion[J]. Journal of CoMbinatorial Theory. Series B, 92 (2001), 99-113.
[120]P'elsma jer. M.J.. Marcus Schaefer. Daniel .Sefankovir. Removing even cro ings[J]. J. Combin. Theory Ser. B. (2006) doi: 10.1016/j.jetb.2006.08.001.
[121]Pelsmajer. M.J.. Marcus Schaefer. Daniel Sefankovic. Odd crossing number and crossing number are not the sanie[J].Discrete Comput.Geom..39 (2008). 442-454.
[122]Archdeacon. D.and R. Bruce Richter. On the parity of crossing numbers[J],J. Graph Theory, 12 (3) (1988). :307-310.
[123]Klavzar, S. and B. Mohar, Crossing imnibers of ,Sierpinski-like graphs[J],J Graph Theory. 50 (2005), 186-198.
[124]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.
[125]Tang L, Wang .J. Huang Y Q. The crossing number of the join of Cn and Pn International .J Math Com, 11 (2007), 110-116.
[126]于平.黄元秋.Pm与Wn的笛卡尔积图的交叉数[J]，湖南师范大学学报(自然科学版),1(2005)14-16.
[127]贺佩玲.关于图的交叉数的研究,硕士学位论文[J]，湖南师范大学.2007.
[128]S.Jendrol. M.Scerbova, On the crossing number of Sm ×Cn,Cas.Pest.Mat. 107(1982). 225-230.