4
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Yes, its called the Aravind graph $\endgroup$ Sep 26, 2019 at 12:52

1 Answer 1

3
$\begingroup$

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.)

$\endgroup$
1
  • $\begingroup$ Thanks for the fast reply and useful references! $\endgroup$
    – Aravind
    Sep 26, 2019 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.