DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 19(1) (1999) 59-69
DOI: https://doi.org/10.7151/dmgt.1085

THE CROSSING NUMBERS OF PRODUCTS OF A 5-VERTEX GRAPH WITH PATHS AND CYCLES

Marián Klešč

Department of Mathematics
Faculty of Electrical Engineering and Informatics
Technical University, 042 00 Košice, Slovak Republic
e-mail: Klesc@ccsun.tuke.sk

Abstract

There are several known exact results on the crossing numbers of Cartesian products of paths, cycles or stars with ``small'' graphs. Let H be the 5-vertex graph defined from K5 by removing three edges incident with a common vertex. In this paper, we extend the earlier results to the Cartesian products of H ×Pn and H ×Cn, showing that in the general case the corresponding crossing numbers are 3n-1, and 3n for even n or 3n+1 if n is odd.

Keywords: graph, drawing, crossing number, path, cycle, Cartesian product.

1991 Mathematics Subject Classification: 05C10, 05C38.

References

[1] D. Archdeacon, R.B. Richter, On the parity of crossing numbers, J. Graph Theory 12 (1988) 307-310, doi: 10.1002/jgt.3190120302.
[2] L.W. Beineke, R.D. Ringeisen, On the crossing numbers of products of cycles and graphs of order four, J. Graph Theory 4 (1980) 145-155, doi: 10.1002/jgt.3190040203.
[3] F. Harary, Graph Theory (Addison - Wesley, Reading, MA, 1969).
[4] S. Jendrol', M. S cerbová, On the crossing numbers of Sm ×Pn and Sm ×Cn, Casopis pro pestování  matematiky 107 (1982) 225-230.
[5] M. Klešč, On the crossing numbers of Cartesian products of stars and paths or cycles, Mathematica Slovaca 41 (1991) 113-120.
[6] M. Klešč, The crossing numbers of products of paths and stars with 4-vertex graphs, J. Graph Theory 18 (1994) 605-614.
[7] M. Klešč, The crossing numbers of certain Cartesian products, Discuss. Math. Graph Theory 15 (1995) 5-10, doi: 10.7151/dmgt.1001.
[8] M. Klešč, The crossing number of K2,3 ×Pn and K2,3 ×Sn, Tatra Mountains Math. Publ. 9 (1996) 51-56.
[9] M. Klešč, R.B. Richter, I. Stobert, The crossing number of C5 ×Cn, J. Graph Theory 22 (1996) 239-243.
[10] A.T. White, L.W. Beineke, Topological graph theory, in: Selected Topics in Graph Theory (Academic Press, London, 1978) 15-49.

Received 9 June 1998
Revised 21 November 1998

Close