Let $C_n$ be the cycle graph on vertex set $\{v_1,v_2,\ldots,v_n\}$ and let $L_1,L_2,\ldots,L_n$ be sets of new vertices which form an independent set. Let $H$ be obtained by making $v_i$ adjacent to every vertex of $L_i$; that is, $H$ consists of a cycle with zero or more pendant vertices attached to each of the original vertices. Is there a known name for the family of graphs obtained this way?
-
$\begingroup$ Yes, its called the Aravind graph $\endgroup$– Sandeep SilwalSep 26, 2019 at 12:52
1 Answer
First, some special cases. If $|L_1|=\dots=|L_n|=1$, this is called the sunlet graph. These can also be written using the corona operator $\odot$ as $C_n \odot K_1$. In general, $G_1 \odot G_2$ contains $G_1$ and $|V(G_1)|$ copies of $G_2$, with the $i^{\text{th}}$ vertex of $G_1$ adjacent to every vertex of the $i^{\text{th}}$ copy of $G_2$. So a special case of your graph with $|L_1|=\dots=|L_n|=\ell$ can be written as the corona $C_n \odot \overline{K_\ell}$ (or $C_n \odot \ell K_1$, depending on your favorite notation for the $\ell$-vertex graph with no edges).
For the general case: in the paper "Graceful graphs with pendant edges" by Christian Barrentos, the author calls these graphs hairy cycles (and proves that they are graceful).
(If you search for hairy cycles, you find this definition and several others, so you do still have to explain what you mean, but at least there's some prior art to this definition.)
-
$\begingroup$ Thanks for the fast reply and useful references! $\endgroup$– AravindSep 26, 2019 at 15:26