摘要
图的交叉数问题,起源于二战期间Pual Tur(?)n在砖厂碰到的一个实际难题,逐渐发展成为图论学科中非常活跃的一个分支,吸引着国内外许多学者的关注.然而,确定一般图的交叉数是一个NP-完全问题,因此,到目前为止有关交叉数的结果比较少,仅限于一些特殊简单图的交叉数.甚至在许多情况下,试图找出图的交叉数的一个好的上界或下界也很困难.本文运用组合方法和归纳思想以及反证法,确定了一些特殊图类,如广义Petersen图P(3k,k),循环图C(3k-1;{1,k}),W_m×P_n,两个特殊的六阶图与星S_n的笛卡尔积图,星图S_m与路P_n、星图S_m与圈C_n的联图的交叉数的精确值或者其上、下界,并试图研究交叉数的一般性质,从画法上着手得到了一个好画法为最优画法的充分条件.全文由9个章节组成.
第一章较为详细地交代了交叉数的起源,研究工作的理论与实际意义,以及目前交叉数研究在国内外的发展动态.同时还简要介绍了本文的主要结构.
第二章介绍了阅读本文所要用到的图的交叉数方面的基本概念和预备知识.
第三章得到了当k≥4时,广义Petersen图P(3k,k)的交叉数为k.
第四章讨论了当k≥3时,循环图C(3k-1;{1,k})交叉数的上界和下界.
第五章确定了对任意的m≥3和n≥1,轮W_m与路P_n的笛卡尔积图的交叉数.
第六章对两个特殊的六阶图与星S_n的笛卡尔积图的交叉数进行了研究.
第七章讨论了当m=3,4,5时,星S_m与路P_n的联图的交叉数,和当m=3,4时,星S_m与圈C_n的联图的交叉数.
第八章研究图的交叉数的一般性质,并从画法上着手得到了一个好画法为最优画法的充分条件.
第九章给出了本文的总结和对未来工作的展望.
The crossing number of graphs comes from the Pual Tur(?)n's brick factory problem during the World WarⅡ, and it becomes a very active branch in Graph Theory, many authors have studied this area. However, determining the crossing number of graphs is NP-complete. Because of its difficulty, there are only very scarce special classes of graphs whose crossing numbers are determined. Even in some cases, it is very difficult to find the upper or lower bounds of the crossing number of graphs. In this paper, we study the crossing number of some special graphs, such as the generalized Petersen graph P(3k,k), the circulant graph C(3k-1;{1,k}), the Cartesian product of S_n with two special 6-vertex graphs, W_m×P_n,S_m∨P_n,S_m∨C_n,etc. The paper is consist of 9 chapters:
In chapter one, we introduce the origins and backgrounds of the crossing number, its theorical and practical meanings, and its development around the world.
Chapter two gives some conceptions and properties of the crossing number, and introduces the required knowledge for reading this paper.
Chapter three determines that the crossing number of the generalized Petersen graph P(3k,k) is k for arbitrary k≥4.
Chapter four studies the upper and lower bounds of the crossing number of the circulant graph C(3k-1;{1, fe}) for k≥3.
Chapter five investigates the crossing number of Cartesian product of the wheel W_m with path P_n for m≥3 and n≥1.
In chapter six, the crossing numbers of the Cartesian product of S_n with two special 6-vertex graphs are determined.
Chapter seven studies the crossing numbers of S_m∨P_n for m= 3,4,5 and for all n, and the crossing numbers of S_m∨C_n for m = 3,4 and for all n.
Chapter eight investigates the general property of the crossing number of graphs, and presents a sufficient condition to enforce a good drawing to be optimal.
In the last chapter, we make some conclusions of our research work and put forward some relative problems which we will go ahead.
引文
[1] Abrego, B. M. and Silvia Fernandez-Merchant, A lower bound for the rectilinear crossing number[J], Graphs and Combinatorics, 21 (2005), 293-300.
[2] Adamsson, J. and R. B. Richter, Arrangements, circular arrangements, and the crossing number of C_τ × C_n[J],J.Combin. Theory Ser. B, 90 (2004), 21-39.
[3] Aichholzer, O.Graz, F. Aurenhammer Graz,H.Krasser Graz, On the crossing number of complete graphs[J], Computing, 76 (2006), 165-176.
[4] Ajtai, M., V. Chv(?)tal, M. Newborn, E. Szemer(?)di,Crossing-free subgraphs, in:Theory and Practice of Combinatorics, in: North-Holland and Math. Stud.[J],vol. 60, Elsevier, Amsterdam, 1982, 9-12.
[5] Akka, D.G.', S. Jendro(?), M. Kle(?)(?) and S. V. Panshetty, On line graphs with crossing number 2[J], Univ. Beograd Publ.Elektrotehn Fak-Ser Math.,8 (1997), 3-8.
[6] Anderson, M. S., R. B. Richter, P. Rodney, Crossing number of C_6 × C_6[J],Congressus Numerantium, 118 (1996), 97-107.
[7] Anderson, M. S., R. B. Richter, P. Rodney, The crossing number of C_7 × C_7[J],Cong Numer., 125 (1997), 97-117.
[8] Archdeacon, D. and R. Bruce Richter, On the parity of crossing numbers[J], J.Graph Theory, 12 (3) (1988), 307-310.
[9] Asano, K., The crossing number of K_(1,3,n) and K_(2,3,n)[J],J.Graph Theory, 10(1986),1-8.
[10] Beineke, L. W. and R. D. Ringeisen, On the crossing numbers of products of cycles and graphs of order four[J], J. Graph Theory, 4 (1980), 145-155.
[11] Bhatt, S. N. and F. T. Leighton, A framework for solving VLSI graph layout problems[J], J. Comput. System Sci., 28 (1984), 300-343.
[12] Bienstock, D. and N. Dean, Bounds for rectilinear crossing numbers[J], J. Graph Theory, 17 (1993), 333-348.
[13] Bokal, D., On the crossing numbers of Cartesian products with paths[J}, J.Combin. Theory Ser B., 97 (2007), 381-384.
[14] Bokal, D., On the crossing numbers of Cartesian products with trees[J], J.Graph Theory, 56 (2007), 287-300.
[15] Brodsky, A., S. Durocher, E. Genthner, The rectilinear crossing number of K_(10) is 62[J], The Electronic J. Combinatorics 8, Research paper 23 (2001).
[16] Brodsky, A., Stephane Durocher, Ellen Gethner, Toward the rectilinear crossing number of K_n:new drawings, upper bounds, and asymptotics[J], Discrete Mathematics, 262 (2003), 59-77.
[17] 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.
[18] 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.
[19] Dean, A. M. and R. B. Richter, The crossing number of C_4 × C_4[J], J. Graph Theory, 19 (1995), 125-129.
[20] Eggleton, R. B. and R. P. Guy, The crossing number of the n-cube[J], Amer.Math. Soc.Notices, 17 (1970), 757.
[21] Erdos, P. and R. K. Guy, Crossing number problems[J], Am. Math. Month., 80(1973), 52-58.
[22] Exoo, G., F.Harary, J.Kabell, The crossing number of some generalized Petersen graphs[J], Math. Scand., 48 (1981), 184-188.
[23] Faria, L., C. M. H. de Figueiredo, Oh Eggleton and Guy conjectured upper bound for the crossing number of the n-cube[J], Mathematics Slovaca, 50(2000), 271-287.
[24] Faria, L., Celina Miraglia Herrera de.Figueiredo, Ondrej S(?)kora, Imrich Vrt'o,An improved upper bound on the crossing number of the hypercube[J], J. Graph Theory, (2008), doi:10.1002/jgt.20330.
[25] Fiorini, S., On the crossing number of generalized Petersen graphs[J], Ann.Disrete Math., 30 (1986), 221-242.
[26] Fox, J. and C. D. T(?)th, On the decay of crossing numbers[J], Journal of Combinatorial Theory, Series B, 98 (2008), 33-42.
[27] Garary, M. R. and D. S. Johnson, Crossing number is NP-complete[J], SIAM J.Algebric Discrete Methods, 4 (1993), 312-316.
[28] Garcia-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.
[29] Glebsky, L. Y. and G. Salazar, The crossing number of C_m × C_n is as conjectured for n ≥ m(m + 1)[J], J.Graph Theory, 47 (2004), 53-72.
[30] Gross, J. L. and T. W. Tucker, Topological Graph Theory[M],Wiley-Interscience Publication, New York, pp:19-20, (1987).
[31] 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.
[32] Guy, R. K., Crossing numbers of graphs[J],In Graph Theory and Applications,Lecture Notes in Mathematics, vol. 303, Spring-Verlag, Heidelberg, Berlin, NewYork, May 1972, 111-124.
[33] Guy, R. P., Latest results on crossing numbers, In Proc.Recent Trends in Graph Theory[J],Lecture Notes in Mathematics, 186 (1971), 143-156.
[34] Guy, R.,T.Jenkyns, J. Schaer, The toroidal crossing number of the complete graph[J], J. Combin. Theory, 4 (1968), 376-390.
[35] Guy, R. K. and T. A. Jenkyns, The toroidal crossing number of K_(m,n)[J],J.Combin. Theory, 6 (1969), 235-250.
[36] Hao, R. and Y. Liu, New upper bounds on crossing number of circular graphs[J],OR Transactions, 3 (1999),1-6.
[37] Harary, F.,P.C.Kainen, A.J.Schwenk, Toroidal graphs with arbitrarily high crossing numbers[J], Nana Math., 6 (1973), 58-67.
[38] Harary, F., Graph Theory[M], Addision-Wesley, Reading, MA, 1969.
[39] Harborth, H.,(U|¨)ber die Kreuzungszahl vollst(a|¨)ndiger, n-geteilter Graphen[J],Math. Nachr., 48 (1971), 179-188.
[40] 何小年,关于图的交叉数研究[D],硕士学位论文,湖南师范大学,(2006).
[41] 何小年,黄元秋,一类笛卡尔积图的交叉数[J],吉首大学学报(自然科学版),26(1)(2005),8-11.
[42] Hlin(?)n(?), P., Crossing-number critical graphs have bounded path-width[J], Journal of Combinatorial Theory, Series B, 88 (2003), 347-367.
[43] Hlin(?)n(?), P., Crossing number is hard for cubic graphs[J], Journal of Combinatorial Theory, Series B, 96 (2006), 455-471.
[44] Ho, P. T., The crossing number of K_(1,m,n)[J], Discrete Mathematics, 308 (2008),5996-6002.
[45] Ho, P. T., The crossing number of some complete multipartite graphs[J], Util.Math., (in press).
[46] Ho, P. T., The crossing number of C(3k +1;{1,k})[J], Discrete Math., 307(2007), 2771-2774.
[47] Ho, P. T., The crossing number of K_(4,n) on the real projective plane[J], Discrete Mathematics, 304 (2005), 23-33.
[48] Ho, P. T., The toroidal crossing number of K_(4,n)[J],Discrete Mathematics,(2008), doi:10.1016/j.disc.2008.09.029.
[49] Huang, Y. and T. Zhao, The crossing number of K_(1,4,n) Discrete Mathematics, 308 (2008), 1634-1638.
[50] Huang, Y. and T. Zhao, The crossing number of K_(2,4,n)[J],已投稿.
[51] 黄元秋,赵霆雷,关于完全3-部图K_(1,6,n)的交叉数[J],应用数学学报,29(6)(2006),1046-1053.
[52] Huang, Y. and T. Zhao, On the crossing number of the complete tripartite graph K_(1,8,n)[J], Acta Mathematics Scientia,26A (7) (2006), 1115-1122.
[53] Huang, Y., and T. Zhao, The crossing number of the line graphs[J], Submitted.
[54] Jendrol', S. and M.(?)(?)erbov(?),On the crossing numbers of S_m × P_n and S_m × C_n[J],(?)as. Pest. Mat., 107 (1982), 225-230.
[55] Jendrol, S. and Mari(?)n Kle(?)(?),On the graphs whose line graphs have crossing number one[J], Journal of Graph Theory, 37 (2001), 181-188.
[56] Jozef (?)ir(?)(?),Infinite families of crossing-critical graphs with a given crossing number[J], Discrete Mathematics, 48 (1984), 129-132.
[57] Juarez, H. A. and G. Salazar, Drawings of C_m × C_n with one disjoint family Ⅱ[J], Journal of Combinatorial Theory, Series B, 82 (2001), 161-165.
[58] 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.
[59] Klav(?)ar, S. and B. Mohar, Crossing numbers of Sierpi(?)ski-like graphs[J], J Graph Theory, 50 (2005), 186-198.
[60] Kleitman, D. J., The crossing number of K_(5,n)[J], J.Comb.Theory, 9 (1970),315-323.
[61] 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.
[62] Klerk, E. D., J. Maharry, D. V. Pasechnik, R. Bruce Richter, G. Salazar, Improved bounds for the crossing numbers of K_(m,n) and K_n[J],SIAM Discrete Math., 20 (1) (2006), 189-202.
[63] 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.
[64] Kle(?)(?),M., R. B. Richter, I. Stobert, The crossing number of C_5 × C_n[J],J.Graph Theory, 22 (1996), 239-243.
[65] Kle(?)(?), M., The crossing number of K_(2,3) × C_3[J],Discrete Math., 251 (2002),109-117.
[66] Kle(?)(?),M., The crossing numbers of products of paths and stars with 4-vertex graphs[J], J. Graph Theory, 18 (1994), 605-614.
[67] Kle(?)(?),M., The crossing numbers of certain Cartesian products[J], Discuss.Math.-Graph Theory, 15 (1995), 5-10.
[68] Klesc, M., The crossing number of K_5 × P_n[J],Tatra Moutains Math. Publ.,18 (1999), 63-68.
[69] Kle(?)(?),M., The crossing number of Cartesian products of paths with 5-vertex graphs[J], Discrete Math., 233 (2001), 353-359.
[70] Kle(?)(?),M., The crossing number of K_(2,3) × P_n and K_(2,3) × S_n[J],Tatra Moutains Math. Publ., 9 (1996), 51-56.
[71] Kle(?)(?),M., On the crossing numbers of Cartesian products of stars and paths or cycles[J], Math. Slovaca, 41 (1991), 113-120.
[72] Kle(?)(?),M.,On the crossing numbers of products of stars and graphs of order five[J], Graphs and Combinatorics, 17 (2001), 289-294.
[73] Kle(?)(?),M. and A. Koc(?)rov(?),The crossing numbers of products of 5-vertex graphs with cycles[J], Discrete Math., 307 (2007), 1395-1403.
[74] Kolman, P. and Ji(?)(?) Matou(?)ek, Crossing number, pair-crossing number, and expansion[J], Journal of Combinatorial Theory, Series B, 92 (2004), 99-113.
[75] 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.
[76] Leighton, F. T., New lower bound techniques for VLSI[J], Math. System Theory, 17 (1984), 47-70.
[77] Lin, X., Y. Yang, J. Lu, X. Hao, The crossing number of C(mk;{1,k})[J],Graphs and Combinatorics, 21 (2005), 89-96. [78] Lin, X., Y. Yang, J. Lu, X. Hao, The crossing number of C(n;{1,(?) -1})[J],Util.Math., 71 (2006), 245-255.
[79] Liu, T. and Y. Liu, On the crossing number of circular graphs[J], OR Transactions, 4 (1998), 31-38.
[80] Lovre(?)i(?) Sara(?)in, M., The crossing number of the generalized Petersen graph P(10,4) is four[J], Math. Slovaca, 47 (2) (1997), 189-192.
[81] 卢俊杰,任韩,马登举,C(m,3)的交叉数[J],系统科学与数学,24(4)(2004),504-512.
[82] Lv,S.and Y. Huang, On the Crossing Numbers of K_5 × S_n,[J] Journal of Mathematical Research Exposition, 28 (3) 2008, 445-459.
[83] Lv, S., L. Tang, Y. Huang, The toroidal crossing number of K_(4,n)[J],已投稿.
[84] Ma, D., H. Ren, J. Lu, The crossing number of the circular graph C(2m + 2,m)[J], Discrete Mathematics, 304 (2005), 88-93.
[85] 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.
[86]马登举,任韩,卢俊杰,广义Petersen图G(2m+1,m)的交叉数[J],华东师范大学学报,1(2005),34-39.
[87] Madej, T., Bounds for the crossing number of the n-cube[J], J. Graph Theory,15 (1991), 81-97.
[88] Martin Kochol, Construcion of crossing-critical graphs [J], Discrete Mathematics, 66 (1987), 311-313.
[89] Mcquillan, D. and R. B. Richter, On the crossing number of certain generalized Petersen graphs[J], Ann. Discrete Math., 104 (1992), 311-320.
[90] 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.
[91] Mei, H. and Y. Huang, The crossing number of K_(1,5,m)[J],International Journal of Mathematical combinatorics, 1 (2007), 33-44.
[92] Montaron, B., An improvement of the crossing number bound[J], J Graph Theory, 50 (2005),43-54.
[93] Oporowski, B. and David Zhao, Coloring graphs with crossings[J], Discrete Mathematics, (2008), doi:10.1016/j.disc.2008.07.040.
[94] Pach, J., J. Spencer, G. T(?)th, New bounds on crossing numbers[J], Discrete Comput.Geom.,24 (2000), 623-644.
[95] Pach, J., R. Radoi(?)i(?),G.Tardos, G. T(?)th, Improving the Crossing Lemma by finding more crossings in sparse graphs[J], Discrete Comput. Geom., 36 (2006),527-552.
[96] Pach, J. and G. T(?)th, Graphs drawn with few crossings per edge[J], Combinatorica, 17 (3) (1997), 427-439.
[97] Pach, J., Which crossing number is it anyway?[J], Journal of Combinatorial Theory, Series B, 80 (2000), 225-246.
[98] Pelsmajer, M. J., Marcus Schaefer, Daniel (?)efankovi(?),Removing even crossings [J],J. Combin. Theory Ser. B, (2006), doi:10.1016/j.jctb.2006.08.001.
[99] Pelsmajer, M. J., Marcus Schaefer, Daniel (?)efankovi(?),Odd crossing number and crossing number are not the same[J], Discrete Comput. Geom., 39 (2008),442-454.
[100] Peng, Y. H. and Y. C. Yiew, The crossing number of P(3,1) × P_n[J], Discrete Math., 306 (2006), 1941-1946.
[101] Pinontoan, B. and R. B. Richter, Crossing numbers of sequences of graphs Ⅱ:planar tiles[J], J Graph Theory, 42 (2003), 332-341.
[102] Richter, R. B., Cubic graphs with crossing number two[J], Journal of Graph Theory, 12 (3) (1988), 363-374.
[103] 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.
[104] Richter, R. B. and C. Thomassen, Relations between crossing numbers of complete and complete bipartite graphs[J], The American Mathematical Monthly,104(2) (1997), 137-137.
[105] Richter, R. B. and C. Thomassen, Intersection of curve systems and the crossing number of C_5 × C_5[J],Discrete and Computational Geometry, 13 (1995), 149-159.
[106] Richter, R. B. and G. Salazar, The crossing number of C_5 × C_n[J], Australas.J.Combin.,23 (2001), 135-143.
[107] Richter, R. B. and G. Salazar, The crossing number of P(N,3)[J], Graphs and Combinatorics, 18 (2002), 381-394.
[108] Richter, R. B. and J.(?)ir(?)(?),The crossing number of K_(3,n) in a surface[J], Journal of Graph Theory, 21 (1996),51-54.
[109] Ringeisen, R. D., L. W. Beineke, The crossing number of C_3 × C_n[J],J.Combin.Theory Ser. B,24 (1978),134-136.
[110] Riskin, A., The genus 2 crossing number of K_9[J],Discrete Mathematics,145(1995), 211-227.
[111] Riskin, A., On the nonembeddability and crossing numbers of some toroidal graphs on the Klein bottle[J], Discrete Mathematics, 234 (2001), 77-88.
[112] Riskin, A., On the nonembeddability and crossing numbers of some Kleinical polyhedral maps on the torus[J], Graphs and Combinatorics, 21 (2005), 131-135.
[113] Salazar, G., On the crossing number of C_m × Cn[J], J. Graph Theory, 28 (1998),163-170.
[114] Salazar, G., A lower bound for the crossing number of C_m × C_n[J], J Graph Theory, 35 (2000), 222-226.
[115] Salazar, G., Drawings of C_m × C_n with one disjoint family[J], Journal of Combinatorial Theory, Series B, 76 (1999), 129-135.
[116] Salazar, G., On the crossing numbers of loop networks and generalized Petersen graphs[J],Discrete Math., 302 (2004), 243-253.
[117] Salazar, G., On a crossing number result of Richter and Thomassen[J], Journal of Combinatorial Theory, Series B, 79 (2000), 98-99.
[118] Salazar, G., Infinite families of crossing-critical graphs with given average degree, Discrete Mathematics[J], 271 (2003), 343-350.
[119] Salazar, G. and E.Ugalde, An improved bound for the crossing number of C_m × C_n :a self-contained proof using mostly combinatorial arguments[J],Graphs and Combinatorics, 20 (2004), 247-253.
[120] Sedlacek, J., Some properties of interchange graphs, Theory of Graphs and its Applications[M], M. Fiedler, (Editor), Academic Press, New York,(1962),145-150.
[121] Shahrokhi, F., O.S(?)kora,L.A.Sz(?)kely,I.Vr(?)o,Intersection of curves and crossing number of C_m × C_n on surfaces[J], Discrete Comput Geom., 19 (2)(1998), 237-247.
[122] Shengjun, P. and R. Bruce Richter, The crossing number of K_(11) is 100[J], J.Graph Theory, 56 (2007), 128-134.
[123] Sykora,O.and I.Vrt'o,On the crossing number of the hypercube and cube connected cycles[J], BIT, 33 (1993), 232-237.
[124] Sz(?)kely, L. A., A successful concept for measuring non-planarity of graphs: The crossing number[J], Discrete Math., 276 (2004), 331-352.
[125] 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,23 (2007), 659-666.
[126] Tang, L., J.Wang, Y. Huang, The crossing number of the join of C_m and P_n[J],International J. Math. Com.,1(2007), 110-116.
[127] Tur(?)n,P., A note of welcome[J], J.Graph Theory,1(1977),7-9.
[128] Tutte, W. T., Toward a theory of crossing numbers[J], J.Combinatorial Theory,8 (1970), 45-53.
[129] 王晶,黄元秋,完全3-部图K_(1,10,n)的交叉数[J],高校应用数学学报,23(3)(2008),349-356.
[130] 王晶,关于一些图类的交叉数[D],硕士学位论文,湖南师范大学,(2006).
[131] 王晶,黄元秋,K_(2,4)×P_n的交叉数[J],数学物理学报,28A(2008),251-255.
[132] 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.
[133] Woodall, D. R., Cyclic-order graphs and Zarankiewicz's crossing number conjecture [J], J. Graph Theory, 17 (1993),657-671.
[134] 肖文兵,黄元秋,一类笛卡尔积图的交叉数[J],湖南师范大学学报(自然科学版),4(2004),3-7.
[135] Yang, Y., X. Lin, J. Lu, X. Hao, The crossing number of C(n;{1,3})[J], Discrete Math., 289 (2004), 107-118.
[136] 杨元生,王丹,陆维明,四正则图的交叉数[J],软件学报,13(12)(2002),2259-2266.
[137] 于平,黄元秋,P_m与W_n的笛卡尔积图的交叉数[J],湖南师范大学学报(自然科学版),1(2005),14-16.
[138] 袁梓瀚,黄元秋,刘金旺,7阶图C(7,2)与P_n的笛卡尔积的交叉数[J],数学进展,37(2)(2008),245-253.
[139] Zarankiewicz, K., On a problem of P.Tur(?)n concerning graphs[J], Found. Math.,41 (1954), 137-145.
[140] Zheng, W., X. Lin, Y. Yang, C. Cui, On the crossing number of K_m × P_n[J],Graphs and Combinatorics, 23 (2007), 327-336.
[141] Zheng, W., X. Lin, Y. Yang, The crossing number of K_(2,m) × P_n[J], Discrete Math.,308 (2008), 6639-6644.
[142] 周智勇,黄元秋,笛卡尔积图K_(3,3)×P_n的交叉数[J],湖南师范大学学报(自然科学版),30(1)(2007),31-34.