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

Document Type : Original paper

Author

Technical University of Kosice, Department of Mathematics and Theoretical Informatics

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