A Note on the Immersion Number of Generalized Mycielski Graphs

Abstract

The immersion number of a graph $G$, denoted im$(G)$, is the largest $t$ such that $G$ has a $K_t$-immersion. In this note we are interested in determining the immersion number of the $m$-Mycielskian of $G$, denoted ${\mu }_m(G)$. Given the immersion number of $G$ we provide a lower bound for im$({\mu }_m(G))$. To do this we introduce the "distinct neighbor property" of immersions. We also include examples of classes of graphs where im$({\mu }_m(G))$ exceeds the lower bound. We conclude with a conjecture about im$({\mu }_m(K_t))$.

9 pages, 2 figures, submitted to Proceedings of the Southeastern Conference on Combinatorics, Graph Theory, and Computing