YANG JIAO,SHAO ZE-LINGAND LI ZHI-GUO

(School of Science,Hebei University of Technology,Tianjin,300401)

Abstract:The book embedding of a graph G consists of placing the vertices of G in a line called spine and assigning edges of the graph to pages so that the edges assigned to the same page do not intersect.The number of pages is the minimum number in which the graph can be embedded.In this paper,we study the book embedding of the Cartesian product Pm×Sn,Pm×Wn,Cn×Sm,Cn×Wm,and get an upper bound of their pagenumber.

Key words:book embedding,cartesian product,pagenumber

1 Introduction

Let G be a simple graph.A book consists of a spine that is just a line and some number of pages each of which is a half-plane with the spine as boundary.We say that a graph admints an n-book embedding if one can assign the edges to n pages and there exists a linear ordering of its vertices along the spine of a book such that the edges on the same page do not intersect.The pagenumber is a measure of the quality of a book embedding.The pagenumber pn(G)or book thickness bt(G)of a graph G is the smallest n such that G has an n-book embedding.

In[12],the book embedding number of the Cartesian products Pm×Pn,Pm×Cnhas been given.In this article,we study the pagenumber of the Cartesian products Pm×Sn,Pm×Wn,Cn×Sm,Cn×Wmand establish the upper bound of these graphs.

2 Main Results

The graph considered in this article are simple and connected.Given a graph G,with edge set E(G)and vertex set V(G),if two vertices i and j are adjacent in G,i.e.,if there is an edge e=ij∈E(G),we say that u and v are neighbors in G.we denote a path with m vertices and a cycle with n vertices by Pmand Cn,respectively.A wheel graph is a graph formed by connecting a single vertex to all vertices of a cycle and we use Wmto denote a wheel graph with m+1 vertices(m≥3).A star graph Snwith n+1 vertices is the complete bipartite graph K1,n.

The Cartesian product of graphs G and H,denoted by G×H,is the graph with vertex set V(G)×V(H),and(u1,v1)is adjacent to(u2,v2)if either u1is adjacent to u2in G and v1=v2or u1=u2and v1is adjacent to v2in H.And given a Cartesian product of path with star Pm× Sn,there is a bijectionfrom V to[m(n+1)],so the edges vivjcan be replaced byFor example,the graph Cn×Sm(see Fig.2.1(a))and Pm×Wn(see Fig.2.1(b)).

Fig.2.1 The graph Cn×Sm(left)and Pm×Wn(right)

For different n and m,the upper bound is different in some situations.Now we prove these theorems.

Theorem 2.1If m≥2 and n≥2,then

Proof.Case 1.The lower bound:When m=2,P2×Snis not outerplanar,then pn(P2×Sn)≥2.

The upper bound:Put the vertices in the ordering of 1,2,3,4,···,m(n+1)as Fig.2.2 and construct a two pages partition for edges as follows:

Page 1:Edges{(a,n+1)|1≤a＜n+1}and edges{(n+2,b)|n+2＜b≤2(n+1)}.

Page 2:Edges{(a,b)|a+b=2(n+1)+1 and 1≤a＜b}.

To summarize,pn(P2×Sn)=2.

Fig.2.2 The book embedding of P2×Sn

Case 2.The lower bound:When m＞2,Pm×Sncontains a k3,3as it minor,so it is a nonplanar graph,then pn(Pm×Sn)≥3.

The upper bound:The book embedding is as follows:

We place the vertices of Pm×Snas the above ordering of Case 1.

Page 1:Edges{(a,b)|a+b=2k(n+1)+1,0＜k＜m and k is odd}.

Page 2:Edges{(a,b)|a+b=2k(n+1)+1,0＜k＜m and k is even}.

Page 3:Edges{(a,k(n+1))|(k?1)(n+1)＜a＜k(n+1),0＜k≤m and k is odd}and edges{(k(n+1)+1,b)|k(n+1)+1＜b≤(k+1)(n+1),0＜k＜m and k is odd}.

Obviously,all edges of this graph are embedded in the pages and the edges assigned to the same page do not intersect(see Fig.2.3),so pn(Pm×Sn)=3.This completes the proof.

Fig.2.3 The book embedding of P4×S5

Theorem 2.2If m≥2,n≥3,then pn(Pm×Wn)≤4.In particular,pn(Pm×Wn)=3 if m=2.

Proof. The lower bound:Since Pm×Wncontains a k3,3as it minor,so it is a nonplanar graph,by[2]known pn(Pm×Wn)≥3.

The upper bound:Firstly,let the ordering be as 1,2,3,···,n?1,n,n+1,···,m(n+1).Placing the edges{(a,b)|a+b=2k(n+1)+1,0＜k＜m and k is odd}in the first page.In the second page,the edges{(a,b)|a+b=2k(n+1)+1,0＜k＜m and k is even}are embedded.The edges{(a,k(n+1))|k is odd,(k?1)(n+1)＜a＜k(n+1)and 0＜k≤m}and edges{(k(n+1)+1,b)|k is odd,k(n+1)+1＜b≤(k+1)(n+1)and 0＜k＜m}are embedded in the third page.In the fourth page,the edges{(k(n+1)+1,(k+1)(n+1)?1)|k is even,0≤k＜m}and edges{((k?1)(n+1)+2,k(n+1))|k is even,0＜k≤m}are embedded.

The edges in the first and second pages are nested,thus they are disjoint.Obviously,the edges are embedded in the third page and the fourth page without any crossing(see Figs.2.4 and 2.5).

When m=2,according to the above proof,the edges on the second page do not exist,because 0＜k＜m and k is even.So all edges can be embedded in three pages.

Fig.2.4 When m is even,the book embedding of Pm×Wn

Fig.2.5 When m is odd,the book embedding of Pm×Wn

Theorem 2.3If m≥3,n is even and n＞3 or n=3,m≥3,then pn(Cn×Sm)=3.If m≥3,n is odd and n＞3,then pn(Cn×Sm)≤m+1.

Proof.The lower bound:Since Cn×Smis not a planar graph,by[2]known pn(Cn×Sm)≥3.

The upper bound:If n=3,m≥3,let Cj(j∈[m+1])be an ordered 3 elements arrays and

Put Ciin the line with the ordering of C0,C1,C2,···,Cm,and all vertices are assigned.

The edges{(a,m+1)|1≤a＜m+1}and edges{(a,b)|a+b=2k(m+1)+1,0＜k＜n,(k?1)(m+1)≤a＜b or 1≤a≤m+1,b?a=(n?1)(m+1)}can be placed in the first page.In the second page,the edges{(a,3(m+1))|2(m+1)＜a＜3(m+1)}are embedded.The edges{(m+2,b)|m+2＜b≤2(m+1)}are embedded in the third page.The edges on each page are disjoint(see Fig.2.6),so pn(C3×Sm)=3.

Fig.2.6 The book embedding of C3×Sm

When n ＞ 3,m ≥ 3,the vertex sequence of Cn×Smis 1,2,3,4,5,···,n(m+1).

Case 1.The upper bound:When n is even,we construct a three-page partition for edges as follows:

Page 1:Edges{(a,b)|a+b=2k(m+1)+1,(k?1)(m+1)＜a＜b,k is even,0＜k＜n}and edges{(a,b)|a+b=n(m+1)+1,1≤a≤m+1}.

Page 2:Edges{(a,b)|a+b=2k(m+1)+1,(k?1)(m+1)＜a＜b,k is odd,0＜k＜n}.

Page 3:Edges{(a,k(m+1))|(k?1)(m+1)＜a＜k(m+1),k is odd,0＜k＜n}and edges{(k(m+1)+1,b)|(k(m+1)+1＜b≤(k+1)(m+1),k is odd,0＜k＜n}.

So three pages are enough to embed this graph.

Secondly,we place the edge(2,(n?1)(m+1)+2)and edges{(a,b)|a+b=2k(m+1)+1,(k?1)(m+1)+1＜a＜b,k is odd,0＜k＜n}in the second page and these edges are nested.Nextly,placing the edges{(a,b)|b?a=(n?1)(m+1),2＜a≤m}in the a-th page,respectively.Because of the different values of a,edges are different and these edges are intersected so that these edges need m?2 pages.

Finally,the edges{(a,b)|a+b=2k(m+1)+1,(k?1)(m+1)≤a＜b,k is even,0＜k＜n}and edge(m+1,n(m+1))are embedded in another page.These edges are nested,so they are disjoint(see Fig.2.7).

By assigning the upper edges,we can get a m+1 pages embedding for Cn×Sm.

Fig.2.7 When n is odd,the book embedding of Cn×Sm

Theorem 2.4If both n and m are equal or greater than 3,then

In particular,pn(Cn×Wm)=3 if n is even and m=3.

Proof.The vertices of Cn× Wmare placed in this sequence of 1,2,3,4,5,···,n(m+1).

Case 1.If n is even and m＞3,the book embedding is as follows:

Page 1:Edges{(a,k(m+1))|(k?1)(m+1)＜a＜k(m+1),k is odd,0＜k＜n}and edges{(k(m+1)+1,b)|k(m+1)+1＜b≤(k+1)(m+1),k is odd,0＜k＜n}.

Page 2:Edges{(a,b)|a+b=2k(m+1)+1,(k?1)(m+1)＜a＜b,k is odd,0＜k＜n}.

Page 3:Edges{(k(m+1)+1,(k+1)(m+1)?1)|k is even,0≤k＜n}and edges{((k?1)(m+1)+2,k(m+1))|k is even,0＜k≤n}.

Page 4:Edges{(a,b)|a+b=2k(m+1)+1,(k?1)(m+1)＜a＜b,k is even,0＜k＜n}and edges{(a,b)|a+b=n(m+1)+1,1≤a≤m+1}(see Fig.2.8).

Fig.2.8 When n is even,the book embedding of Cn×Wm

Case 2.If n is odd and m≥3,the book embedding is as follows:

Page 2:Edges{(a,b)|a+b=2k(m+1)+1,(k?1)(m+1)+1＜a＜b,k is odd,0＜k＜n}and edge(2,(n?1)(m+1)+2).

Page a:Edges{(a,b)|b?a=(n?1)(m+1),2＜a＜m}.The edges that satisfy the preceding condition are all intersected,so these edges require m?3 pages altogether.

Page m:Edges{(a,b)|a+b=2k(m+1)+1,(k?1)(m+1)＜a＜b,k is even,0＜k＜n}and edge(m+1,n(m+1)).

Page m+1:Edges{(k(m+1)+1,(k+1)(m+1)?1)|k is even,0≤k＜n},edges{((k?1)(m+1)+2,k(m+1))|k is even,0＜k＜n}and edge(m,n(m+1)?1).We can see from Fig.2.9 that the the edges are not intersecting at the same page.The result is obtained.

Fig.2.9 When n is odd,the book embedding of Cn×Wm

Case 3.When n is even and m=3,on the one hand,since Cn×W3contains a k3,3as it minor,then by[2]known pn(Cn×W3)≥3.On the other hand,let the ordering be as 1,2,3,···,n(m+1)and construct a three-page partition for edges as follows:

Page 2:Edges{(a,b)|a+b=2k(m+1)+1,(k?1)(m+1)+1＜a＜b,k is odd,0＜k＜n},edges{(a,b)|a+b=2k(m+1)+1,k(m+1)?2＜a≤k(m+1),k is even,0＜k＜n}and edge(2,n(m+1)?1).

Page 3:Edges{(k(m+1)+1,(k+1)(m+1)?1)|k is even,0≤k＜n}and edges{((k?1)(m+1)+2,k(m+1))|k is even,0＜k≤n},edges{(a,b)|a+b=2k(m+1)+1,(k?1)(m+1)＜a＜(k?1)(m+1)+3,k is even,0＜k＜n}and edges{(a,b)|a+b=n(m+1)+1,3≤a≤m+1}.

Clearly,all edges do not intersect in each page(see Fig.2.10),so three pages are sufficient for Cn×W3.

Fig.2.10 The book embedding of C6×W3