Embedding Generalized Petersen Graph in Books?

Bin ZHAOWei XIONGYingzhi TIANJixiang MENG

1 Introduction

A book consists of a spine which is just a line and some number of pages each of which is a half-plane with the spine as its boundary.A book embedding of a graph G consists of placing the vertices of G on the line in order and assigning edges of the graph to pages so that the edges assigned to the same page do not cross each other.The page number is a measure of the quality of a book embedding.It is the minimum number of pages in which the graph G can be embedded,and is denoted by pn(G).

Ollmann[18] first introduced the page number problem,and the problem is NP-complete even if the order of nodes on the spine is fixed(see[3,13]).The book embedding problem has been motivated by several areas of computer science such as sorting with parallel stacks,singlerow routing,fault-tolerant processor arrays and turning machine graphs(see[3]).Embedding a graph in a book with the minimum number of pages has received much attention in the literature(see[3–10]).In[16],Berhart and Keinen proved the theorem:pn(G)≤ 1 if and only if G is outplanar and pn(G)≤2 if and only if G is a subgraph of a Hamiltonian planar graph.By the above,for a connected graph G which is neither an outplanar nor a subhamiltonian planar graph,we have pn(G)≥3.

The Petersen graph is one of the most famous graphs.The notation of the generalized Petersen graph is that given integers n≥3 and k∈Zn{0},the graph P(n,k)is defined on the set{xi,yi|i∈Zn}of 2n vertices,with the adjacencies given by xixi+k,xiyi,yiyi+1for alli∈Zn.In this notion,the Petersen graph isP(5,2)(see Figure a),which can be embedded in a 3-page book(see Figure b).

Figure a

Figure b

From the definition of the generalized Petersen graphThus,we always assumeThe graphP(n,1)is called a Prism graph,which is an outplanar graph,so we assume 2

Let(n,k)=dbe the greatest common denominator ofnandk.For different parities ofnandd,we give a complete description of the upper bounds ofpn(P(n,k)),and in some situations,we obtain thatpn(P(n,k))=3,which is best possible.We shall prove the following theorems.

Theorem 1.1If n and d are even,then pn(P(n,k))4.

Corollary 1.1If n is even and k=2,then pn(P(n,k))=3.

Theorem 1.2If n is even and d is odd,then pn(P(n,k))5.

Letn=qk+rands=k?r,whereris an integer less thank.

Theorem 1.3If n is odd and k is even,then pn(P(n,k))2s+1.In particular,pn(P(n,k))2d+1,if s=d?1.

Corollary 1.2If n is odd and k=2,then pn(P(n,k))=3.

Theorem 1.4If both n and k are odd,then pn(P(n,k))

Table1

Some graphs are special cases of the generalized Petersen graph.For example,the Desargues graph isP(10,3),the M?bius-Kantor graph isP(8,3),and the prism graph isP(n,1).We can know the page number of these graphs from the page number of the generalized Petersen graph(see Table 1).

2 Proofs of the Main Results

We assumeV(P(n,k))={0,1,···,n?1,0?,1?,···,(n?1)?},E···(P(n,k)···)={ii?|i=0,1,···,n?1}∪{i?(i+1)?|i=0,1,···,n?1}∪{i(i+k)|i=0,1,···,n?1}(modn)andV1∪V2=V(P(n,k)),whereV1={0,1,···,(n?1)}andV2={0?,1?,···,(n?1)?}in the following.Each edge inE···(P(n,k)[V2]···)is called a 1-edge,and each edge inE···(P(n,k)[V1]···)is called ak-edge,whereP(n,k)[Vi]is the subgraph ofP(n,k)induced by the vertex setVi,soE(P(n,k)[Vi])?E(P(n,k)).E(Ci)denotes the edge set containing all edges induced by the vertex setCi,andE[Ci,Cj]denotes the edge set containing all edges fromCitoCj.

ForP(n,k),we lay outV1in the spine by orderingβ,and useβ?1to denote the reverse ordering ofβ.That is,β?1is obtained fromβby revolving 1800.Replacing eachi∈V1byi?∈V2inβ?1gives an ordering ofV2,which is denoted byβ?.So we have the following fact.

Fact 2.1 For the generalized Petersen graphP(n,k),if an ordering ofV1isβ,thenV(P(n,k))has an orderingββ?.

Using Fact 2.1,we can draw the next lemma.

Lemma 2.1If P(n,k)[V1]and P(n,k)[V2]can be embedded in p1and p2pages with the vertex orderings βand β?respectively,then pn(P(n,k))≤max(p1,p2)+1.

Proof SinceP(n,k)[V1]∩P(n,k)[V2]=?,pn(P(n,k)[V1]∪P(n,k)[V2])=max(p1,p2).By the definition ofP(n,k),there is a perfect matchingM,where each edgee=uv∈Msatisfiesu∈V1,v∈V2,andP(n,k)=P(n,k)[V1]∪P(n,k)[V2]∪M.Sinceβis the vertex ordering ofP(n,k)[V1]withpn(P(n,k)[V1])=p1,by Fact 2.1,we have an ordering ofV(P(n,k)),denoted byββ?.By the construction ofββ?,Mneeds one page to be embedded,and the edges inMcross the edges inP(n,k)[V1]andP(n,k)[V2].Sopn(P(n,k))≤max(p1,p2)+1.

Proof of Theorem 1.1 Let Ci(i∈[d?1]∪0)be an ordered-element array and

ThusCi∩Cj=?and 0≤v≤N?1 for v∈Ciand i=0,1,···,d ? 1.

Put Ciin the line with the ordering of C0,C1,···,Cd?1,and then all vertices of V1are assigned.Let the ordering of V1be β.By Fact 2.1,we have an ordering ββ?of V(P(n,k)).We

denote β?=C(d?1)?,C(d?2)?,···,C0?,whereif i?is odd.There are some properties as follows.

Property 1 The ordering of V(P(n,k))is C0→ C1→ ···→ Cd?1→ C(d?1)?→ C(d?2)?→C0?(see Figure 1).

Property 2 The edge sets{E(Ci)|i=0,1,···,d?1}and{E[Ci,Ci+1]|i=0,1,···,(d?2)}∪{ECd?1,C0}are contained in E(P(n,k)[V1])which does not have a 1-edge,and the edge set{E[Ci?,C(i+1)?]|i?=0?,1?,···,(d ? 2)?} ∪ E[C(d?1)?,C0?]is contained in E(P(n,k)[V2])which does not have a k-edge.

Property 3 All k-edges can be embedded in one page without crossing(see Figure 2).

Property 4 Edges in E(V1,V2)do not cross each other(see Figure 4).

By Properties 1–4,we have k-edges and E[V1,V2]are embedded in two pages.Thus we only need to embed 1-edges in pages.

Claim 1 1-edges can be embedded in three pages without crossing.

Proof In the ordering of V(P(n,k)),if i?is even,E[Ci?,C(i+1)?]containsedges and they are{(jk+i)?,(jk+i+1)?},where j?goes from 0?to??1??and i?∈[(d?2)?]∪{0?}(mod n is omitted),which can be embedded in one page without crossing.If i is odd,the edges of E[Ci?,C(i+1)?]are{(jk+i)?,(jk+i+1)?},where j?goes from??1??to 0?and i?∈[(d?2)?]∪{0?},which can be embedded in another page without crossing.Next we can embed E[C(d?1)?,C0?]into two pages.The edge set{(d?1+ik)?,(d+ik)?}withi?(denoted by I-edges)can be assigned in one page and the other edges of E[C(d?1)?,C0?]which(denoted by II-edges)can be assigned in the other page.

By Property 3,Claim 1 and Lemma 2.1,we know that P(n,k)can be embedded in a 4-page book.

Page 1:II-edges.

Page 2:k-edges and

Page 3:i?is odd and I-edges.

Page 4:

Proof of Corollary 1.1 Ifk=2,sinceV2can be partitioned into two partsC0?andC1?,whereC0?=(0?,2?,4?,···,n?)andC0?=((n?1)?,(n?2)?,···,5?,3?,1?),all 1-edges{(0?,1?),(1?,2?),(2?,3?)···((n?2)?,(n?1)?),((n?1)?,0?)}can be embedded in two pages.SoP(n,k)can be embedded in a 3-page book.

Page 1:1-edges except the edge(n?1,0).

Page 2:k-edges and(n?1,0).

Page 3:E[V1,V2].

Proof of Theorem 1.2 LetC0=(0,2,···,n?4,n?2)andC1=(n?2+k,n?4+k,···,2+k,k)(modnis omitted)be the ordered vertex set ofV1,C0∩C1=?,andC0∪C1=V1.We putCiin the spine with the ordering ofC0,C1.Then all vertices ofV1are assigned.

Denote the vertex ordering ofV1byβ,and by Fact 2.1,we have an orderingββ?ofV(P(n,k)).Thus all vertices ofP(n,k)are assigned in the spine.In the ordering,1-edges can be embedded in four pages:(denoted by E1),{(2i)?,(2i+1)?}with(denoted by E2),{(k+2i)?,(k+2i+1)?}with(denoted by E3)and{(n?1+2i)?,i?}with(denoted by E4).k-edges can be embedded in three pages as follows.

k-edges can be embedded in three pages which are{2i,2i+k}withwith

By Lemma 2.1,we know that P(n,k)can be embedded in a 5-page book.

Next,we will embed P(n,k)when n is odd.It is more complicated.

Proof of Theorem 1.3

Case 1 When n is odd,k is even,and d=1.Let Cibe an ordered array and

C0= ···(0,k,···,(c? 1)k,ck ···),

C1= ···(ck+1,(c? 1)k+1···,k+1,0+1···),

···

Ci= ···(i,k+i,···,(c? 1)k+i,ck+i)···),i is even,Ci= ···(ck+i,(c? 1)k+i,···,k+i,0+i···),i is odd,

···

Ck?1= ···(ck+(k ?1),(c?1)k+(k ?1),···,k+(k ?1),0+(k ?1)···).

Thus|Ci|=c+1,c=q if ck+i

Claim 1|Ci|=q+1 with 0≤i≤r?1 and|Ci|=q with r?1

ProofLet Ci={v1,v2,···,vc}and Ci+1={vc+1,vc?1+1,···,v1+1}.From the structure of Ci,wefind that the vertex in Ci+1 is equal to Ci+1,0≤i≤r?2 and q+1=|C0|=|C1|= ···=|Cr?1|.Assume Cr?1={r?1,k+r?1,···,(q ?1)k+r?1,},and then Cr?1+1={qk+r,(q?1)k+r,···,k+r,r}.|Cr|=q because qk+r ≡ 0(mod n)and 0 ∈ C0.So q=|Cr|=|Cr+1|= ···=|Ck?1|.

Put Ciin the spine with the ordering of C0,C1,···,Ck?1,and then all vertices of V1are assigned.Let the ordering of V1be β.By Fact 2.1,we have an ordering ββ?of V(P(n,k)).

Therefore,each vertex of p(n,k)is assigned in the spine by the vertex set ordering ββ?.We have the following properties.

Property 1 The order of V(P(n,k))is C0→ C1→ ···→ Ck?1→ C(k?1)?→ C(k?2)?→···→ C0?(see Figure 5).

Property 2 The edge sets{E(Ci)|i=0,1,···,k?1}and{E(Ci?)|i?=0?,1?,···,(k?1)?}are contained in E(P(n,k)[V1]),and they contain no 1-edge.The edge set E[Ci?,Cj?]=E[Ci?,C(i+1)?]∪ E[C(k?1)?,C0?]∪ ((n ? k)?,0?)(i?,j?=0?,1?,···,(k ? 1)?)is contained in E(P(n,k)[V2]),and they contain no k-edge.

Property 3 Edges do not cross each other in E[V1,V2](see Figure 8).

Next,we embed 1-edges and k-edges of P(n,k)in 2s pages without crossing.

Claim 2 The k-edges can be embedded in 2s pages without crossing,where s=k?r.

Proof Let Ek(Ci)denote the k-edges in E(Ci).Similarly,Ek[Ci,Cj]denotes the k-edges in E[Ci,Cj].From the partition and the ordering of V1,we know that Ek[C0,Cs],Ek[Cs,C2s],···,can be embedded in two pages.Obviously,can be embedded in the same page.Similarly,under the vertex ordering,for i

Claim 3 Embedding of 1-edges needs three pages.

Proof Because of the vertex ordering and the structure of Ci?,1-edges are E[Ci?,C(i+1)?]∪E(C(k?1)?,C0)∪ ((n?1)?,0?)(i??=1).Obviously,the edge set E[Ci?,C(i+1)?](i?is even)can be embedded in one page.Similarly,when i?is odd,the embedding of E[Ci?,C(i+1)?]and E[C(k?1)?,E(C0?)]also needs one page.((n?1)?,0?)needs another page(see Figure 7).

Combining the above properties and claims,P(n,k)can be embedded in a(2s+1)-page book if d=1.

Case 2 When n is odd,k is even,and d?=1.Let Cibe an ordered array and

C0= ···(0,k,···,(c ? 1)k,ck ···),

C1= ···(ck+1,(c? 1)k+1,···,k+1,0+1···),

···

Ci= ···(0+i,k+i,···,(c? 1)k+i),ck+i···),i is even,Ci= ···(ck+i,(c? 1)k+i,···,k+i,0+i···),i is odd,

···Ck?1= ···(ck+k ?1,(c?1)k+k ?1,···,k+k ?1,0+k ?1···).

|Ci|=c+1,c=q if ck+i

The graph P(n,k)[V1]can be divided into d copies because(n,k)=d?=1.The copy containing 0 is denoted by G0,and the other copies are denoted by G1,G2,···,Gd?1.We know|V(Gi)|=with i=0,1,···,d?1 and V(Gi)=V(G0)+i,where V(G0)+i={v0+i=vi|vi∈V(G0),v0∈V(G0)}.If we only embed k-edges,each copy has the same k-edges embedding.

The vertex set V1can be assigned in the spine in this ordering C0,C1,···,Ck?1.Clearly,all vertices of V1are assigned.We use β to denote this ordering.By Fact 2.1,we have an ordering of V(P(n,k)),denoted by ββ?.Therefore,each vertex of P(n,k)is assigned in the spine and has a position by the vertex set ordering ββ?.We have the following properties.

Property 4The ordering of V(P(n,k))is C0→ C1→ ···→ Ck?1→ C(k?1)?→ ···→C(k?2)?···→ C1?→ C0?(see Figure 9).

Property 5 {E(Ci)|i=0,1,···,k ? 1}and{E[Ci,Ci+1]|i=0,1,···,(k ? 2)} ∪{E[Cd?1,C0]}are contained in E(P(n,k)[V1]),and then they contain no 1-edges.The edge set{E[Ci?,C(i+1)?]|i?=0?,1?,···,(k?2)?}∪{E[C(k?1)?,C0?]}is contained in E(P(n,k)[V2]),and then they contain no k-edges.

Property 6 Edges in E[V1,V2]do not cross each other(see Figure 12).

Now we embed the edges of P(n,k)in 2s+1 pages without crossing.

Claim 4 All k-edges can be embedded in 2s pages without crossing.

Proof Since ck+is+k≡(i+1)s(mod n),where ck+is+k∈Cisand(i+1)s∈C(i+1)s,webecause s is a multiple of d,and ordered array Cid={ck+id,(c?1)k+id,···,k+d,d}where i is even,and Cid={d,k+d,···,(c?1)k,ck+id}where i is odd.k-edges of G0can be embedded inpages in ββ?because ck+id+k=s+id ≡(i+)d(mod n),the number of Ci(i=0,1,···,s?1)in V[G0]is,ck+id is the first(when i is odd)or the last(when i is even)vertex of Cid,and(i+)d is the last(when i is odd)or the first(when i is even)vertex ofSince Giwith i=0,1,···,d ? 1 has the same k-edges embedding,all k-edges can be embedded in a(2s)-page book.Specially,if s=d,k-edges can be embedded in 2d pages.Then ck+id+k=s+id≡(i+1)d(mod n)and id∈Cid(see Figure 6).

Claim 5 All 1-edges can be embedded in three pages.

Proof The edge set E[Ci?,C(i+1)?],i?=0?,1?,···,(k?2),and E[C(k?1)?,C0?]can be embedded in three pages without crossing.When i?is even or odd,E[Ci?,C(i+1)?](i?from 0?to(k?2)?,i?is even or odd)can be embedded in one page.The edge(n?1,0)needs another page(see Figure 11).

Combining the above properties and claims,P(n,k)can be embedded in 2s+1 pages if d?=1.

Proof of Corollary 1.2 When k=2 and s=1,all k-edges can be embedded in two pages and 1-edges can be embedded in one of pages of the k-edges.By Lemma 2.1,the embedding of P(n,2)needs 3 pages.

Proof of Theorem 1.4Let C0={0,2,···,n ? 1}and C1={n ? 2,n ? 4,···,1}be the ordered vertex set of V1,C0∩C1=?,and C0∪C1=V1.We put Ciin the line with the ordering of C0,C1.So all vertices of V1are assigned.

Denote the vertex ordering of V1by β.By Fact 2.1,we have an ordering ββ?of V(P(n,k)).Therefore,each vertex of P(n,k)is assigned in the spine.

Note that 1-edges can be embedded in two pages.Next we embed k-edges.

The edge setcan be embedded in one page,and the edge set{1+2i,1+2i+k}with i∈can also be embedded in one page.Edges in the edge set{(n?k+2i,2i)}with i∈(denoted by A1)cross each other.Edges in the edge set{(n?2i,n?2i+k)}with(denoted by A2)also cross each other,while A1,A2do not cross each other.Since maxk-edges at most needpages to be embedded.

By Lemma 2.1,P(n,k)can be embedded inpages.

3 Conclusion

The connected graph G can be embedded in one page if and only if G is outplanar,and in two pages if and only if G is a subgraph of a Hamiltonian planar graph.So for a connected graph which is not an outplanar or a subhamiltonian planar graph,we have pn(G)≥3.A graph is planar if and only if it does not contain subdivision of either K3,3or K5,or it has no Kuratowski minor(a minor which is isomorphic to K3,3or K5).The general Peterson graph is not a planar graph for k?=1.For example,K5is a minor of P(5,2),so pn(P(n,k))≥3.In this paper,we completely describe the upper bounds of pn(P(n,k)),and in some situation,pn(P(n,k))=3,which is the best possible.

Acknowledgements The authors are grateful to the referees for their valuable comments and suggestions which significantly helped to improve the paper.Also,they are thankful to the referees and editors for their help.

[1]Bondy,J.A.and Murty,U.S.R.,Graph Theory with Application,Macmillan,London,1976.

[2]Bilski,T.,Optimum embedding of complete graphs in books,Discrete Math.,182,1998,21–28.

[3]Chung,F.R.K.,Leighton,F.T.and Rosenberg,A.L.,Embedding graph in books:A layout problem with applications to VLSI design,SIAM J.Algebr.Discrete Methods,8(1),1987,33–58.

[4]Endo,T.,The page number of toroidal graphs is at most seven,Discrete Math.,175,1997,87–96.

[5]Nakamoto,A.and Ozeki,K.,Book embedding of toroidal bipartite graphs,SIAM J.Discrete Math.,26(2),2012,661–669.

[6]Fang,J.F.and Lai,K.C.,Embedding the incomplete hypercube in books,Inf.Process.Lett.,96,2005,1–6.

[7]Enomoto,H.,Nakamigawa,T.and Ota,K.,On the page number of complete bipartite graphs,J.Comb.Theory B,71,1997,111–120.

[8]Sperfeld,K.,On the page number of complete odd-partite graphs,Discrete Math.,313,2013,1689–1696.

[9]Swaminathan,R.,Giraraj,D.and Bhatia,D.K.,The page number of the class of bandwidth-k graphs is k ?1,Inf.Process.Lett.,55,1995,71–74.

[10]Yang,W.H.and Meng,J.X.,Embedding connected double-loop networks with even cardinality in books,Appl.Math.Lett.,22,2009,1458–1461.

[11]Garey,M.R.,Johnson,D.S.,Miller,G.L.and Papadimitrion,C.H.,The complexity of coloring circular arcs and chords,SIAM J.Algebr.Discrete Methods,1(2),1980,216–217.

[12]Kapoor,N.,Russell,M.,Stojmenovic,I.and Zomaya,A.Y.,A genetic algorithm for finding the page number of interconnection networks,JPDC,62,2002,267–283.

[13]Shahrokhi,F.and Shi,W.,On crossing sets,disjiont sets and page number,J.Algorithms,34,2000,40–53.

[14]Wood,D.R.,Degree constrained book embeddings,J.Algorithms,45,2002,144–154.

[15]Watkins,M.E.,A theorem on Tait colorings with an application to generalized Petersen graphs,J.Comb.Theory,6,1969,152–164.

[16]Bemhart,F.and Kainen,B.,The book thickness of a graph.J.Comb.Theory B,27,1979,320–331.

[17]Yannakakis,M.,Embedding planar graph in four pages.J.Comput.Syst.Sci.,38,1989,36–37.

[18]Ollmann,L.T.,On the book thicknesses of various graphs,in Hoffman,F.,Levow,R.B.and Thomas,R.S.D.,editors,Proc.4th Southeastern Conference on Combinatorics,Graph Theory and Computing,Vol.VIII of Congr.Numer.,Utilitas Math.,1973.