二部置换图Hm,n的交叉数

The crossing number of the bipartite permutation graph

讨论了二部置换图Hm,n的交叉数。让cr(G)代表图G的交叉数,Hm,n表示二部置换图,得到了:cr(H3,n)=0;[n-1]≤cr(H4,n)≤2n-4;当m=2,3,4时,cr(Hm,2)=0;cr(H5,2)=1;当m≥6时,cr(Hm,2)≥[m-32][m-4/2]2。并求出一般情况下Hm,n的交叉数的上下界[n2][m-3/2][m-4/2]2≤cr(Hm,n)≤2C4m+(n-3)C4m+1。

The crossing number of the bipartite permutation graph is investigated.Let cr(G)denote the crossing number of graph G,and Hm,ndenote the bipartite permutation graph.It is shown that cr(H3,n)=0 and cr(Hm,2)=0 for m=2,3,4,■and■.For any m and n,it is obtained that ■.