摘要
图的交叉数是在近代图论中发展起来的一个重要概念,确定一般图的交叉数是一个NP-完全问题,因此到目前为止有关交叉数的结果很少,且仅限于一些特殊图类的交叉数.本文运用k-连通图限制画法下的求交叉数法、组合方法、归纳思想和反证法等,确定了一些特殊的图与路的笛卡尔积的交叉数,一类循环图的一点悬挂与两点悬挂的交叉数,这类循环图分别与路、星、树和圈的笛卡尔积的交叉数,及一类外平面图与圈的笛卡尔积的交叉数,并对Petersen图P(m,1)与路的笛卡尔积的交叉数进行了推广.全文由十个章节构成.
第一章交代了交叉数的起源,交叉数研究在国内外发展的动态,以及这项研究工作的理论及实际意义.
第二章对与交叉数有关的一些基本概念、定义和性质进行了解析或者说明,运用图的连通性得到了n—连通图和4—连通循环图C(l,2)的两个拷贝相交叉的一些性质等.
第三章研究K_(2,2,2)和K_(1,1,2,2)的相关性质,并利用这些性质确定K_(1,1,2,2)与路P_n的交叉数.利用P(3,1)和K_(2,4)与路的交叉数的有关结果得到了三个特殊的六个顶点的图与路的交叉数.
第四章在K_(1,3,n)和K_(2,3,n)交叉数的基础上,利用n-连通图相交叉的有关性质等,得到了七阶循环图C(7,2)与路P_n的笛卡尔积的交叉数和一个七阶3-连通图与路P_n的笛卡尔积的交叉数.
第五章探索Petersen图P(4,1)与八阶循环图C(8,2)的相关性质,确定了C(8,2)和P(4,1)与路P_n的笛卡尔积的交叉数.
第六章利用循环图C(l,2)的一点悬挂和两点悬挂的性质和画法等确定了C(l,2)的一点悬挂与两点悬挂的交叉数.
第七章在C(7,2)和C(8,2)与路的笛卡尔积的交叉数的研究基础上,对原有的方法进行改进和推广,确定了循环图C(9,2)、C(10,2)和C(12,2)分别与路P_n的笛卡尔积的交叉数.
第八章在假定Zarankiewicz猜想成立的基础上,由于循环图C(l,2)与路、星和树的笛卡尔积的交叉数研究的难度,我们采取限制C(l,2)的主圈上没有交叉点的措施,得出了循环图C(l,2)在限制条件下与路、星和树的笛卡尔积的交叉数.
第九章限制C(l,2)的主圈上没有交叉点,得出了循环图C(l,2)在限制条件下与圈的笛卡尔积的交叉数的下界.同时还得到了一类外平面图与圈的笛卡尔积的交叉数.
在最后一章中,简要地进行了总结,并介绍了作者今后研究的方向和重点及一些有待解决的问题.
The crossing number of graphs is a vital concept in morden graph theory, we have already known that to determine the crossing numbers of graphs is NP-complete. At present the classes of graphs whose crossing numbers have been de-termined are very scarce,and there are only some special graphs whose crossing numbers are known.In this paper,we study the crossing numbers of the Cartesian products of paths,stars,cycles with circular graphs,a Petersen graph and some special graphs,and we discuss the crossing numbers of one suspension and a double suspension of circular graph C(l,2),and explore the crossing numbers of the Cartesian products of outplanar graphs with cycles.
At first,in Chapter one,we introduce the backgrouds and origins of the crossing number and its developments and recent situations around the world,and present the meanings of the research.
In Chapter two,we give some conceptions and properties of the crossing number, and present the properties of n-connected graph and circular graphs and so on.
In Chapter three,properties of K_(2,2,2) and K_(1,1,2,2) are investigated,and with the results of the crossing number of P(3,1) and K_(2,4) with paths,the crossing numbers of Cartesian products of paths with K_(1,1,2,2) and three speical 6-vertex graphs are determined.
In Chapter four,applying the results of crossing numbers of K_(1,3,n) and K_(2,3,n) and the properties of n-connected graph,we obtain the crossing numbers of the Cartesian products of paths with circular graph C(7,2) and a 3-connected graph of seven vertices.
In Chapter five,the properties of Petersen graph P(4,1) and the relations of P(4,1) and circlar graph C(8,2) being studied,the crossing number of Cartesian products of paths with C(8,2) and P(4,1) are determined.
In Chapter six,by the properties and drawings of one suspension and a double suspension of circular graph C(l,2) which is 4-connected graph,we obtain the crossing numbers of one suspension and a double suspension of circular graph C(l,2).
In Chapter seven,we improve on the methods of chapter's four and five,and determine the crossing numbers of Cartesian products of paths with circular graphs C(9,2),C(10,2) and C(12,2).
In Chapter eight,supposing that the conjecture of Zarankiewicz is true,and letting there be no crossing points in the principle cyle of C(l,2),we determine the crossing numbers of Cartesian product of paths,stars,trees with C(l,2).
In Chapter nine,letting there be no crossing points in the principle cyle of C(l,2),we study the lower bound on the crossing numbers of Cartesian products of cycles with C(l,2),and the crossing numbers of Cartesian products of cycles C_n with some outplanar graphs.
In the last chapter,we make a summary of th paper and intruduce the directions of our research work and put forward some relative problems which we will go ahead.
引文
[1]Bondy,J.A.& U.S.R.Murty.Graph theory with application[M].New York:Macmillan London and Elsevier,1979.
[2]Harary,F.Graph theory[M].Addison-Wesley:Reading,MA,1969.
[3]Turan,P.A note of welcome[J].Journal of Graph Theory,1977,1:7-9.
[4]Myers,N.The crossing number of C_m × C_n:A Reluctant Induction[J].Math.magazine,1998,71(5):350-359.
[5]Tutte,W.T.Toward a theory of crossing numbers[J].Journal of Combinatorial Theory,1970,8:45-53.
[6]Erd(o|¨)s,P.R.& K.Guy.Crossing number problems[J].Am.Math.Month.,1973,80:52-58.
[7]Pach,J.& G.T(?)ch.Which crossing number is it anyway?[J].Journal of Combinatorial Theory(Series B),2000,80:225-246.
[8]CS20C Progress Report.Crossing numbers[EB/OL].http://www.stetson.edu/hpulapak/crossing/
[9]Pach,J.& G.T(?)ch.Thirteen problems on crossing numbers[J].Geombinatorics,2000,9:194-207.
[10]Leighton,F.T.Complexity issues in VLSI[M].Cambridge:The MIT Press,1983.
[11]Garey,M.R.& D.S.Johnson.Crossing number is NP-complete[J].SIAM J.Alg.Disc.Meth.,1983,1:312-316.
[12]Leighton,F.T.New lower bound techniques for VLSI[J].Math.Sys.Theory,1984,17:47-70.
[13]Bhatt,S.N.& F.T.Leighton.A framework for Solving VLSI Graph Layout Problems[J].J.Comput.System.Sci.,1984,28:300-343.
[14]Pach,J.& F.Shahrokhi,M.Szegedy.Applications of the crossing number[J].Algorithmica,1996,16:111-117.
[15]Peng,Y.H.& Y.C.Yiew.The crossing number of P(3,1) ×P_n[J].Discrete Math.,2006,306:1941-1946.
[16]杨元生,王丹,陆维明.四正则图的交叉数[J].软件学报,2002,13(12):2259-2266.
[17]Harborth,H.& I.mengersen.Drawings of the complete graph with maximum number of crossing[J].Congressus Numerantium,1992,88:225-228.
[18]Harborth,H.& I.Mengersen.Edges without crossings in drawings of complete graphs[J].Journal of Combinatorial Theory(Series B),1974,17:299-311.
[19]Harborth,H.Empty triangles in drawings of the complete graph[J].Discrete Math.,1998,191:109-111.
[20]Klerk,E.D.& J.Maharry,D.V.Pasechnik,R.B.Richter,G.Salazar.Improved bounds for the crossing numbers of K_(m,n) and K_n[J].SIAM Discrete Math.,2006,20(1):189-202.
[21]Pan,S.& R.B.Richter.The crossing number of K_(11) is 100[J].Journal of Graph Theory,2007,56:128-134.
[22]Zarankiewicz,K.On a problem of P.Turan concerning graphs[J].Found.Math.,1954,41:137-145.
[23]Guy,R.K.The decline and fall of Zarankiewic's theorem[A],in:Proc.Proof Techniques in Graph Theory(F.Harary ed.)[C].N.Y.:Academic Press,1969,pp.63-69.
[24]Nagi,H.N.On the crossing number of K_(m,n)[J].The Electronic Journal of Combinatorics,2003,10:1-8.
[25]Kleitman,D.J.The crossing number of K_(5,n)[J].Journal of Combinatorial Theory (Series B),1970,9:315-323.
[26]Woodall,D.R.Cyclic-order graphs and Zarankiewicz's crossing-number conjecture [J].Journal of Graph Theory,1993,17(6):657-671.
[27]Asamo,K.The crossing number of K_(1,3,n) and K_(2,3,n)[J].Journal of Graph Theory,1986,10:1-8.
[28]Harary,F.& P.C.Kainen,A.J.Schwenk.Toroidal graphs with arbitrarily high crossing numbers[J].Nanta.Math.,1973,6:58-67.
[29]Ringeisen,R.D.& L.W.Beineke.The crossing number of C_3×C_n[J].Journal of Combinatorial Theory(Series B),1978,24:134-136.
[30]Beineke,L.W.& R.D.Ringeisen.On the crossing numbers of products of cycles and graphs of order four[J].Journal of Graph Theory,1980,4:145-155.
[31]Kle(?),M & a.B.Richter,L.Stobert.The crossing number of C_5×C_n[J].Journal of Graph Theory,1996,22(3):239-243.
[32]Richter,R.B.& G.Salazar.The crossing number of C_6×C_n[J].Australasian Journal of Combinatorics,2001,28:135-143.
[33]Adamsson,J.& R.B.Richter.Arrangements,circular arrangements and the crossing number of C_7×C_n[J].Journal of Combinatorial Theory(Series B),2004,90(1):21-39.
[34]Dean,A.M.& R.B.Richter.The crossing number of C_4×C_4[J].Journal of Graph Theory,1995,19(I):125-129.
[35]Richter,R.B.& C.Thomassen.Intersection of curve systems and the crossung number of C_5×C_5[J].Discrete & Computational Geometry,1995,13:149-159.
[36]Anderson,M.& R.B.Richter,P.Rodney.The crossing number of C_6×C_6[J].Congr.Numer.,1996,118:97-107.
[37]Anderson,M.& R.B.Richter,P.Rodney.The crossing number of C_7×C_7[J].Congr.Numer.,1997,125:97-117.
[38]Salazar,G.On the crossing number of C_m ×C_n[J].Journal of Graph Theory,1998,28(3):163-170.
[39]Salazar,G.A lower bound for the crossing number of C_m×C_n[J].Journal of Graph Theory,2000,35:222-226.
[40]Salazar,G.Drawings of C_m × C_n with one disjoin family[J].Journal of Combinatorial Theory(Series B),1999,76(2):129-135.
[41]Juarez,H.A.& G.Salazar.Note drawings of C_m× C_n with one disjoin family Ⅱ[J].Journal of Combinatorial Theory(Series B),2001,82:161-165.
[42]Jendro(?),S.& M.S(?)erbov(?).On the crossing numbers of S_m×P_n,and S_m×C_n[J].(?)as.P(?)st.Math.,1982,107:225-230.
[43]Kle(?),M.On the crossing number of Cartesian products of stars and paths or cycles[J].Math.Slovaca,1991,41:113-120.
[44]Zheng,W.& X.Lin,Y.Yang,C.Deng.On the crossing numbers of K_m ×C_n and K_(m,l)× P_n[J].Discrete Appl.Math.,doi:10.1016/j.dam.2007.09.007.
[45]Zheng,W.& X.Lin,Y.Yang,C.Cui.On the Crossing Number of K_(m) ×P_n[J].Graphs and Combinatorics,2007,23:327-336.
[46]Zheng,W.& X.Lin,Y.Yang.The Crossing Number of K_(2,m)× P_n[J].Discrete Math.,doi:10.1016/j.disc.2007.11.014
[47]Kle(?),M.The crossing numbers of products of paths and stars with 4-vertex graphs[J].Journal of Graphs Theory,1994,18:605-614.
[48]Kle(?),M.The crossing numbers of certain Cartesian products[J].Discussions Mathematica-Graph Theory,1995,15:5-10.
[49]Kle(?),M.The crossing number of K_(2,3 ×P_n and K_(2,3)× S_n[J].Tatra Mountains Math.Publ.,1996,9:51-56.
[50]Kle(?),M.The crossing numbers of products of 5-vertex graphs with paths and cycles[J].Discussions Mathematica-Graph Theory,1999,19:59-69.
[51]Kle(?),M.The crossing number of K_5 × P_n[J].Tatra Mountains Math.Publ.,1999,18:63-68.
[52]Kle(?),M.The crossing numbers of Cartesian products of paths with 5-vertex graphs[J].Discrete Math.,2001,233:353-359.
[53]Kle(?),M.On the crossing numbers of products of stars and graphs of order five[J].Graphs and Combinatorics,2001,17:289-294.
[54]Kle(?),M.The crossing number of K_(2,3) × C_3[J].Discrete Math.,2002,251:109-117.
[55]Fiorini,S.On the crossing number of generalized Petersen graphs[J].Ann.Discrete Math.,1986,30:221-242.
[56]Richter,R.B.& G.Salazar.The crossing number of P(N,3)[J].Graphs and Combinatorics,2002,18(2):381-394.
[57]McQuillan,D.& R.B.Richter.On crossing number of certain generalized Petersen graphs[J].Ann.Discrete Math.,1992,104(3):311-320.
[58]Saraz(?)n,M.L.The crossing number of the generalized Petersen graph P(10,4) is four[J].Math.Slovaca,1997,47:189-192.
[59]Yang,Y.& X.Lin,J.Lu,X.Hao.The crossing number of C(n;{1,3})[J].Discrete Math.2004,289:107-118.
[60]Lin,X.& Y.Yang,J.Lu,X.Hao.The crossing number of C(mk;{1,k})[J].Graphs and Combinatorics,2005,21:89-96.
[61]Liu,W.& Y.Liu.On the crossing number of circular graphs[J].运筹学学报,1998,2(4):32-38.
[62]Hao,R.& Y.Liu.New upper bounds on crossing number of circular graphs[J].运筹学学报,1999,3(3):1-6.
[63]Lin,S.& W.Xu,H.Ren.The crossing number of C(3m,m)[J].华东师范大学学报(自然科学版),2007,3:62-66.
[64]马登举,任韩,卢俊杰.循环图交叉数的新结果,华南大学学报(理工版),2003,17(4):17-20.
[65]Ma,D.& H.Ren,J.Lu.The crossing number of circular graph C(2m + 2,m)[J].Discrete Math.,2005,304:88-93.
[66]Tung Ho,P.The crossing number of C(3k + 1;{1,k})[J].Discrete Math.,2007,307:2771-2774.
[67]Salazar,G.On the crossing numbers of loop networks and generalized Petersen graphs.Disc.Math.,2005,302:243-253.
[68]Oporowski,B.& D.Zhao.Coloring graphs with crossings[J].Discrete Math.,2008,doi:10.1016/j.disc.2008.07.040.
[69]Shahrokhi,F.O.& L.A.S(?)kora,Sz(?)kely I.Vrt'o.Intersection of curves and crossing number of C_m × C_n on surfaces[J].Discrete Comput.Geom.,1998,19:237-247.
[70]Negami,S.Crossing numbers of graph embedding pairs on closed surfaces[J].Journal of Graph Theory,2001,36:8-27.
[71]Shalirokhi,F & L.A.Sz(?)kely,O.S(?)kora,I.Vet'o.Drawing of graphs on surfaces with few crossings[J].Algorithmica,1996,16:118-131.
[72]Shahrokhi,F.& O.S(?)kora,L.A.Sz(?)kely,I.Ve(?)o.The crossing number of a graph on a compact 2-manifold[J].Advances in Mathematics,1996,123:105-119.
[73]Riskin,A.On the nonembeddability and crossing numbers of some toroidal graphs on the Klein bottle[J].Discrete Math.,2001,234:77-88.
[74]Bonnington,C.P.& M.E.Watkins.Planar embeddings with infinite surfaces[J].Journal of Graph Theory,2003,42:257-275.
[75]Riskin,A.The projective plane crossing number of C_3×C_n[J].Journal of Graph Theory,1993,17(6):683-693.
[76]Tung Ho,P.The crossing number of K_(4,n) on the real projective plane[J].Discrete Math.,2005,304:23-33.
[77]Guy,R.K.& W.A.Jenkyns.The toroidal crossing number of K_(m,n)[J].Journal of Combinatorial Theory,1969,6:235-250.
[78]Bienstock,D.& N.Dean.New results on rectilinear crossing numbers and plane embeddings[J].Journal of Graph Theory,1992,16(5):389-398.
[79]Jensen,H.F.An upper bound for the rectilinear crossing number of the complete graph[J].Journal of Vombinatorial Theory,1971,11:212-216.
[80]Salazar,G.On the intersections of systems of curves[J].Journal of Combinatorial Theory(Series B),1999,75:56-60.
[81]Bienstock,D.& N.Dean.Bounds for rectilinear crossing numbers[J].Journal of Graph Theory,1993,17(3):333-348.
[82]Bienstock,D.Some provable hard crossing number problems[J].Discrete & Computational Geometry,1991,6:443-459.
[83]Wagner,U.On the rectilinear crossing number of complete graphs[EB/OL].http://www.inf.ethz.ch/personal/wagneru/manuscripts/crossing-encounters.pdf.
[84]Kolman,P.& J.Matou(?)ek.Crossing number,pair-crossing number and expansion [J].Journal of Combinatorial Theory(Series B),2004,92:99-113.
[85]Pelsmajer,M.J.& M.Schaefer,D.(?)efankovi(?).Odd crossing number is not crossing number "[A],in:Proc.13th Intl.Symposium on Graph Drawing,Lecture Notes in Computer Science 3843[C],Berlin:Springer,2006,pp.386-396.
[86]McQuillan,D.& R.B.Richter.On 3-regular graphs having crossing number at least 2[J].Journal of Graph Theory,1994,18(8):831-839.
[87]Kochol,M.Note construction of crossing-critical graphs[J].Discrete Math.,1987,66(3):311-313.
[88]Richter,R.B.& C.Thomassen.Minimal graphs with crossing number at least κ[J].Journal of Combinatorial Theory(Series B),1993,(58):217-224.
[89]Hlin(?)ny,P.Crossing-number critical graphs have bounded path-width[J].Journal of Combinatorial Theory(Series B),2003,88:347-367.
[90](?)ir(?),J.Infinite families of crossing-critical graphs with a given crossing number[J].Discrete Math.1984,48(1):129-132.
[91]Salazar,G.Infinite families of crossing-critical graphs with given average degree[J].Discrete Math.,2003,271:343-350.
[92]Sedlacek,J.Some properties of interchange graphs[A].Theory of Graphs and its Applications[C].New York:Academic Press,1962,pp.145-150.
[93]Kulli,V.R.& D.G.Akka,L.W.Beineke.On the line graphs with crossing number 1[J].Journal of Graph theory,1979,3:87-90.
[94]Jendro(?),S.& M.Kle(?).On the graphs whose line graphs have crossing number one[J].Journal of Graph Theory,2001,37:181-188.
[95]Akka,D.G.& S.Jendro(?),M.Kle(?),S.V.Panshetty.On line grapgs with crossing number 2[J].Univ.Beograd Publ.Elektrotehn Fak-Ser Math.,1997,8:3-8.
[96]Huang,Y.& T.Zhao.The crossing number of the line graphs,Submitted.
[97]Pach,J.& G.T(?)th.Graghs drawn with few crossing per edge[J].Combinatorica,1997,17:427-439.
[98]Moreno,E.G.Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree[J].Journal of Graph Theory,2001,36:168-173.
[99]Green,J.E.& R.D.Ringeisen.Lower bounds for the maximum crossing number using certain subgraphs[J].Congressus Numeratium,1992,90:193-203.
[100]Kainen,P.C.& A.T.White.On stable crossing numbers,Journal of Graph Theory,1978,2:181-187.
[101]Pinontoan,B.& R.B.Richter.Crossing numbers of sequences of graphs Ⅱ:planar toles,Journal of Graph Theory,2003,42:332-341.
[102]Kemnitz,A.& H.Harborth.Plane integral drawings of planar graphs[J].Discrete Math.,2001,236:191-195.
[103]Archdeacon,D.& R.B.Richter.On the parity of crossing numbers[J].Journal of Graph Theory,1988,12(3):307-310.
[104]Kleitman,D.J.A note on the parity of the number of crossings of a graph[J].Journal of Combinatorial Theory(Series B),1976,21:88-89.
[105]Grohe,M.Computing crossing number in quadratic time[C],32nd A CM Symposium on Theory of Computing STOC'01,2001,pp.231-236.
[106]Harborth,H.Maximum number of crossings for the cube graph[J].Congressus Numerantium,1991,82:117-122.
[107]Hlin(?)n(?),P.Crossing number is hard for cubic graphs[A].In:Math Foundations of computer Science MFCS 2004.Lecture Notes in Computer Science 3153[C].Springer Verlag,2004,pp.772-782.
[108]Madej,T.Bounds for the crossing number of the N-cube[J].Journal of Graph Theory,1991,15:81-97.
[109]Gross,J.L.& T.W.Tucker.Topolgical Graph Theory[M],Canada:A Wiley-Interscience Publication,1987.
[110]Richter,R.B.& J.(?)ir(?).The crossing number of K_(3,n) in a surface[J].Journal of Graph Theory,1996,21(1):51-54.
[111]Huang,Y.& T.Zhao.The crossing number of K_(1,4,n)[J].Discrete Math.,doi:10.1016/j.disk.2006.12.002.
[112]Mei H.& Y.Huang.The crossing number of K_(1,5,n)[J].International J.Math.Combin.,2007,1(1):33-34.
[113]黄元秋,赵霆雷.关于完全3-部图K_(1,6,n)的交叉数[J].应用数学学报,2006,29(6):1046-1053.
[114]Huang,Y.& T.Zhao.On the crossing number of the complete tripartite graph K_(1,8,n)[J].Acta Mathematica Scientia(A),2006,26(7):1115-1122.
[115]王晶,黄元秋.完全3-部图K_(1,10,n)的交叉数[J].高校应用数学学报,2008,23(3):349-356.
[116]黄元秋,王晶,何小年.完全3-部图K_(1,m,n)的交叉数.已投稿.
[117]黄元秋,赵霆雷.关于完全3-部图K_(2,4,n)的交叉数.已投稿.
[118]Bokal,D.On the crossing number of Cartesian product with path[J].Journal of Combinatorial Theory(Series B),2007,97:381-384.
[119]肖文兵,黄元秋.一类笛卡尔积图的交叉数[J].湖南师范大学学报(自然科学版),2004,4:3-7.
[120]肖文兵,王红专,黄元秋.一个六阶图与星图S_n的笛卡尔积图的交叉数[J].湖南文理学院学报,2004,16(4):15-17.
[121]周智勇,肖文兵,黄元秋.星图S_5及5个六阶图与路的笛卡尔积图的交叉数[J].湖南文理学院学报,2007,19(1):1-4.
[122]周智勇,黄元秋.笛卡尔积图K_(3,3)×P_n的交叉数[J].湖南师范大学学报(自然科学版),2007,30(1):31-34.
[123]于平,黄元秋.P_m与W_n的笛卡尔积图的交叉数[J].湖南师范大学学报(自然科学版),2005.1:14-16.
[124]何小年,黄元秋.一类笛卡尔积图的交叉数[J].吉首大学学报(自然科学版),2005,1:8-11
[125]Wang,J.& Y.Huang.The crossing number of the Cartesian products of paths with some 6-vetex graphs[J].吉首大学学报(自然科学版),2005,2:9-13.
[126]袁梓瀚,黄元秋.C_m+{e_1},G_m+{e_1}+{e_2}与路P_n的笛卡尔积图的交叉数[J].吉首大学学报(自然科学版),2007,3:16-19.
[127]袁梓瀚,黄元秋.C(6,2)＼{e_1}与路Pn的笛卡尔积图的交叉数[J].数学理论与应用,2007.2:49-51.
[128]Lv,S.& Y.Huang.On the crossing number of products of paths with some 6-vetex graphs[J].湖南文理学院学报(自然科学版),2007,1:22-55.
[129]Lv,S.& Y.Huang.the crossing number of K_5×S_n[J].J.Math.and expos.,2008,28(3):445-459.
[130]王晶,黄元秋.K_(2,4)×P_n的交叉数[J].数学物理学报(中文版),2008,2:81-97.
[131]Glebsky,L.Y.& G.Salazar.The crossing number of C_m × C_n is as conjectured for n ≥ m(m + 1)[J].Journal of Graph Theory,2004,47(1):53-72.
[132]袁梓瀚,黄元秋.C(12,2)×P_n的交叉数.投ARS Combinatoria.
[133]袁梓瀚,黄元秋.C(9,2)×P_n的交叉数.已投高校应用数学学报.
[134]袁梓瀚,黄元秋.K_(1,1,2,2)×P_n的交叉数.高校应用数学学报,已接受.
[135]袁梓瀚,黄元秋.7阶循环图C(7,2)×P_n的交叉数[J].数学进展,2007,2:245-254.
[136]袁梓瀚,王晶,黄元秋.10阶循环图C(10,2)×P_n的交叉数,已投应用数学学报.
[137]Yuan,Z.& l.Tang,Y.Huang.The crossing number of C(8,2) ×P_n[J].Graphs and Combinatorics,2008,24:597-604.
[138]Tang,L.& S.Lv,Y.Huang.The Crossing Number of Cartesian Products of Complete Bipartite Graphs K_(2,m) with Paths P_n[J].Graphs and Combinatorics,2007,23:659-666.
[139]贺佩玲,黄元秋.一个六阶图F与sn的笛卡尔积交叉数[J].吉林师范大学学报(自然科学版),2008,4:14-16.
[140]B.Li & L.Zhang,Y.Huang.The crossing number of cartesian product of star with a 6-vertex graph[J].湖南文理学院学报(自然科学版),2008,20(2):7-11.
[141]张莉茜,李波,黄元秋.关于六阶图与星的笛卡儿积交叉数[J].湖南文理学院学报(自然科学版),2008,20(1):16-19.
[142]杨希武.Flower Snark和K_6＼{e)×P_n的交叉数[D].大连:大连理工大学,2008:40-47.
[143]李婷.关于积图与联图的交叉数问题研究[D].北京:北京师范大学,2008:5-8.
[144]马祖强,蔡俊亮.W_5×P_n的交叉数[J].应用数学学报,2008,31(4):615-623.
[145]赵琳.关于图的交叉数[D].北京:北京交通大学,2007:9-11.
[146]张建根.几类图的交叉数及其相关性质[D].北京:北京交通大学,2008:12-15.
[147]贺佩玲,黄元秋.一个六阶图与路的笛卡尔积交叉数[J].湖南人文科技学院学报,2007,6:3-4.