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, \ldots, 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.