A study of typenumber in book-embedding

Abstract

The type of a vertex v in a p-page book-embedding is the p x 2 matrix of nonnegative integers [GRAPHICS] where l(v,i) (respectively, r(v,i)) is the number of edges incident to v that connect on page i to vertices lying to the left (respectively, to the right) of v. The typenumber of a graph G, T(G), is the minimum number of different types among all the book-embeddings of G. In this paper, we disprove the conjecture by J. Buss et. al. which says for n greater than or equal to 4, T(L-n) is not less than 5 and prove that T(L-n) = 4 for n greater than or equal to 3.