Cyclic permutations and crossing numbers of join products of symmetric graph of order six


Berežný, Štefan and Štas, Michal


Abstract

carpathian_2018_34_2_143_155_abstract

Full PDF

carpathian_2018_34_2_143_155

In the paper, we extend known results concerning crossing numbers for join of graphs of order six. We give the crossing number of the join product G + D_n, where the graph G consists of two leaves incident with two opposite vertices of one 4-cycle, and D_n consists on n isolated vertices. The proof is done with the~help of software that generates all cyclic permutations for a given number k, and creates a~new graph \hbox{COG} for a~calculating the distances between all (k-1)! vertices of the graph. Finally, by adding new edges to the graph G, we are able to obtain the crossing number of the join product with the discrete graph D_n for two other graphs. The methods used in the paper are new, and they are based on combinatorial properties of cyclic permutations.

 

 

Additional Information

Author(s)

Berežný, Štefan, Štas, Michal