Embedding the Myceilski of a Graph and the Amalgamation of Two Graphs in Pages

Mahavir Banukumar1
1Department of Mathematics, A. M. Jain College, Chennai 600114

Abstract

A book consists of a line in the 3-dimensional space, called the spine, and a number of pages, each a half-plane with the spine as boundary. A book embedding \((\pi, p)\) of a graph consists of a linear ordering \(\pi\) of vertices, called the spine ordering, along the spine of a book and an assignment \(p\) of edges to pages so that edges assigned to the same page can be drawn on that page without crossing. That is, we cannot find vertices \(u, v, x, y\) with \(\pi(u) < \pi(x) < \pi(v) 2\) and \(C_n\) are given. If \(G\) is any graph, an upper bound for the page number of the Mycielski of \(G\) is given. When \(G\) and \(H\) are any two graphs with page number \(k\) and \(l\), it is proved that the amalgamation of \(G\) and \(H\) can be embedded in a \max(k, l)\) pages. Further, we remark that the amalgamation of \(G\) with itself requires the same number of pages as \(G\), irrespective of the vertices identified in the two copies of \(G\), to form an amalgamation.