Crossing Number of the Cartesian Product of a 6-Vertex Graph with S*n

Abstract

Abstract: There are several known exact results on the crossing numbers of Cartesian products of stars with “small” graphs. In this paper we extend these results to the cartesian products of a specific 6-vertex with the star K1，n and determine its crossing number is z(6,n)+4n. In addition we give the crossing number of the graph Hn obtained by adding 2 edges to the graphin K2,4,n such a way that these new edges respectively join a pair of vertices of degree n+2 of the graph K2,4,n.

Key words: graph, cartesian product, crossing number, star

ZHANG Li-xi, LI Bo, HUANG Yuan-Qiu. Crossing Number of the Cartesian Product of a 6-Vertex Graph with S*n[J]. journal6, 2008, 29(5): 23-29.

References

[1] HARARY F.Graph Theory [M].Addision-Wesley，Reading，MA，1969.

[2] GARARY M R,JOHNSON D S.Crossing Number is NP-Complete [J],SIAM J. Algebric Discrete Methods，1993，(4):312-316.

[3] HARARY F,KLAITEN P C,SCHWENK A J.Toroidal Graphs with Arbitrarily High Crossing Numbers [J].Nana. Math.,1973,6:58-67.

[4] DEAN A M,RICHTER R B.The Crossing Number of C4×Ｃ４ [M].J. Graph Theory，1995,19:125-129.

[5] KLE M.The Crossing Number of K2,3×C3 [J].Discrete Math.，2002,251:109-117.

[6] BEINEKE L W,RINGEISEN R D.On the Crossing Numbers of Products of Cycles and Graphs of Order Four[J].J. Graph Theory，1980，4:145-155.

[7] JENDROL’S,ERBOV M.On the Crossing Numbers of Sm×Pn and Sm×Cn [J].as. Pest. Mat.，1982，107:225-230.

[8] KLE M.The Crossing Numbers of Products of Paths and Stars with 4-Vertex Graphs[J].J. Graph Theory，1994,18:605-614.

[9] KLE M.The Crossing Numbers of Certain Cartesian Products [J].Discuss. Math. Graph Theory，1995，15:5-10.

[10] KLE M.The Crossing Number of K5×Pn [J].Tatra Moutains Math. Publ.，1999，18:63-68.

[11] KLE M.The Crossing Number of Cartesian Products of Paths with 5-Vertex Graphs [J].Discrete Math.，2001，233:353-359.

[12] KLE M.The Crossing Number of K2,3×Pn and K2,3×Ｓn [J].Tatra Moutains Math. Publ.,1996，(9):51-56.

[13] KLE M.On the Crossing Numbers of Cartesian Products of Stars and Paths or Cycles [M].Math. Slovaca，1991，41:113-120.

[14] KLE M.On the Crossing Numbers of Products of Stars and Graphs of Order Five [J].Graphs and Combinatorics， 2001,17:289-294.

[15] KLE M，KOCU〖KG-*2〗＇ROV A.The Crossing Numbers of Products of 5-Vertex Graphs with Cycles [J].Discrete Math.，2007,307:1395-1403.

[16] PENG Y H,YIEW Y C.The Crossing Number of P(3,1)×Pn [J].Discrete Math.，2006,306:1 941-1 946.

[17] RINGEISEN R D,BEINEKE L W.The Crossing Number of C3×Cn [J].J. Combin. Theory Ser. B，1978,24:134-136.

[18] KLE M,RICHTER R B,STOBERT I.The Crossing Number of C5×Cn [J].J. Graph Theory，1996,22:239-243.

[19] RICHTER R B,SALAZAR G.The Crossing Number of C6×Cn [J].Australas. J. Combin.，2001,23:135-143.

[20] GLEBSKY L Y,SALAZAR G.The Crossing Number of Cm×Cn is as Conjectured for n≥m(m+1) [J].J. Graph Theory，2004，47:53-72.

[21] BOKAL D.On the Crossing Numbers of Cartesian Products with Paths [J].J. Combin. Theory Ser B.，2007，97:381-384.

[22] KLEITMAN D J.The Crossing Number of K5,n [J].J. Comb. Theory，1970，9:315-323.

[23] XIAO Wen-bing，WANG Hong-zhuan，HUANG Yuan-qiu，The Crossing Number of the Cartesian Product of a 6-Vertex Graph with Sn [J].Journal of the University of Arts and Scince,2004，16(4):15-17.