The crossing numbers of join product of four graphs on six vertices with discrete graphs

Document Type : Original paper

Author

Department of Mathematics and Theoretical Informatics, Faculty of Electrical Engineering and Informatics, Technical University, 042 00 Košice, Slovak Republic

Abstract

The main aim of the paper is to give the crossing number of the join product $G^\ast + D_n$ for the graph $G^\ast$ isomorphic to 4-regular graph on six vertices except for two distinct edges with no common vertex such that two remaining vertices are still adjacent, and where $D_n$ consists of $n$ isolated vertices. The proofs are done with possibility of an existence of a separating cycle in some particular drawing of the investigated graph $G^\ast$ and also with the help of well-known exact values for crossing numbers of join products of two subgraphs $H_k$ of $G^\ast$ with discrete graphs.

Keywords

Main Subjects

References

[1] K. Asano, The crossing number of $K_{1,3,n}$ and $K_{2,3,n}$, J. Graph Theory. 10 (1986), no. 1, 1–8. https://doi.org/10.1002/jgt.3190100102
[2] Š. Berežný and M. Staš, Cyclic permutations and crossing numbers of join products of symmetric graph of order six, Carpathian J. Math. 34 (2018), no. 2, 143–155. http://doi.org/10.37193/CJM.2018.02.03
[3] Š. Berežný and M. Staš, On the crossing numbers of the join products of five graphs on six vertices with discrete graphs, Carpathian J. Math. 39 (2023), no. 2, 371–382.  https://doi.org/10.37193/CJM.2023.02.03
[4] M. Chimani and T. Wiedera, An ilp-based proof system for the crossing number problem, 24th In Proceedings of the Annual European Symposium on Algorithms 29 (2016), 1–13.
[5] K. Clancy, M. Haythorpe, and A. Newcombe, A survey of graphs with known or bounded crossing numbers, Australas. J. Combin. 78 (2020), no. 2, 209–296.
[6] Z. Ding and Y. Huang, The crossing numbers of join of some graphs with $n$ isolated vertices, Discuss. Math. Graph Theory 38 (2018), no. 4, 899–909.  http://doi.org/10.7151/dmgt.2048
[7] E. Draženská and M. Klešč, The crossing numbers of products of the graph $K_{2,2,2}$ with stars, Carpathian J. Math. 24 (2008), no. 3, 327–331.
[8] M.R. Garey and D.S. Johnson, Crossing number is NP-complete, SIAM J. Algebraic. Discrete Methods 4 (1983), no. 3, 312–316.  https://doi.org/10.1137/0604033
[9] C. Hernández-Vélez, C. Medina, and G. Salazar, The optimal drawing of $K_{5,n}$, Electron. J. Comb. 21 (2014), no. 4, #P4.1
[10] P.T. Ho, The crossing number of $K_{1,m,n}$, Discrete Math. 308 (2008), no. 24, 5996–6002.  https://doi.org/10.1016/j.disc.2007.11.023
[11] P.T. Ho, The crossing number of $K_{2,2,2,n}$, Far East J. Appl. Math. 30 (2008), 43–69.
[12] P.T. Ho, On the crossing number of some complete multipartite graphs, Util. Math. 79 (2009), 125–143.
[13] P.T. Ho, The crossing number of $K_{1,1,3,n}$, Ars Combin. 99 (2011), 461–471.
[14] P.T. Ho, The crossing number of $K_{2,4,n}$, Ars Combin. 109 (2013), 527–537.
[15] Y. Huang and T. Zhao, The crossing number of $K_{1,4,n}$, Discrete Math. 308 (2008), no. 9, 1634–1638. https://doi.org/10.1016/j.disc.2006.12.002
[16] D.J. Kleitman, The crossing number of $K_{5,n}$, J. Comb. Theory 9 (1970), 315–323. https://doi.org/10.1016/S0021-9800(70)80087-4
[17] M. Klešč, On the crossing numbers of cartesian products of stars and graphs on five vertices, Combinatorial Algorithms (Berlin, Heidelberg) (J. Fiala, J. Kratochv´ıl, and M. Miller, eds.), Springer Berlin Heidelberg, 2009, pp. 324–333.
[18] M. Klešč, On the crossing numbers of products of stars and graphs of order five, Graphs Combin. 17 (2001), 289–294. https://doi.org/10.1007/s003730170042
[19] M. Klešč, The crossing numbers of join of the special graph on six vertices with path and cycle, Discrete Math. 310 (2010), no. 9, 1475–1481.  https://doi.org/10.1016/j.disc.2009.08.018
[20] M. Klešč, D. Kravecová, and J. Petrillová, The crossing numbers of join of special graphs, Electr. Eng. Inform. 2 (2011), 522–527.
[21] M. Klešč and Š. Schrötter, The crossing numbers of join products of paths with graphs of order four, Discuss. Math. Graph Theory 31 (2011), no. 2, 321–331.
[22] M. Klešč and Š. Schrötter, The crossing numbers of join of paths and cycles with two graphs of order five, Lecture Notes in Computer Science: Mathematical Modeling and Computational Science 7125 (2012), 160–167.
[23] M. Klešč and Š. Schrötter, On the crossing numbers of cartesian products of stars and graphs of order six, Discuss. Math. Graph Theory 33 (2013), no. 3, 583–597.  http://doi.org/10.7151/dmgt.1705
[24] M. Klešč and M. Staš, Cyclic permutations in determining crossing numbers, Discuss. Math. Graph Theory 42 (2022), no. 4, 1163–1183.  https://doi.org/10.7151/dmgt.2351
[25] M. Klešč, M. Staš, and J. Petrillová, The crossing numbers of join of special disconnected graph on five vertices with discrete graphs, Graphs Combin. 38 (2022), no. 2, Article number: 35.  https://doi.org/10.1007/s00373-021-02423-5
[26] M. Klešč and M. Valo, Minimum crossings in join of graphs with paths and cycles, Acta Elec. Inf. 12 (2012), no. 3, 32–37.  http://doi.org/10.2478/v10198-012-0028-0
[27] H. Mei and Y. Huang, The crossing number of $K_{1,5,n}$, Int. J. Math. Combin. 1 (2007), no. 1, 33–44.
[28] Z.D. Ouyang, J. Wang, and Y.Q. Huang, The crossing number of join of the generalized petersen graph $P(3, 1)$ with path and cycle, Discuss. Math. Graph Theory 38 (2018), no. 2, 351–370.  http://doi.org/10.7151/dmgt.2005
[29] M. Staš, On the crossing number of the join of the wheel on five vertices with the discrete graph, Bull. Aust. Math. Soc. 101 (2020), no. 3, 353–361. https://doi.org/10.1017/S0004972719001199
[30] M. Staš, On the crossing numbers of join products of five graphs of order six with the discrete graph, Opuscula Math. 40 (2020), no. 3, 383–397.  https://doi.org/10.7494/OpMath.2020.40.3.383
[31] M. Staš, On the crossing numbers of the joining of a specific graph on six vertices with the discrete graph, Symmetry 12 (2020), no. 1, Article ID: 135.  https://doi.org/10.3390/sym12010135
[32] M. Staš, On the crossing numbers of join products of four graphs of order six with the discrete graph, Azerbaijan J. Math. 12 (2022), no. 1, 80–97.
[33] J. Wang, L. Zhang, and Y. Huang, On the crossing number of the cartesian product of a 6-vertex graph with $S_n$, Ars Combin. 109 (2013), 257–266.
[34] Y. Wang and Y. Huang, The crossing number of cartesian product of 5-wheel with any tree, Discuss. Math. Graph Theory 41 (2021), no. 1, 183–197. http://doi.org/10.7151/dmgt.2181
[35] D.R. Woodall, Cyclic-order graphs and zarankiewicz’s crossing number conjecture, J. Graph Theory. 17 (1993), no. 6, 657–671.  https://doi.org/10.1002/jgt.3190170602
Communications in Combinatorics and Optimization
Volume 9, Issue 2
June 2024
Pages 241-252

Files

Share

How to cite

Statistics