The Book Embedding Of Some Graphs

Given a simple graph G=(V,E)with n vertices,a bijection f:V→{1,2,3,4,...,n} is called a labeling of G,where f∈ {1,2,3,...,n} represents the label of vertex v ∈V.Let ui= f-1(i)be the vertex with label i.Then the labeling f can be also regarded as a linear ordering(u1,u2,...,un)on the spine of the book.Two edges uv,xy ∈ E are said to be crossing if and only if f(u)<f(x)<f(v)<f(y)or f(x)<f(u)<f(y)<f(v).Under a labeling f,a partition█＝{E1,E2,…Ep} of edge set E(G)is called a page partition if no pair of edges in any set Ei(1≤i≤)cross.We call the minimum number of subsets of a page partition █ the pagenumber of G under labeling f,and denote it by p(G,f).The pagenumber of G is then defined as P(G)=min p(G,f),f where f is taken over all labeling of G.Conclusion 1 Let Cn,m be a cyclic graph,and n=km+p,① If m and p(p≠0)are both even,then p(Cn,m)≤4.②If m is even and p(1<p<m-1)is odd,then█where(m,p)≠1 and t,θ can be got by Algorithm 1;█where(m,p)=1,r=m-[m/p+1]·(p+1),p’=m-p,r’=m[m/p’+1]·(p’+1).③█Conclusion 2 Let SG(n,k)(n=2k+1,2k+2)be a Schrijver graph,then for k≥3,p(SG(2k+2,k))≤1,especially p(SG(6,2))=3.p(SG(2k+1,k))=1,p(SG(6,2)×Pn)≤5.Conclusion 3 For Fibonacci cubes Γn,p(Γn)≤n-2 for n≥3.Conclusion 4 Let Q2k(n)be a 2k-ary hypercubes,p(Q2k(n))≤2n-1,for n≥2,k∈Z and k>1.Conclusion 5 There are(3n-11)-pages for crossed cubes CQn(n≥ 6).