D. Bokal proved that the crossing number is additive for the zip product under the condition of having two coherent bundles in the zipped graphs. This property is very effective when dealing with the crossing numbers of (capped) Cartesian product of trees with graphs containing a dominating vertex. In this paper, we first prove that the crossing number is still additive for the zip product under a weaker condition. Based on the new condition, we then establish some general expressions for bounding the crossing numbers of (capped) Cartesian product of trees with graphs (possibly without dominating vertex). Exact values of the crossing numbers of Cartesian product of trees with most graphs of order at most five are obtained by applying these expressions, which extend some previous results due to M. Klešč. In fact, our results can also be applied to deal with Cartesian product of trees with graphs of order more than five.

REFERENCES

1J. Adamsson and R. B. Richter, Arrangements, circular arrangements and the crossing number of $C_{7} □ C_{n}$ , J. Combin. Theory Ser. B 90 (2004), 21–39.
10.1016/j.jctb.2003.05.001
Web of Science® Google Scholar
2K. Asano, The crossing number of $K_{1, 3, n}$ and $K_{2, 3, n}$ , J. Graph Theory 10 (1986), 1–8.
10.1002/jgt.3190100102
Web of Science® Google Scholar
3L. W. Beineke and R. D. Ringeisen, On the crossing numbers of products of cycles and graphs of order four, J. Graph Theory 4 (1980), 145–155.
10.1002/jgt.3190040203
Web of Science® Google Scholar
4D. Bokal, On the crossing numbers of Cartesian products with paths, J. Combin. Theory Ser. B 97 (2007), 381–384.
10.1016/j.jctb.2006.06.003
Web of Science® Google Scholar
5D. Bokal, On the crossing numbers of Cartesian products with trees, J. Graph Theory 56 (2007), no. 4, 287–300.
10.1002/jgt.20258
Web of Science® Google Scholar
6J. A. Bondy and U. S. R. Murty, Graph theory, Grad. Texts Math., Springer, New York, 2008.
Google Scholar
7P. Erdös and R. K. Guy, Crossing number problems, Amer. Math. Monthly 80 (1973), 52–58.
10.1080/00029890.1973.11993230
Google Scholar
8M. R. Garey and D. S. Johnson, Crossing number is NP-complete, SIAM J. Algebr. Discrete Methods 4 (1983), 312–316.
10.1137/0604033
Web of Science® Google Scholar
9L. Y. Glebsky and G. Salazar, The crossing number of $C_{m} □ C_{n}$ is as conjectured for $n \geq m (m + 1)$ , J. Graph Theory 47 (2004), 53–72.
10.1002/jgt.20016
Web of Science® Google Scholar
10F. Harary, P. C. Kainen, and A. J. Schwenk, Toroidal graphs with arbitrarily high crossing numbers, Nanta Math. 6 (1973), 58–67.
Google Scholar
11P. Ho, The crossing number of $K_{1, 1, 3, n}$ , Ars Combinatoria 99 (2011), 461–471.
Web of Science® Google Scholar
12P. Ho, On the crossing number of some complete multipartite graphs, Utilitas Mathematica 79 (2009), 125–143.
Web of Science® Google Scholar
13Y. Huang and T. Zhao, The crossing number of $K_{1, 4, n}$ , Discrete Math. 308 (2008), no. 9, 1634–1638.
10.1016/j.disc.2006.12.002
Web of Science® Google Scholar
14S. Jendrol' and M. Ščerbová, On the crossing numbers of $S_{m} □ P_{n}$ and $S_{m} □ C_{n}$ , Časopis Pro Pěstování Matematiky 107 (1982), 225–230.
Google Scholar
15M. Klešč, The crossing numbers of products of paths and stars with 4-vertex graphs, J. Graph Theory 18 (1994), 605–614.
10.1002/jgt.3190180608
Web of Science® Google Scholar
16M. Klešč, The crossing number of $K_{2, 3} □ P_{n}$ and $K_{2, 3} □ S_{n}$ , Tatra Mountains Math. Publ. 9 (1996), 51–56.
Google Scholar
17M. Klešč, The crossing numbers of Cartesian products of paths with 5-vertex graphs, Discrete Math. 233 (2001), 353–359.
10.1016/S0012-365X(00)00251-X
Web of Science® Google Scholar
18M. Klešč, On the crossing numbers of Cartesian products of stars and graphs on five vertices, Combinatorial Algorithms, LNCS, 5874, Springer, Heidelberg, 2009, pp. 324–333.
10.1007/978-3-642-10217-2_32
Google Scholar
19M. Klešč and S. Schrötter, The crossing numbers of join products of paths with graphs of order four, Discuss. Math. Graph Theory 31 (2011), 321–331.
10.7151/dmgt.1548
Google Scholar
20D. J. Kleitman, The crossing number of $K_{5, n}$ , J. Combinatorial Theory 9 (1970), no. 4, 315–323.
10.1016/S0021-9800(70)80087-4
Google Scholar
21S. Lv and Y. Huang, On the crossing numner of $K_{5} □ S_{n}$ , J. Math. Res. Expo. 28 (2008), 445–459.
Google Scholar
22Z. Ouyang, W. Jing, and Y. Huang, On the crossing numbers of the Cartesian product path with complete graph, Discrete Math. 328 (2014), 71–78.
10.1016/j.disc.2014.03.011
Web of Science® Google Scholar
23R. B. Richter and C. Thomassen, Intersections of curve system and the crossing number of $C_{5} □ C_{5}$ , Discrete Comput. Geom. 13 (1995), 149–153.
10.1007/BF02574034
Web of Science® Google Scholar
24R. D. Ringeisen and L. W. Beineke, The crossing number of $C_{3} □ C_{n}$ , J. Combin. Theory Ser. B 24 (1978), 134–136.
10.1016/0095-8956(78)90014-X
Web of Science® Google Scholar
25G. Salazar, Drawings of $C_{m} □ C_{n}$ with one disjoint family, J. Combin. Theory Ser. B 76 (1999), 21–39.
10.1006/jctb.1998.1890
Web of Science® Google Scholar
26M. Schaefer, Crossing numbers of graphs, CRC Press, Boca Raton, FL, 2017.
Google Scholar
27F. Shahrokhi et al., Intersection of curves and crossing number of $C_{m} □ C_{n}$ on surfaces, Discrete Comput. Geom. 19 (1998), 237–247.
10.1007/PL00009343
Web of Science® Google Scholar

Citing Literature

Volume96, Issue2

February 2021

Pages 289-309

Zip product of graphs and crossing numbers

Abstract

REFERENCES

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

Zip product of graphs and crossing numbers

Abstract

REFERENCES

Citing Literature

References

Related

Information