On the crossing number of join product of the discrete graph with special graphs of order five

Michal Staš

Abstract


The main aim of the paper is to give the crossing number of join product G+Dn for the disconnected graph G of order five consisting of the complete graph K4 and of one isolated vertex. In the proofs,  it will be extend the idea of the minimum numbers of crossings between two different subgraphs from the set of subgraphs which do not cross the edges of the graph G onto the set of subgraphs which cross the edges of the graph G exactly one times. All methods used in the paper are new, and they are based on combinatorial properties of cyclic permutations. Finally, by adding some edges to the graph G, we are able to obtain the crossing numbers of the join product with the discrete graph Dn for two new graphs.

Keywords


graph; drawing; crossing number; join product; cyclic permutation

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2020.8.2.10

References

S. Berezny and J. Busa Jr., Algorithm of the Cyclic-Order Graph Program (Implementation and Usage), Math. Model. Geom. 7(3) (2019), 1–8.

S. Berezny and M. Stas, Cyclic permutations and crossing numbers of join products of two symmetric graphs of order six, Carpathian J. Math. 35(2) (2019), 137–146.

S. Berezny and M. Stas, On the crossing number of join of the wheel on six vertices with the discrete graph, Carpathian J. Math. 36(3) (2020), 381–390.

M. R. Garey and D. S. Johnson, Crossing number is NP-complete. SIAM J. Algebraic. Discrete Methods 4 (1983), 312–316.

R. K. Guy, A combinatorial problem, Bull. Malayan Math. Soc. 7 (1960), 68–72.

C. Hernandez-Velez, C. Medina and G. Salazar, The optimal drawing of K5,n, Electronic Journal of Combinatorics 21(4), P4.1 (2014), 29 pp.

D. J. Kleitman, The crossing number of K5,n, J. Combinatorial Theory 9 (1970), 315–323.

M. Klesc, On the Crossing Numbers of Cartesian Products of Stars and Graphs on Five Vertices, Combinatorial Algorithms, 5874 (2009), 324–333.

M. Klesc, The crossing numbers of join of the special graph on six vertices with path and cycle, Discrete Math. 310(9) (2010), 1475–1481.

M. Klesc and E. Drazenska, The crossing numbers of products of the graph K2,2,2 with stars, Carpathian J. Math. 24(3) (2008), 327–331.

M. Klesc and S. Schrotter, The crossing numbers of join of paths and cycles with two graphs of order five, Combinatorial Algorithms, Springer, LNCS 7125 (2012), 160–167.

M. Klesc and S. Schrotter, The crossing numbers of join products of paths with graphs of order four, Discuss. Math. Graph Theory 31(2) (2011), 321–331.

A. A. G. Ngurah and R. Simanjuntak, On the super edge-magic deficiency of join product and chain graphs, Electron. J. Graph Theory Appl. 7 (1) (2019), 157–167.

M. Stas, On the crossing number of the join of the discrete graph with one graph of order five, Mathematical Modelling and Geometry 5(2) (2017), 12–19.

M. Stas, Determining crossing number of join of the discrete graph with two symmetric graphs of order five, Symmetry 11(2) (2019), 1–9.

M. Stas, On the crossing number of join of the wheel on five vertices with the discrete graph, Bull. Aust. Math. Soc. 101(3) (2020), 353–361.

D.R. Woodall, Cyclic-order graphs and Zarankiewicz’s crossing number conjecture, J. Graph Theory 17 (1993), 657–671.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats