The crossing number of G ▭ C n for the graph G on six vertices

Mathematica Slovaca - 2011
Emília Draženská1
1Department of Mathematics Faculty of Electrical Engineering and Informatics, Technical University, Košice, Slovak Republic

Tóm tắt

The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. The crossing numbers of G□C n for some graphs G on five and six vertices and the cycle C n are also given. In this paper, we extend these results by determining the crossing number of the Cartesian product G □ C n , where G is a specific graph on six vertices.

Từ khóa


Tài liệu tham khảo

ADAMSON, J.— RICHTER, R. B.: Arrangements, circular arrangements and the crossing number of C 7 × C n, J. Combin. Theory Ser. B 90 (2004), 21–39.

ANDERSON, M.— RICHTER, R. B.— RODNAY, P.: The crossing number of C 6 × C 6, Congr. Numer. 118 (1996), 97–107.

ANDERSON, M.— RICHTER, R. B.— RODNAY, P.: The crossing number of C 7 × C 7, Congr. Numer. 125 (1997), 97–117.

BEINEKE, L. W.— RINGEISEN, R. D.: On the crossing numbers of products of cycles and graphs of order four, J. Graph Theory 4 (1980), 145–155.

DEAN, A. M.— RICHTER, R. B.: The crossing number of C 4 × C 4, J. Graph Theory 19 (1995), 125–129.

DRAŽENSKÁ, E— KLEŠČ, M.: The crossing numbers of products of cycles with 6-vertex trees, Tatra Mt. Math. Publ. 36 (2007), 109–119.

GLEBSKY, L. Y.— SALAZAR, G.: The crossing number of C m × C n is as conjectured for n ≥ m(m+ 1), J. Graph Theory 47 (2004), 53–72.

HARARY, F.— KAINEN, P. C.— SCHWENK, A. J.: Toroidal graphs with arbitrarily high crossing numbers, Nanta Math. 6 (1973), 58–67.

JENDROĽ, S.— ŠČERBOVÁ, M.: On the crossing numbers of S m × P n and S m × C n, Časopis Pěst. Mat. 107 (1982), 225–230.

KLEŠČ, M.: On the crossing numbers of Cartesian products of stars and paths or cycles, Math. Slovaca 41 (1991), 113–120.

KLEŠČ, M.: The crossing number of (K 4 − e) × C 3. In: Proc. International Scientific Conference on Mathematics (Herl’any, 1999), Univ. Technol. Košice, Košice, 2000, pp. 106–109.

KLEŠČ, M.: The crossing numbers of Cartesian products of paths with 5-vertex graphs, Discrete Math. 233 (2001), 353–359.

KLEŠČ, M.: The crossing number of K 2,3 × C 3, Discrete Math. 251 (2002), 109–117.

KLEŠČ, M.: Some crossing numbers of products of cycles, Discuss. Math. Graph Theory 25 (2005), 197–210.

KLEŠČ, M.— RICHTER, R. B.— STOLBERT, I.: The crossing number of C 5 × C n , J. Graph Theory 22 (1996), 239–243.

KLEŠČ, M.— KOCÚROVÁ, A.: The crossing number of products of 5-vertex graphs with cycles, Discrete Math. 307 (2007), 1395–1403.

RICHTER, R. B.— SALAZAR, G: The crossing number of C 6×C n, Australas. J. Combin. 23 (2001), 135–144.

RINGEISEN, R. D.— BEINEKE, L. W.: The crossing number of C 3 × C n, J. Combin. Theory Ser. B 24 (1978), 134–136.

Thông tin
Thông tin xuất bản

Mathematica Slovaca

Thông tin tác giả