Generalized Booksand $C_m$-Snakes are Prime Graphs

Abstract

A graph $G$ on $n$ vertices has a prime labeling if its vertices can be assigned the distinct labels $1,2,\dots ,n$ such that for every edge $xy$ in $G$, the labels of $x$ and $y$ are relatively prime. In this paper, we show that generalized books and $C_m$ snakes all have prime labelings. In the process, we demonstrate a way to build new prime graphs from old ones.