Cellular embeddings of line graphs and lifts
Bull. Korean Math. Soc. 2002 Vol. 39, No. 1, 175-184
Published online March 1, 2002
Jin Hwan Kim
Yeungnam University
Abstract : A cellular embedding of a graph $G$ into an orientable surface $\BS$ can be considered as a cellular decomposition of $\BS$ into 0-cells, 1-cells and 2-cells and vise versa, in which 0-cells and 1-cells form a graph $G$ and this decomposition of $\BS$ is called a map in $\BS$ with underlying graph $G$. For a map $\mathcal{M}$ with underlying graph $G$, we define a natural rotation on the line graph of the graph $G$ and we introduce the line map for $\mathcal{M}$. We find the genus of the supporting surface of the line map for a map and we give a characterization for the line map to be embedded in the sphere. Moreover we show that the line map for any lift of a map $\mathcal{M}$ is map-isomorphic to a lift of the line map for $\mathcal{M}$.
Keywords : graph, cellular embedding, permutation voltage assignment, lift, rotation, map, graph-isomorphism, map-isomorphism, line graph, line map
MSC numbers : 05C10
Downloads: Full-text PDF  

Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd