Acta Electrotechnica et Informatica (Mar 2019)
ALTERNATIVE PROOF ON THE CROSSING NUMBER OF K1,1,3,N
Abstract
The main aim of the paper is to give the crossing number of join product G+Dn for the connected graph G of order five isomorphic with the complete tripartite graph K1,1,3, where Dn consists on n isolated vertices. The proof of the crossing number of K1,1,3,n was published by very rather unclear discussion of cases by Ho in [5]. In our 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 once. The methods used in the paper are new, and they are based on combinatorial properties of cyclic permutations. Finally, by adding one edge to the graph G, we are able to obtain the crossing number of the join product with the discrete graph Dn for one new graph
Keywords