http://dx.doi.org/10.7494/OpMath.2011.31.4.533

RECURSIVELY ARBITRARILY
VERTEX-DECOMPOSABLE SUNS

Olivier Baudon, Frédéric Gilbert, Mariusz Woźniak

**Abstract.** A graph $G = (V, E)$ is arbitrarily vertex decomposable if for any sequence $\tau$ of positive integers adding up to $|V|$, there is a sequence of vertex-disjoint subsets of $V$ whose orders are given by $\tau$, and which induce connected graphs. The aim of this paper is to study the recursive version of this problem on a special class of graphs called suns. This paper is a complement of [O. Baudon, F. Gilbert, M. Woźniak, *Recursively arbitrarily vertex-decomposable graphs*, research report, 2010].

**Keywords:** arbitrarily vertex-decomposable graphs (AVD), recursively AVD graphs.

**Mathematics Subject Classification:** 05C99, 68R10.

# 1. TERMINOLOGY AND PRELIMINARY RESULTS

In this paper, we deal only with simple graphs, that means, graphs without loops or multiple edges. We denote by $n$ the number of vertices, also called *order* of the graph and by $m$ the number of edges. If $G = (V, E)$ and $A \subseteq V$, $G[A]$ will denote the subgraph of $G$ induced by $A$. For more definitions on graphs, please refer to [2].

## 1.1. ARBITRARILY VERTEX-DECOMPOSABLE GRAPHS

Let $n$, $\tau_1, \dots, \tau_k$ be positive integers such that $\tau_1 + \dots + \tau_k = n$. $\tau = (\tau_1, \dots, \tau_k)$ is called a *decomposition* of $n$. If the size of the decomposition is pertinent, we would precise *k-decomposition*.

Let $G = (V, E)$ be a graph of order $n$, and $\tau$ a $k$-decomposition of $n$. $G$ is
$\tau$-vertex-decomposable iff it exists a partition of $V$: $V_1, \dots, V_k$ such that for each
$i, 1 \le i \le k$

• $|V_i| = \tau_i,$

• $G[V_i]$ is connected.

A graph $G = (V, E)$ of order $n$ is arbitrarily vertex-decomposable (in short AVD) iff for each decomposition $\tau$ of $n$, $G$ is $\tau$-vertex-decomposable.
## 1.2. RECURSIVELY ARBITRARILY VERTEX-DECOMPOSABLE GRAPHS

**Definition 1.1.** A graph $G = (V, E)$ with order $n$ is recursively arbitrarily vertex-decomposable (in short R-AVD) iff:

* $G = K_1$ or

* $G$ is connected and for each decomposition $\tau = (\tau_1, \dots, \tau_k)$ of $n$, $k \ge 2$, it exists a partition of $V$: $V_1, \dots, V_k$ such that for all $i, 1 \le i \le k$:

- $|V_i| = \tau_i$

- $G[V_i]$ is R-AVD.

**Remark 1.2.** A graph $G = (V, E)$ of order $n$ is R-AVD iff for each integer $1 \le \lambda \le \lfloor \frac{n}{2} \rfloor$, it exists a subset $V_\lambda$ of $V$ such that:

* $|V_\lambda| = \lambda$,

* $G[V_\lambda]$ is R-AVD,

* $G[V \setminus V_\lambda]$ is R-AVD.

## 1.3. FAMILIES OF GRAPHS

We present here some families of graphs and their notations, used in the further sections.

Let $a$ be a positive integer. $P_a$ denotes the path of order $a$, $C_a$ the cycle of order $a$ (cp. Figures 1a and 1b).

A $k$-pode $T_k(t_1, \dots, t_k)$ is a tree of order $1 + \sum_{i=1}^k t_i$ composed by $k$ paths of order respectively $t_1, \dots, t_k$, connected to a unique node, called the *root* of the $k$-pode (cp. Figure 1c).

Let $a$ and $b$ be two positive integers. A caterpillar Cat$(a, b)$ is a tree of order $a+b$, composed by three paths of order $a, b$ and 2, sharing exactly one node, called the *root* of the caterpillar. Cat$(a, b)$ is isomorphic to $T_3(a-1, b-1, 1)$ (cp. Figure 1d).

A sun with $r$ rays is a graph of order $n \ge 2r$ with $r$ hanging vertices $u_1, \dots, u_r$ whose deletion yields a cycle $C_{n-r}$, and each vertex $v_i$ adjacent to $u_i$ is of degree three. If the sequence of vertices $v_i$ is situated on the cycle $C_{n-r}$ in such a way that there are exactly $a_i \ge 0$ vertices, each of degree two, between $v_i$ and $v_{i+1}$, $i = 1, \dots, r$ (the indices taken modulo $r$), then this sun is denoted by $\text{Sun}(a_1, \dots, a_r)$, and is unique up to isomorphism (cp. Figure 1e).

Note that the order of $\text{Sun}(a_1, \dots, a_r)$ equals $n = 2r + a_1 + \dots + a_r$.

## 1.4. ON-LINE ARBITRARILY VERTEX-DECOMPOSABLE GRAPHS

The notion of on-line arbitrarily vertex decomposable graph has been introduced by Horňák and al. in [3].

Let $G = (V, E)$ be a graph. Imagine now the following decomposition procedure consisting of $k$ stages, where $k$ is a random variable attaining values from $[1, n]$. In the $i^{th}$ stage, where $i \in [1, k]$, a positive integer $\tau_i$ arrives and we have to choose a subset $V_i$ of $V$ of order $\tau_i$ that is disjoint from all subsets of $V$ chosen in previous stages (without a possibility of changing the choice in the future).
<figure><img src="image_1.png" /><figcaption>Fig. 1. Examples of graphs</figcaption></figure>

More precisely, for every partial sequence $(\tau_1, \dots, \tau_i)$ whose sum is less than $n$, there is a sequence $(V_1, \dots, V_i)$ of disjoint subsets of $V$ such that for $1 \le j \le i$, $|V_j| = \tau_j$, with the following property: for all sequences $(\tau'_1, \dots, \tau'_k)$ with $k \ge i$ and summing to $n$, such that $\tau'_r = \tau_r$ for $1 \le r \le i$, there is a decomposition of $V$ into disjoint subsets $V'_1, \dots, V'_k$ with $|V'_j| = \tau'_j$ and $G[V'_j]$ connected, for all $j$, and $V'_j = V_j$ for $1 \le j \le i$.

**Definition 1.3 ([3])**. If the decomposition procedure can be accomplished for any (random) sequence of positive integers $(\tau_1, \dots, \tau_k)$ adding up to $n$, the graph $G$ is said to be *on-line arbitrarily vertex-decomposable*, (in short *OL-AVD*).

**Lemma 1.4 ([3])**. A graph $G = (V, E)$ of order $n$ is OL-AVD iff for each integer $1 \le \lambda \le n-1$, it exists a subset $V_\lambda$ of $V$ such that

* $|V_\lambda| = \lambda$,

* $G[V_\lambda]$ is connected,

* $G[V \setminus V_\lambda]$ is OL-AVD.

**Remark 1.5.** A straightforward consequence of Lemma 1.4 and Remark 1.2 is that every R-AVDgraph is OL-AVD.

The opposite is not true. For example, the caterpillar Cat(8, 11) is OL-AVD [3], but not R-AVD [1].

The next result gives a complete characterization of OL-AVD suns.
**Theorem 1.6 ([4]).** A sun with one ray is always OL-AVD.

A sun with two rays Sun (a, b) is OL-AVD iff a and b take values given in Table 1a.

A sun with three rays Sun (a, b, c) is OL-AVD iff a, b and c take values given in Table 1b.

A sun with four rays is OL-AVD iff it is isomorphic to Sun (0, 0, 1, d), where $d \equiv 2, 4 (\text{mod } 6)$.

A sun with five or more rays is never OL-AVD.

<table><caption>**Table 1.** Values for OL-AVD suns</caption><thead><tr><th>a</th><th>b</th></tr></thead><tbody><tr><td>0</td><td>arbitrary</td></tr><tr><td>1, 3</td><td>≡ 0 (mod 2)</td></tr><tr><td>2</td><td>≠ 3 (mod 6), 3, 9, 21</td></tr><tr><td>4</td><td>≡ 2, 4 (mod 6), [4, 19]\{15}</td></tr><tr><td>5</td><td>≡ 2, 4 (mod 6), 6, 18</td></tr><tr><td>6</td><td>6, 7, 8, 10, 11, 12, 14, 16</td></tr><tr><td>7</td><td>8, 10, 12, 14, 16</td></tr><tr><td>8</td><td>8, 9, 10, 11, 12</td></tr><tr><td>9</td><td>10, 12</td></tr></tbody></table>

(a) Values a, b ($b \ge a$), such that Sun (a, b) is OL-AVD

<table><thead><tr><th>a</th><th>b</th><th>c</th></tr></thead><tbody><tr><td>0</td><td></td><td>≡ 1, 2 (mod 3)</td></tr><tr><td>1</td><td></td><td>≡ 0 (mod 2)</td></tr><tr><td>2</td><td></td><td>≡ 2, 4 (mod 6), 3, 6, 7, 11, 18, 19</td></tr><tr><td>3</td><td></td><td>≡ 2, 4 (mod 6)</td></tr><tr><td>4</td><td></td><td>4, 5, 6, 8, 10, 11, 12, 14, 16</td></tr><tr><td>5</td><td></td><td>6, 8, 16</td></tr><tr><td>6, 7</td><td></td><td>8, 10</td></tr><tr><td>8</td><td></td><td>8, 9</td></tr><tr><td>1</td><td>2</td><td>≡ 2, 4 (mod 6), 6, 18</td></tr><tr><td>2</td><td>3</td><td>4, 8, 16</td></tr></tbody></table>

(b) Values a, b, c ($c \ge b \ge a$), such that Sun (a, b, c) is OL-AVD

## 1.5. RECURSIVELY ARBITRARILY VERTEX-DECOMPOSABLE TREES

**Theorem 1.7 ([1]).** A tree T is R-AVD if and only if either T is a path or T is a caterpillar Cat (a, b) with a and b given in Table 2 or T is the 3-pode $T_3(2, 4, 6)$.

<table><caption>**Table 2.** Values a, b ($b \ge a$), such that Cat (a, b) is R-AVD</caption><thead><tr><th>a</th><th>b</th></tr></thead><tbody><tr><td>2, 4</td><td>≡ 1 (mod 2)</td></tr><tr><td>3</td><td>≡ 1, 2 (mod 3)</td></tr><tr><td>5</td><td>6, 7, 9, 11, 14, 19</td></tr><tr><td>6</td><td>7</td></tr><tr><td>7</td><td>8, 9, 11, 13, 15</td></tr></tbody></table>

## 2. RECURSIVELY ARBITRARILY VERTEX-DECOMPOSABLE SUNS

This section presents the main result of this paper, a complete characterization of R-AVD suns.
**Theorem 2.1.**

A sun with one ray is always R-AVD.

A sun with two rays Sun (a, b) is R-AVD if and only if a and b take values given in Table 3a.

A sun with three rays Sun (a, b, c) is R-AVD if and only if a, b and c take values given in Table 3b.

A sun with four rays is R-AVD if and only if it is isomorphic to Sun (0, 0, 1, 2) or to Sun (0, 0, 1, 4).

A sun with five or more rays in never R-AVD.

<table><caption>**Table 3.** Values for R-AVD suns</caption><thead><tr><th>a</th><th>b</th><th>a</th><th>b</th><th>c</th></tr></thead><tbody><tr><td>0</td><td>arbitrary</td><td>0</td><td>≡ 1, 2 (mod 3)</td><td></td></tr><tr><td>1</td><td>≡ 0 (mod 2)</td><td>1</td><td>≡ 0 (mod 2)</td><td></td></tr><tr><td>2</td><td>≠ 0 (mod 3), 3, 6, 9, 12, 18, 21, 24, 36</td><td>2</td><td>2, 3, 4, 6, 7, 8, 10, 11, 14, 16, 18, 19</td><td></td></tr><tr><td>3</td><td>≡ 0 (mod 2)</td><td>3</td><td>4, 8, 10</td><td></td></tr><tr><td>4</td><td>4 ≤ b ≤ 19 except for b = 15, ≡ 2, 4 (mod 6) with 20 ≤ b ≤ 46</td><td>4</td><td>4, 5, 6, 8, 10, 11, 12, 14, 16</td><td></td></tr><tr><td>5</td><td>≡ 2, 4 (mod 6) with 8 ≤ b ≤ 32, 6, 18</td><td>5</td><td>6</td><td></td></tr><tr><td>6</td><td>6, 7, 8, 10, 11, 12, 14, 16</td><td>1</td><td>2, 4, 6, 8, 10, 14, 16, 18</td><td></td></tr><tr><td></td><td></td><td>2</td><td>3</td><td>4</td></tr></tbody></table>

(a) Values a, b (b ≥ a), such that Sun (a, b) is R-AVD

(b) Values a, b, c (c ≥ b ≥ a), such that Sun (a, b, c) is R-AVD

*Proof.* Since every R-AVD graph is also OL-AVD, so, we shall use the complete characterization of OL-AVD suns given in Theorem 1.6, and Remark 1.2.

The labelling used in the proof follows that one from Figure 2.

<figure><img src="image_2.png" /><figcaption>**Fig. 2.** Sun (a, b, ...)</figcaption></figure>
**Sun with one ray.** A sun with one ray is traceable. Thus, it is R-AVD.

**Sun with two rays.** Without loss of generality, we consider Sun (a,b) with $b \ge a$.

• Sun (0, b) is traceable and then is R-AVD.

• Sun (1, b) contains Cat (2, b+3) as partial graph. Thus, Sun (1, b) with $b \equiv 0 \pmod{2}$ is R-AVD.

• Sun (2, b) is OL-AVD only for $b \not\equiv 3 \pmod{6}$ or $b = 3, 9, 21$.

– Sun (2, b) contains Cat (3, b + 3) as spanning tree and thus is R-AVD for $b \not\equiv 0 \pmod{3}$.

– If $b = 6k$ with $k = 5$ or $k \ge 7$, it is not possible to find a partition into two R-AVD subgraphs of size 18 and $n-18$.

– If $b \in \{3, 6, 9, 12, 18, 21, 24, 36\}$, then Sun (2, b) is R-AVD and the values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ are given in Table 4.

• Sun (3, b) contains Cat (4, b + 1) as a spanning tree. Thus, it is R-AVD for $b \equiv 0 \pmod{2}$.

• Sun (4, b) is OL-AVD only for $b \equiv 2, 4 \pmod{6}$ or $b \in \{4, \dots, 19\} \setminus \{15\}$.

– Sun (4, b) contains Cat (5, b + 3) as a spanning tree. Thus, it is R-AVD for $b \in \{4, 6, 8, 11, 16\}$.

– Similarly, Sun (4, b) contains Cat (7, b+1) as a spanning tree. Thus, it is R-AVD for $b \in \{7, 10, 12, 14\}$.

– Let us consider the case where $b \equiv 2, 4 \pmod{6}$.

* If $b \ge 50$, then $n = b + 8 \ge 58$. Then, we have to consider the case $\lambda = 30$ with $n - \lambda \ge 28$. Because there is no caterpillar with order 30, $G[V_\lambda]$ must be a path and $G[V\setminus V_\lambda]$ a caterpillar Cat (5, x) or Cat (7, x). But such a caterpillar has a maximum order 24. Thus, if $b \ge 50$, Sun (4, b) cannot be R-AVD.

* For $b \equiv 2, 4 \pmod{6}$, $20 \le b \le 46$, all the Sun (4, b) are R-AVD and the values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ are given in Table 5.

– For the last possible values of $b$, that is $b \in \{5, 9, 13, 17, 18, 19\}$, Sun (4, b) is R-AVD and the values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ are given in Table 5.

• Sun (5, b) is OL-AVD only for $b \equiv 2, 4 \pmod{6}$ or $b \in \{6, 18\}$.

– Consider the case $b \equiv 2, 4 \pmod{6}$. For $\lambda = 18$, the only possibility is that $G[V_{18}] = P_{18}$. But in that case, $G[V\setminus V_{18}]$ must be a caterpillar Cat (6, x) or Cat (8, x), which is impossible for $n - 18 \ge 14$, that is $n \ge 32$ and $b \ge 23$. Thus Sun (5, b) may be R-AVD only for $b \equiv 2, 4 \pmod{6}$ with $8 \le b \le 22$ or $b \in \{6, 18\}$.

– For all the remaining values of $b$, that is $b \in \{6, 8, 10, 14, 16, 18, 20, 22\}$, Sun (5, b) is R-AVD and the values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ are given in Table 6.

• Sun (6, b) is OL-AVD only for $b \in \{6, 7, 8, 10, 11, 12, 14, 16\}$.

– Observe that Sun (6, b) contains, as a spanning tree, the caterpillar Cat (7, b+3). Thus, Sun (a, b) is R-AVD for $b \in \{6, 8, 10, 12\}$.

– For all the remaining values of $b$, that is $b \in \{7, 11, 14, 16\}$, Sun (6, b) is R-AVD and the values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ are given in Table 7.
* Sun (7, b) is OL-AVD only for $b \in \{8, 10, 12, 14, 16\}$. For all of these values of b, it is not possible to find an edge $\{w_1, w_2\}$ such that $G[V\setminus\{w_1, w_2\}]$ is R-AVD.

* Sun (8, b) is OL-AVD only for $b \in \{8, 9, 10, 11, 12\}$.

- For $b \in \{8, 10, 11, 12\}$, it is not possible to find a set of size 3 $V_3$ such that both $G[V_3]$ and $G[V\setminus V_3]$ are R-AVD.

- For $b = 9$, it is not possible to find an edge $\{w_1, w_2\}$ such that $G[V\setminus\{w_1, w_2\}]$ is R-AVD.

* Sun (9, b) is OL-AVD only for $b \in \{10, 12\}$. For these two values of b, it is not possible to find an edge $\{w_1, w_2\}$ such that $G[V\setminus\{w_1, w_2\}]$ is R-AVD.

<table><caption>**Table 4.** Values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ for Sun (2, b)</caption><thead><tr><th>b</th><th>λ</th><th>V<sub>λ</sub></th><th>G[V<sub>λ</sub>]</th><th>G[V\V<sub>λ</sub>]</th></tr></thead><tbody><tr><td rowspan="2">3, 6, 9, 12, 18, 21, 24, 36</td><td>1</td><td>{u<sub>1</sub>}</td><td>P<sub>1</sub></td><td rowspan="2">sun with one ray</td></tr><tr><td>2</td><td>{x<sub>1</sub>, x<sub>2</sub>}</td><td>P<sub>2</sub></td></tr><tr><td>3</td><td rowspan="3">3</td><td>{x<sub>3</sub>, x<sub>4</sub>, x<sub>5</sub>}</td><td>P<sub>3</sub></td><td>P<sub>6</sub></td></tr><tr><td>6, 12, 18, 24, 36</td><td>{x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>}</td><td>P<sub>3</sub></td><td>Cat (2, b + 1)</td></tr><tr><td>9, 21</td><td>{x<sub>a+b-2</sub>, x<sub>a+b-1</sub>, x<sub>a+b</sub>}</td><td>P<sub>3</sub></td><td>Cat (5, b - 2)</td></tr><tr><td>3, 6, 9, 12, 18, 21, 24, 36</td><td>4</td><td>{u<sub>1</sub>, 1<sub>2</sub>, x<sub>1</sub>, x<sub>2</sub>}</td><td>P<sub>4</sub></td><td>P<sub>b+2</sub></td></tr><tr><td rowspan="2">6, 9, 12, 18, 21, 24, 36</td><td>5</td><td>{x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>3</sub>}</td><td>Cat (2, 3)</td><td>P<sub>b+1</sub></td></tr><tr><td>6</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>}</td><td>P<sub>6</sub></td><td>P<sub>b</sub></td></tr><tr><td>9, 12, 18, 21, 24, 36</td><td>7</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>3</sub>}</td><td>Cat (2, 5)</td><td>P<sub>b-1</sub></td></tr><tr><td rowspan="2">12, 18, 21, 24, 36</td><td>8</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>3</sub>, x<sub>4</sub>}</td><td>Cat (3, 5)</td><td>P<sub>b-2</sub></td></tr><tr><td>9</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>3</sub>, x<sub>4</sub>, x<sub>5</sub>}</td><td>Cat (4, 5)</td><td>P<sub>b-3</sub></td></tr><tr><td rowspan="3">18, 21, 24, 36</td><td>10</td><td>{x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>3</sub>, ..., x<sub>8</sub>}</td><td>Cat (3, 7)</td><td>P<sub>b-4</sub></td></tr><tr><td>11</td><td>{x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>3</sub>, ..., x<sub>9</sub>}</td><td>Cat (3, 8)</td><td>P<sub>b-5</sub></td></tr><tr><td>12</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>3</sub>, ..., x<sub>8</sub>}</td><td>Cat (5, 7)</td><td>P<sub>b-6</sub></td></tr><tr><td>21, 24, 36</td><td>13</td><td>{x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>3</sub>, ..., x<sub>11</sub>}</td><td>Cat (3, 10)</td><td>P<sub>b-7</sub></td></tr><tr><td rowspan="2">24, 36</td><td>14</td><td>{x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>3</sub>, ..., x<sub>12</sub>}</td><td>Cat (3, 11)</td><td>P<sub>b-8</sub></td></tr><tr><td>15</td><td>{x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>3</sub>, ..., x<sub>14</sub>}</td><td>Cat (2, 13)</td><td>Cat (2, b - 11)</td></tr><tr><td rowspan="6">36</td><td>16</td><td>{x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>3</sub>, ..., x<sub>14</sub>}</td><td>Cat (3, 13)</td><td>P<sub>26</sub></td></tr><tr><td>17</td><td>{x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>3</sub>, ..., x<sub>15</sub>}</td><td>Cat (3, 14)</td><td>P<sub>25</sub></td></tr><tr><td>18</td><td>{x<sub>21</sub>, ..., x<sub>38</sub>}</td><td>P<sub>18</sub></td><td>Cat (5, 19)</td></tr><tr><td>19</td><td>{x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>3</sub>, ..., x<sub>17</sub>}</td><td>Cat (3, 16)</td><td>P<sub>23</sub></td></tr><tr><td>20</td><td>{x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>3</sub>, ..., x<sub>18</sub>}</td><td>Cat (3, 17)</td><td>P<sub>22</sub></td></tr><tr><td>21</td><td>{x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>3</sub>, ..., x<sub>20</sub>}</td><td>Cat (2, 19)</td><td>Cat (2, 19)</td></tr></tbody></table>

**Sun with three rays.** Without loss of generality, we consider Sun (a,b,c) with $c \ge b \ge a$.

* Sun (0,0,c) is OL-AVD only for $c \equiv 1, 2 \pmod 3$. Because Sun (0,0,c) contains Cat (3, c + 3) as a spanning tree, thus it is also R-AVD for $c \equiv 1, 2 \pmod 3$.

* Sun (0,1,c) is OL-AVD only for $c \equiv 0 \pmod 2$. Because Sun (0,1,c) contains Cat (4, c + 3) as a spanning tree, thus it is also R-AVD for $c \equiv 0 \pmod 2$.

* Sun (0,2,c) is OL-AVD only for $c \equiv 2, 4 \pmod 6$ or $c \in \{3, 6, 7, 11, 18, 19\}$.
<table><caption>Table 5. Values of $G[V_λ]$ and $G[V \setminus V_λ]$ for some Sun (4, b)</caption><thead><tr><th>b</th><th>λ</th><th>V<sub>λ</sub></th><th>G[V<sub>λ</sub>]</th><th>G[V \ V<sub>λ</sub>]</th></tr></thead><tbody><tr><td>5, 9, 13, 17, 18, 19<br>b ≡ 2, 4 (mod 6), 20 ≤ b ≤ 46</td><td>1</td><td>{u<sub>1</sub>}</td><td>P<sub>1</sub></td><td>sun with<br>one ray</td></tr><tr><td>5, 13, 17, 19<br>b ≡ 2, 4 (mod 6), 20 ≤ b ≤ 46</td><td>2</td><td>{x<sub>1</sub>, x<sub>2</sub>}</td><td>P<sub>2</sub></td><td>Cat (3, b + 3)</td></tr><tr><td>9</td><td></td><td>{x<sub>5</sub>, x<sub>6</sub>}</td><td>P<sub>2</sub></td><td>Cat (7, 8)</td></tr><tr><td>18</td><td></td><td>{u<sub>1</sub>, v<sub>1</sub>}</td><td>P<sub>2</sub></td><td>Cat (5, 19)</td></tr><tr><td>5, 13, 17</td><td>3</td><td>{x<sub>5</sub>, x<sub>6</sub>, x<sub>7</sub>}</td><td>P<sub>3</sub></td><td>Cat (7, b − 2)</td></tr><tr><td>9, 19</td><td></td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>5</sub>}</td><td>P<sub>3</sub></td><td>Cat (5, b)</td></tr><tr><td>18<br>b ≡ 2, 4 (mod 6), 20 ≤ b ≤ 46</td><td>4</td><td>{x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>}</td><td>P<sub>3</sub></td><td>Cat (2, b + 3)</td></tr><tr><td>5, 9, 13, 17, 18, 19<br>b ≡ 2, 4 (mod 6), 20 ≤ b ≤ 46</td><td>4</td><td>{x<sub>1</sub>, ..., x<sub>4</sub>}</td><td>P<sub>4</sub></td><td>P<sub>b+4</sub></td></tr><tr><td>5, 13, 17, 19</td><td>5</td><td>{x<sub>3</sub>, x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>}</td><td>Cat (2, 3)</td><td>Cat (3, b)</td></tr><tr><td>9</td><td></td><td>{x<sub>5</sub>, ..., x<sub>9</sub>}</td><td>P<sub>5</sub></td><td>Cat (5, 7)</td></tr><tr><td>18<br>b ≡ 2, 4 (mod 6), 20 ≤ b ≤ 46</td><td>6</td><td>{x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, x<sub>6</sub>}</td><td>Cat (2, 3)</td><td>Cat (4, b − 1)</td></tr><tr><td>5, 9, 13, 17, 18, 19<br>b ≡ 2, 4 (mod 6), 20 ≤ b ≤ 46</td><td>6</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>, ..., x<sub>4</sub>}</td><td>P<sub>6</sub></td><td>P<sub>b+2</sub></td></tr><tr><td>9, 13, 19</td><td>7</td><td>{x<sub>3</sub>, x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, x<sub>6</sub>, x<sub>7</sub>}</td><td>Cat (3, 4)</td><td>Cat (3, b − 2)</td></tr><tr><td>17</td><td></td><td>{x<sub>15</sub>, ..., x<sub>21</sub>}</td><td>P<sub>7</sub></td><td>Cat (7, 11)</td></tr><tr><td>18<br>b ≡ 2, 4 (mod 6), 20 ≤ b ≤ 46</td><td>8</td><td>{x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>8</sub>}</td><td>Cat (2, 5)</td><td>Cat (4, b − 3)</td></tr><tr><td>9, 13, 17, 18, 19<br>b ≡ 2, 4 (mod 6), 20 ≤ b ≤ 46</td><td>8</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>}</td><td>P<sub>8</sub></td><td>P<sub>b</sub></td></tr><tr><td>13, 17, 18, 19<br>b ≡ 2, 4 (mod 6), 20 ≤ b ≤ 46</td><td>9</td><td>{x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, x<sub>6</sub>, x<sub>7</sub>}</td><td>Cat (4, 5)</td><td>P<sub>b-1</sub></td></tr><tr><td>10</td><td></td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, x<sub>6</sub>}</td><td>Cat (3, 7)</td><td>P<sub>b-2</sub></td></tr><tr><td>17, 18, 19<br>b ≡ 2, 4 (mod 6), 20 ≤ b ≤ 46</td><td>11</td><td>{x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>9</sub>}</td><td>Cat (5, 6)</td><td>P<sub>b-3</sub></td></tr><tr><td>12</td><td></td><td>{x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>10</sub>}</td><td>Cat (5, 7)</td><td>P<sub>b-4</sub></td></tr><tr><td>18, 19<br>b ≡ 2, 4 (mod 6), 20 ≤ b ≤ 46</td><td>13</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>9</sub>}</td><td>Cat (6, 7)</td><td>P<sub>b-5</sub></td></tr><tr><td>b ≡ 2, 4 (mod 6), 20 ≤ b ≤ 46</td><td>14</td><td>{x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>12</sub>}</td><td>Cat (5, 9)</td><td>P<sub>b-6</sub></td></tr><tr><td>b ≡ 2, 4 (mod 6), 22 ≤ b ≤ 46</td><td>15</td><td>{x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>16</sub>}</td><td>Cat (2, 13)</td><td>Cat (4, b − 11)</td></tr><tr><td>16</td><td></td><td>{x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>14</sub>}</td><td>Cat (5, 11)</td><td>P<sub>b-8</sub></td></tr><tr><td>17</td><td></td><td>{x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>18</sub>}</td><td>Cat (2, 15)</td><td>Cat (4, b − 13)</td></tr><tr><td>28, 32, 34, 38, 40, 44, 46</td><td>18</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>14</sub>}</td><td>Cat (7, 11)</td><td>P<sub>b-10</sub></td></tr><tr><td>32, 34, 38, 40, 44, 46</td><td>19</td><td>{x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>20</sub>}</td><td>Cat (2, 17)</td><td>Cat (4, b − 15)</td></tr><tr><td>34, 38, 40, 44, 46</td><td>20</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>16</sub>}</td><td>Cat (7, 13)</td><td>P<sub>b-12</sub></td></tr><tr><td>38, 40, 44, 46</td><td>21</td><td>{x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>22</sub>}</td><td>Cat (2, 19)</td><td>Cat (4, b − 17)</td></tr><tr><td>40, 44, 46</td><td>22</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>18</sub>}</td><td>Cat (7, 15)</td><td>P<sub>b-14</sub></td></tr><tr><td>44, 46</td><td>23</td><td>{x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>24</sub>}</td><td>Cat (2, 21)</td><td>Cat (4, b − 19)</td></tr><tr><td>46</td><td>24</td><td>{x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>22</sub>}</td><td>Cat (5, 19)</td><td>P<sub>b-16</sub></td></tr><tr><td>25</td><td></td><td>{x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>26</sub>}</td><td>Cat (2, 23)</td><td>Cat (4, b − 21)</td></tr><tr><td>26</td><td></td><td>{x<sub>3</sub>, x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>26</sub>}</td><td>Cat (3, 23)</td><td>Cat (3, b − 21)</td></tr><tr><td>27</td><td></td><td>{x<sub>4</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>5</sub>, ..., x<sub>28</sub>}</td><td>Cat (2, 25)</td><td>Cat (4, 23)</td></tr></tbody></table>
<table><caption>**Table 6.** Values of $G[V_λ]$ and $G[V \setminus V_λ]$ for Sun (5, b)</caption><thead><tr><th>b</th><th>λ</th><th>V<sub>λ</sub></th><th>G[V<sub>λ</sub>]</th><th>G[V \ V<sub>λ</sub>]</th></tr></thead><tbody><tr><td rowspan="2">6, 8, 10, 14,<br>16, 18, 20, 22</td><td>1</td><td>{u<sub>1</sub>}</td><td>P<sub>1</sub></td><td rowspan="2">sun with one ray</td></tr><tr><td>2</td><td>{x<sub>1</sub>, x<sub>2</sub>}</td><td>P<sub>2</sub></td></tr><tr><td>6, 18</td><td rowspan="3">3</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>}</td><td>P<sub>3</sub></td><td>Cat (4, b + 7)</td></tr><tr><td rowspan="2">8, 10, 14, 16, 20, 22</td><td>{x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>}</td><td>P<sub>3</sub></td><td>Cat (5, b + 1)</td></tr><tr><td></td><td>P<sub>4</sub></td><td>Cat (3, b + 3)</td></tr><tr><td rowspan="4">6, 8, 10, 14,<br>16, 18, 20, 22</td><td>4</td><td>{x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>, x<sub>4</sub>}</td><td>P<sub>4</sub></td><td>Cat (2, b + 5)</td></tr><tr><td>5</td><td>{x<sub>1</sub>..., x<sub>5</sub>}</td><td>P<sub>5</sub></td><td>P<sub>b+4</sub></td></tr><tr><td>6</td><td>{x<sub>2</sub>..., x<sub>5</sub>, v<sub>2</sub>, u<sub>2</sub>}</td><td>P<sub>6</sub></td><td>Cat (2, b + 1)</td></tr><tr><td>7</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>..., x<sub>5</sub>}</td><td>P<sub>7</sub></td><td>P<sub>b+2</sub></td></tr><tr><td>8, 10, 14, 16, 18, 20, 22</td><td>8</td><td>{x<sub>2</sub>..., x<sub>5</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>6</sub>, x<sub>7</sub>}</td><td>Cat (3, 5)</td><td>Cat (2, b - 1)</td></tr><tr><td rowspan="2">10, 14, 16, 18, 20, 22</td><td>9</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>..., x<sub>5</sub>, v<sub>2</sub>, u<sub>2</sub>}</td><td>P<sub>9</sub></td><td>P<sub>b</sub></td></tr><tr><td>10</td><td>{x<sub>4</sub>, x<sub>5</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>6</sub>, ..., x<sub>11</sub>}</td><td>Cat (3, 7)</td><td>Cat (4, b - 5)</td></tr><tr><td>14, 16, 18, 20, 22</td><td>11</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>..., x<sub>5</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>6</sub>, x<sub>7</sub>}</td><td>Cat (3, 8)</td><td>P<sub>b-2</sub></td></tr><tr><td>16, 18, 20, 22</td><td>12</td><td>{x<sub>2</sub>..., x<sub>5</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>6</sub>, ..., x<sub>11</sub>}</td><td>Cat (5, 7)</td><td>Cat (2, b - 5)</td></tr><tr><td>18, 20, 22</td><td>13</td><td>{x<sub>1</sub>, ..., x<sub>5</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>6</sub>, ..., x<sub>11</sub>}</td><td>Cat (6, 7)</td><td>P<sub>b-4</sub></td></tr><tr><td>20, 22</td><td>14</td><td>{x<sub>2</sub>, ..., x<sub>5</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>6</sub>, ..., x<sub>13</sub>}</td><td>Cat (5, 9)</td><td>Cat (2, b - 7)</td></tr><tr><td>22</td><td>15</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>..., x<sub>5</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>6</sub>, ..., x<sub>11</sub>}</td><td>Cat (7, 8)</td><td>P<sub>16</sub></td></tr></tbody></table>

<table><caption>**Table 7.** Values of $G[V_λ]$ and $G[V \setminus V_λ]$ for some Sun (6, b)</caption><thead><tr><th>b</th><th>λ</th><th>V<sub>λ</sub></th><th>G[V<sub>λ</sub>]</th><th>G[V \ V<sub>λ</sub>]</th></tr></thead><tbody><tr><td>7, 11, 14, 16</td><td>1</td><td>{u<sub>1</sub>}</td><td>P<sub>1</sub></td><td rowspan="3">sun with one ray</td></tr><tr><td>7, 14</td><td rowspan="2">2</td><td>{u<sub>1</sub>, v<sub>1</sub>}</td><td>P<sub>2</sub></td></tr><tr><td>11, 16</td><td>{x<sub>1</sub>, x<sub>2</sub>}</td><td>P<sub>2</sub></td></tr><tr><td>7</td><td rowspan="3">3</td><td>{x<sub>7</sub>, x<sub>8</sub>, x<sub>9</sub>}</td><td>P<sub>3</sub></td><td>Cat (7, b + 1)</td></tr><tr><td>11</td><td>{v<sub>2</sub>, u<sub>2</sub>, x<sub>7</sub>}</td><td>P<sub>3</sub></td><td>Cat (5, b + 3)</td></tr><tr><td>14, 16</td><td>{x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>}</td><td>P<sub>3</sub></td><td>Cat (5, b + 3)</td></tr><tr><td>7, 11, 14, 16</td><td>4</td><td>{x<sub>1</sub>, ..., x<sub>4</sub>}</td><td>P<sub>4</sub></td><td>Cat (3, b+3)</td></tr><tr><td>7, 11</td><td rowspan="2">5</td><td>{x<sub>5</sub>, x<sub>6</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>7</sub>}</td><td>Cat (2, 3)</td><td>Cat (5, b)</td></tr><tr><td>14, 16</td><td>{x<sub>1</sub>, ..., x<sub>5</sub>}</td><td>P<sub>5</sub></td><td>Cat (2, b + 3)</td></tr><tr><td>7, 11, 14, 16</td><td>6</td><td>{x<sub>1</sub>, ..., x<sub>6</sub>}</td><td>P<sub>6</sub></td><td>P<sub>b+4</sub></td></tr><tr><td>7, 11</td><td rowspan="2">7</td><td>{x<sub>3</sub>, ..., x<sub>6</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>7</sub>}</td><td>Cat (2, 5)</td><td>Cat (3, b)</td></tr><tr><td>14, 16</td><td>{x<sub>2</sub>, ..., x<sub>6</sub>, v<sub>2</sub>, u<sub>2</sub>}</td><td>P<sub>7</sub></td><td>Cat (2, b + 1)</td></tr><tr><td>7, 11, 14, 16</td><td>8</td><td>{x<sub>1</sub>, ..., x<sub>6</sub>, v<sub>2</sub>, u<sub>2</sub>}</td><td>P<sub>8</sub></td><td>P<sub>b+2</sub></td></tr><tr><td rowspan="2">11, 14, 16</td><td>9</td><td rowspan="2">{x<sub>1</sub>, ..., x<sub>6</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>7</sub>, ..., x<sub>λ-2</sub>}</td><td rowspan="2">Cat (λ - 7, 7)</td><td rowspan="2">P<sub>b+10-λ</sub></td></tr><tr><td>10</td></tr><tr><td rowspan="2">14, 16</td><td>11</td><td rowspan="2"></td><td rowspan="2"></td><td rowspan="2"></td></tr><tr><td>12</td></tr><tr><td>16</td><td>13</td><td></td><td></td><td></td></tr></tbody></table>
* Sun (0,2,c) contains Cat (5, c + 3) as a spanning tree, thus it is R-AVD for c ∈ {3, 6, 11}.

* For $c \in \{7, 18, 19\}$, Sun (0, 2, c) is R-AVD and the values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ are given in Table 8.

* For $c \equiv 2, 4 \pmod 6$, we first eliminate values of $c$ such that Sun (0,2,c) is not R-AVD.

* $c \equiv 2 \pmod 6$, $c \neq 2, 8, 14, 26$

Consider $\lambda = 10$. The two possibilities for $G[V_{10}]$ to be R-AVD are

- Cat (3, 7) with $V_{10} = \{u_2, v_2, v_1, u_1, x_{c+2}, \dots, x_{c-3}\}$, and thus $G[V\setminus V_{10}] = \text{Cat}(3, c-5)$. Cat (3, $c-5$) is not R-AVD for $c \equiv 2 \pmod 6$.

- $P_{10}$ with $V_{10} = \{u_1, v_1, x_{c+2}, \dots, x_{c-5}\}$. Then $G[V\setminus V_{10}] = \text{Cat}(5, c-7)$. If we consider only the cases where $c \ge 20$ and $c \equiv 2 \pmod 6$, $G[V\setminus V_{10}]$ is R-AVD only if $c = 26$.

* $c = 26$

Consider $\lambda = 13$. The possibilities for $G[V_{13}]$ to be R-AVD are

- Cat (3, 10) with $V_{13} = \{u_2, v_2, v_1, u_1, x_{c+2}, \dots, x_{c-6}\}$. If $c = 26$, then $G[V\setminus V_{13}] = \text{Cat}(3, 18)$ which is not R-AVD.

- $P_{13}$ with $V_{13} = \{u_1, v_1, x_{c+2}, \dots, x_{c-8}\}$. If $c = 26$, $G[V\setminus V_{13}] = \text{Cat}(5, 16)$ which is not R-AVD.

* $c \equiv 4 \pmod 6$, $c \ge 22$

First, observe that because $n = c + 8$ and $c \equiv 4 \pmod 6$, we have $n \equiv 0 \pmod 6$ and then $n \equiv 0 \pmod 3$.

We consider $\lambda = 15$. Both 15 and $n - 15 \equiv 0 \pmod 3$. Therefore, both $G_{15}$ and $G[V\setminus V_{15}]$ cannot be realized as a R-AVD caterpillar of the form Cat (3, b). Because Cat (5, 10) is not R-AVD the only remaining possibility is that $G_{15}$ is a path $P_{15}$ and $G[V\setminus V_{15}]$ is a caterpillar Cat (5, $c-12$). But Cat (5, $c-12$) is not R-AVD for $c = 22, 28$ or $c \ge 34$.

In conclusion, for $c \equiv 2, 4 \pmod 6$, the only remaining values are 2, 4, 8, 10, 14 and 16. For all of these values, Sun (0,2,c) is R-AVD and the values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ are given in Table 8.

* Sun (0,3,c) is OL-AVD only for $c \equiv 2, 4 \pmod 6$.

Consider first $\lambda = 6$. Because there is no R-AVD caterpillar of order 6, $G[V_6]$ must be a path of length 6. The two possibilities are that $V_6 = \{u_1, v_1, x_{c+3}, \dots, x_c\}$ or $\{u_3, v_3, x_4, \dots, x_7\}$.

If $V_6 = \{u_3, v_3, x_4, \dots, x_7\}$, $G[V\setminus V_6]$ is R-AVD if and only if $G[V\setminus V_6]$ is a caterpillar Cat (3, 4) and $c = 4$.

If $V_6 = \{u_1, v_1, x_{c+3}, \dots, x_c\}$, $G[V\setminus V_6]$ is R-AVD if and only if $G[V\setminus V_6]$ is a caterpillar Cat (5, 6) or Cat (6, 7) and then $c = 8$ or $c = 10$.

For $c \in \{4, 8, 10\}$, Sun (0, 3, c) is R-AVD and the values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ are given in Table 9.

* Sun (0,4,c) is OL-AVD only for $c \in \{4, 5, 6, 8, 10, 11, 12, 14, 16\}$.

For all of these values of $c$, Sun (0,4,c) is also R-AVD and values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ are given in Table 10.

* Sun (0,5,c) is OL-AVD only for $c \in \{6, 8, 16\}$.
<table><caption>**Table 8.** Values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ for some Sun $(0, 2, c)$</caption><thead><tr><th>c</th><th>λ</th><th>V<sub>λ</sub></th><th>G[V<sub>λ</sub>]</th><th>G[V\V<sub>λ</sub>]</th></tr></thead><tbody><tr><td>2, 4, 7, 8, 10, 14, 16, 18, 19</td><td>1</td><td>{u<sub>3</sub>}</td><td>P<sub>1</sub></td><td>P<sub>c+7</sub></td></tr><tr><td>2, 4, 7, 8, 10, 14, 16, 19</td><td></td><td>{u<sub>1</sub>, v<sub>1</sub>}</td><td>P<sub>2</sub></td><td>Cat (3, c + 3)</td></tr><tr><td>18</td><td>2</td><td>{x<sub>1</sub>, x<sub>2</sub>}</td><td>P<sub>2</sub></td><td>Cat (5, 19)</td></tr><tr><td>2, 4, 8, 10, 14, 16, 18</td><td></td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>}</td><td>P<sub>3</sub></td><td>Cat (2, c + 3)</td></tr><tr><td>7, 19</td><td>3</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>c+2</sub>}</td><td>P<sub>3</sub></td><td>Cat (5, c)</td></tr><tr><td>2, 4, 7, 8, 10, 14, 16, 18, 19</td><td>4</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, x<sub>2</sub>}</td><td>P<sub>4</sub></td><td>P<sub>c+4</sub></td></tr><tr><td>2, 4, 8, 10, 14, 16, 18</td><td></td><td>{u<sub>1</sub>, v<sub>1</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>1</sub>}</td><td>Cat (2, 3)</td><td>Cat (2, c + 1)</td></tr><tr><td>7, 19</td><td>5</td><td>{x<sub>c+2</sub>, v<sub>1</sub>, u<sub>1</sub>, v<sub>2</sub>, u<sub>2</sub>}</td><td>Cat (2, 3)</td><td>Cat (3, c)</td></tr><tr><td>4, 7, 8, 10, 14, 16, 18, 19</td><td>6</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, x<sub>2</sub>, v<sub>3</sub>, u<sub>3</sub>}</td><td>P<sub>6</sub></td><td>P<sub>c+2</sub></td></tr><tr><td>7, 8, 10, 14, 16, 18, 19</td><td>7</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, x<sub>2</sub>, v<sub>3</sub>, u<sub>3</sub>, x<sub>3</sub>}</td><td>Cat (2, 5)</td><td>P<sub>c+1</sub></td></tr><tr><td>8, 10, 14, 16, 18, 19</td><td>8</td><td>{u<sub>1</sub>, v<sub>1</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>1</sub>, x<sub>2</sub>, v<sub>3</sub>, u<sub>3</sub>}</td><td>Cat (3, 5)</td><td>P<sub>c</sub></td></tr><tr><td>10, 14, 16, 18, 19</td><td>9</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, x<sub>2</sub>, v<sub>3</sub>, u<sub>3</sub>, x<sub>3</sub>, x<sub>4</sub>, x<sub>5</sub>}</td><td>Cat (4, 5)</td><td>P<sub>c-1</sub></td></tr><tr><td>14</td><td></td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>16</sub>, ..., x<sub>9</sub>}</td><td>P<sub>10</sub></td><td>Cat (5, 7)</td></tr><tr><td>16, 18, 19</td><td>10</td><td>{u<sub>2</sub>, v<sub>2</sub>, v<sub>1</sub>, u<sub>1</sub>, x<sub>c+2</sub>, ..., x<sub>c-3</sub>}</td><td>Cat (3, 7)</td><td>Cat (3, c - 5)</td></tr><tr><td>14, 16, 18, 19</td><td>11</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, x<sub>2</sub>, v<sub>3</sub>, u<sub>3</sub>, x<sub>3</sub>, ..., x<sub>7</sub>}</td><td>Cat (5, 6)</td><td>P<sub>c-3</sub></td></tr><tr><td>16, 18, 19</td><td>12</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, x<sub>2</sub>, v<sub>3</sub>, u<sub>3</sub>, x<sub>3</sub>, ..., x<sub>8</sub>}</td><td>Cat (5, 7)</td><td>P<sub>c-4</sub></td></tr><tr><td>18, 19</td><td>13</td><td>{u<sub>2</sub>, v<sub>2</sub>, v<sub>1</sub>, u<sub>1</sub>, x<sub>c+2</sub>, ..., x<sub>c-6</sub>}</td><td>Cat (3, 10)</td><td>Cat (3, c - 8)</td></tr></tbody></table>

<table><caption>**Table 9.** Values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ for Sun $(0, 3, c)$</caption><thead><tr><th>c</th><th>λ</th><th>V<sub>λ</sub></th><th>G[V<sub>λ</sub>]</th><th>G[V\V<sub>λ</sub>]</th></tr></thead><tbody><tr><td rowspan="5">4, 8, 10</td><td>1</td><td>{u<sub>3</sub>}</td><td>P<sub>1</sub></td><td>P<sub>c+8</sub></td></tr><tr><td>2</td><td>{u<sub>2</sub>, v<sub>2</sub>}</td><td>P<sub>2</sub></td><td>Cat (4, c + 3)</td></tr><tr><td>3</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>}</td><td>P<sub>3</sub></td><td>Cat (3, c + 3)</td></tr><tr><td>4</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, x<sub>2</sub>}</td><td>P<sub>4</sub></td><td>Cat (2, c + 3)</td></tr><tr><td>5</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>}</td><td>P<sub>5</sub></td><td>P<sub>c+4</sub></td></tr><tr><td>4</td><td></td><td>{u<sub>3</sub>, v<sub>3</sub>, x<sub>4</sub>, ..., x<sub>7</sub>}</td><td>P<sub>6</sub></td><td>Cat (3, 4)</td></tr><tr><td>8, 10</td><td>6</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>c+3</sub>, ..., x<sub>c</sub>}</td><td>P<sub>6</sub></td><td>Cat (6, c - 3)</td></tr><tr><td>8, 10</td><td>7</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, x<sub>2</sub>, v<sub>3</sub>, u<sub>3</sub>}</td><td>P<sub>7</sub></td><td>P<sub>c+2</sub></td></tr><tr><td>8, 10</td><td>8</td><td>{u<sub>2</sub>, v<sub>2</sub>, v<sub>1</sub>, u<sub>1</sub>, x<sub>c+3</sub>, ..., x<sub>c</sub>}</td><td>Cat (3, 5)</td><td>Cat (4, c - 3)</td></tr><tr><td>10</td><td>9</td><td>{x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>, v<sub>3</sub>, u<sub>3</sub>, x<sub>4</sub>, ..., x<sub>7</sub>}</td><td>Cat (4, 5)</td><td>Cat (3, 7)</td></tr></tbody></table>

Consider $\lambda = 2$. There is only two possibilities for $V_2$, either $V_2 = \{u_2, v_2\}$, or $V_2 = \{u_1, v_1\}$.

If $V_2 = \{u_2, v_2\}$, then $G[V\setminus V_2] = \text{Cat}(6, c + 3)$ which is not R-AVD for any $c \in \{6, 8, 16\}$.

If $V_2 = \{u_1, v_1\}$, then $G[V\setminus V_2] = \text{Cat}(8, c + 1)$ which is R-AVD for $c = 6$ but not for $c = 8$ or $c = 16$.

In fact, Sun (0, 5, 6) is R-AVD and values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ are given in Table 11.

* Sun (0,6,c) is OL-AVD only for $c \in \{8, 10\}$.

Consider $\lambda = 3$. The two possibilities for $V_3$ are $\{u_2, v_2, x_1\}$ and $\{u_1, v_1, x_{c+6}\}$.
<table><caption>**Table 10.** Values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ for Sun (0, 4, c)</caption><thead><tr><th>c</th><th>λ</th><th>V<sub>λ</sub></th><th>G[V<sub>λ</sub>]</th><th>G[V\V<sub>λ</sub>]</th></tr></thead><tbody><tr><td>4, 5, 6, 8, 10, 11, 12, 14, 16</td><td>1</td><td>{u<sub>3</sub>}</td><td>P<sub>1</sub></td><td>P<sub>c+9</sub></td></tr><tr><td>4, 6, 11, 16</td><td></td><td>{u<sub>2</sub>, v<sub>2</sub>}</td><td>P<sub>2</sub></td><td>Cat (5, c + 3)</td></tr><tr><td>5, 8, 10, 12, 14</td><td>2</td><td>{u<sub>1</sub>, v<sub>1</sub>}</td><td>P<sub>2</sub></td><td>Cat (7, c + 1)</td></tr><tr><td>4, 6, 8, 10, 12, 14, 16</td><td></td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>}</td><td>P<sub>3</sub></td><td>Cat (4, c + 3)</td></tr><tr><td>5, 11</td><td>3</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>c+4</sub>}</td><td>P<sub>3</sub></td><td>Cat (7, c)</td></tr><tr><td>4, 5, 8, 10, 11, 14, 16</td><td></td><td>{x<sub>1</sub>, ..., x<sub>4</sub>}</td><td>P<sub>4</sub></td><td>Cat (3, c + 3)</td></tr><tr><td>6, 12</td><td>4</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>c+4</sub>, x<sub>c+3</sub>}</td><td>P<sub>4</sub></td><td>Cat (7, c - 1)</td></tr><tr><td>4, 6, 8, 10, 12, 14, 16</td><td></td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>}</td><td>P<sub>5</sub></td><td>Cat (2, c + 3)</td></tr><tr><td>5</td><td>5</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>9</sub>, x<sub>8</sub>, x<sub>7</sub>}</td><td>P<sub>5</sub></td><td>Cat (3, 7)</td></tr><tr><td>11</td><td></td><td>{u<sub>2</sub>, v<sub>2</sub>, v<sub>1</sub>, u<sub>1</sub>, x<sub>15</sub>}</td><td>Cat (2, 3)</td><td>Cat (5, 11)</td></tr><tr><td>4, 5, 6, 8, 10, 11, 12, 14, 16</td><td>6</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, ..., x<sub>4</sub>}</td><td>P<sub>6</sub></td><td>P<sub>c+4</sub></td></tr><tr><td>4, 6, 8, 10, 12, 14, 16</td><td></td><td>{u<sub>1</sub>, v<sub>1</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>}</td><td>Cat (3, 4)</td><td>Cat (2, c + 1)</td></tr><tr><td>5, 11</td><td>7</td><td>{u<sub>2</sub>, v<sub>2</sub>, v<sub>1</sub>, u<sub>1</sub>, x<sub>c+4</sub>, x<sub>c+3</sub>, x<sub>c+2</sub>}</td><td>Cat (3, 4)</td><td>Cat (5, c - 2)</td></tr><tr><td>6, 8, 10, 11, 12, 14, 16</td><td>8</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>3</sub>, u<sub>3</sub>}</td><td>P<sub>8</sub></td><td>P<sub>c+2</sub></td></tr><tr><td>8, 10, 11, 12, 14, 16</td><td>9</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>3</sub>, u<sub>3</sub>, x<sub>5</sub>}</td><td>Cat (2, 7)</td><td>P<sub>c+1</sub></td></tr><tr><td>10, 11, 12, 14, 16</td><td>10</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>3</sub>, u<sub>3</sub>, x<sub>5</sub>, x<sub>6</sub>}</td><td>Cat (3, 7)</td><td>P<sub>c</sub></td></tr><tr><td>12, 14, 16</td><td>11</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>3</sub>, u<sub>3</sub>, x<sub>5</sub>, x<sub>6</sub>, x<sub>7</sub>}</td><td>Cat (4, 7)</td><td>P<sub>c-1</sub></td></tr><tr><td>14, 16</td><td>12</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>3</sub>, u<sub>3</sub>, x<sub>5</sub>, ..., x<sub>8</sub>}</td><td>Cat (5, 7)</td><td>P<sub>c-2</sub></td></tr><tr><td>16</td><td>13</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, ..., x<sub>4</sub>, v<sub>3</sub>, u<sub>3</sub>, x<sub>5</sub>, ..., x<sub>9</sub>}</td><td>Cat (6, 7)</td><td>P<sub>c-3</sub></td></tr></tbody></table>

<table><caption>**Table 11.** Values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ for Sun (0, 5, 6)</caption><thead><tr><th>λ</th><th>V<sub>λ</sub></th><th>G[V<sub>λ</sub>]</th><th>G[V\V<sub>λ</sub>]</th></tr></thead><tbody><tr><td>1</td><td>{u<sub>3</sub>}</td><td>P<sub>1</sub></td><td>P<sub>16</sub></td></tr><tr><td>2</td><td>{u<sub>1</sub>, v<sub>1</sub>}</td><td>P<sub>2</sub></td><td>Cat (7, 8)</td></tr><tr><td>3</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>}</td><td>P<sub>3</sub></td><td>Cat (5, 9)</td></tr><tr><td>4</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, x<sub>2</sub>}</td><td>P<sub>4</sub></td><td>Cat (4, 9)</td></tr><tr><td>5</td><td>{u<sub>1</sub>, v<sub>1</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>1</sub>}</td><td>Cat (2, 3)</td><td>Cat (5, 7)</td></tr><tr><td>6</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, ..., x<sub>4</sub>}</td><td>P<sub>6</sub></td><td>Cat (2, 9)</td></tr><tr><td>7</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, ..., x<sub>5</sub>}</td><td>P<sub>7</sub></td><td>P<sub>10</sub></td></tr><tr><td>8</td><td>{u<sub>1</sub>, v<sub>1</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>1</sub>, ..., x<sub>4</sub>}</td><td>Cat (3, 5)</td><td>Cat (2, 7)</td></tr></tbody></table>

In the first case, $G[V\setminus V_3] = \text{Cat}(6, c+3)$, in the second case $G[V\setminus V_3] = \text{Cat}(9, c)$. In both cases, $G[V\setminus V_3]$ is not R-AVD for $c = 8$ or $c = 10$.

* Sun (0,7,c) is OL-AVD only for $c \in \{8, 10\}$.

Consider $\lambda = 2$. There is only two possibilities for $V_2$, either $V_2 = \{u_2, v_2\}$, or $V_2 = \{u_1, v_1\}$.

If $V_2 = \{u_2, v_2\}$, then $G[V\setminus V_2] = \text{Cat}(8, c + 3)$. If $V_2 = \{u_1, v_1\}$, then $G[V\setminus V_2] = \text{Cat}(10, c + 1)$. Both $\text{Cat}(8, c + 3)$ and $\text{Cat}(10, c + 1)$ are not R-AVD for $c = 8$ and $c = 10$.

* Sun (0,8,c) is OL-AVD only for $c \in \{8, 9\}$.
Consider again $\lambda = 2$ and the two possibilities for $V_2$: $V_2 = \{u_2, v_2\}$, or $V_2 = \{u_1, v_1\}$.

If $V_2 = \{u_2, v_2\}$, then $G[V\setminus V_2] = \text{Cat}(9, c+3)$. If $V_2 = \{u_1, v_1\}$, then $G[V\setminus V_2] = \text{Cat}(11, c+1)$. Both $\text{Cat}(9, c+3)$ and $\text{Cat}(11, c+1)$ are not R-AVD for $c=8$ and $c=9$.

• $\text{Sun}(1,2,c)$ is OL-AVD only for $c \equiv 2, 4 \pmod 6$ or $c \in \{6, 18\}$.

Consider first $\lambda = 11$. That means that $n \ge 22$ and thus $c \ge 13$. We consider four possibilities to obtain a R-AVD graph with order 11:

- $V_{11} = \{u_2, v_2, x_1, v_1, u_1, x_{c+3}, \dots, x_{c-2}\}$. In that case, $G[V\setminus V_{11}] = \text{Cat}(3, c-5)$.

- $V_{11} = \{u_2, v_2, x_2, x_3, v_3, u_3, x_4, \dots, x_8\}$. Thus, $G[V\setminus V_{11}] = \text{Cat}(2, c-4)$.

- $V_{11} = \{x_2, x_3, v_3, u_3, x_4, \dots, x_{10}\}$. Thus, $G[V\setminus V_{11}] = \text{Cat}(4, c-6)$.

- $V_{11} = \{x_1, v_1, u_1, x_{c+3}, \dots, x_{c-4}\}$. Thus, $G[V\setminus V_{11}] = \text{Cat}(5, c-7)$.

For all these cases, $G[V\setminus V_{11}]$ is not R-AVD for $c \ge 13$, $c \equiv 2 \pmod 6$, except for $G[V\setminus V_{11}] = \text{Cat}(5, 7)$ or $\text{Cat}(5, 19)$ and $c = 14$ or $26$.

Consider now $\lambda = 13$. That means that $n \ge 26$ and thus $c \ge 17$. We consider three possibilities to obtain a R-AVD graph with order 13:

- $V_{13} = \{x_2, x_3, v_3, u_3, x_4, \dots, x_{13}\}$. Thus, $G[V\setminus V_{13}] = \text{Cat}(4, c-8)$.

- $V_{13} = \{u_2, v_2, x_1, v_1, u_1, x_{c+3}, \dots, x_{c-4}\}$. In that case, $G[V\setminus V_{13}] = \text{Cat}(3, c-7)$.

- $V_{13} = \{x_1, v_1, u_1, x_{c+3}, \dots, x_{c-6}\}$. Thus, $G[V\setminus V_{13}] = \text{Cat}(5, c-9)$.

For all these cases, $G[V\setminus V_{13}]$ is not R-AVD for $c \ge 17$, $c \equiv 4 \pmod 6$, except when $G[V\setminus V_{13}] = \text{Cat}(5, 19)$ and $c = 28$.

At last, consider an induced subgraph with order 18. Because the only caterpillar with this order is $\text{Cat}(7, 11)$, the only way to have a R-AVD subgraph of $\text{Sun}(1, 2, c)$ with order 18 is a path $P_{18}$. In the cases of $c = 26$ or $c = 28$, the remaining subgraph contains four leaves and then, cannot be R-AVD.

Thus, the only remaining values for $c$ are 2, 4, 6, 8, 10, 14, 16 and 18. For all these values of $c$, $\text{Sun}(1, 2, c)$ is R-AVD and values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ are given in Table 12.

• $\text{Sun}(2,3,c)$ is OL-AVD only for $c \in \{4, 8, 16\}$.

Let us consider $\lambda = 2$. If $V_2 = \{u_1, v_1\}$, $V_2 = \{u_2, v_2\}$ or $V_2 = \{u_3, v_3\}$, then $G[V\setminus V_2]$ has four leaves and then is not R-AVD. The only remaining possibility is $V_2 = \{x_1, x_2\}$, and thus $G[V\setminus V_2] = \text{Cat}(6, c+3)$. Then, $\text{Sun}(2, 3, c)$ cannot be R-AVD with $c=8$ or $c=16$.

$\text{Sun}(2, 3, 4)$ is R-AVD and values of $G[V_\lambda]$ and $G[V\setminus V_\lambda]$ are given in Table 13.

**Sun with four rays.** A sun with four rays is OL-AVD if and only if it is isomorphic to $\text{Sun}(0, 0, 1, d)$ with $d \equiv 2, 4 \pmod 6$.

Consider $\lambda = 6$. Since an R-AVD graph with order 6 must be a path, the only possibility is to have:

• $d = 2, V_6 = \{u_1, v_1, x_3, x_2, v_4, u_4\}$ and $G[V\setminus V_6] = \text{Cat}(2, 3)$ or

• $d = 4, V_6 = \{u_1, v_1, x_5, x_4, x_3, x_2\}$ and $G[V\setminus V_6] = \text{Cat}(4, 3)$.
<table><caption>**Table 12.** Values of $G[V_λ]$ and $G[V \setminus V_λ]$ for Sun (1, 2, c)</caption><thead><tr><th>c</th><th>λ</th><th>V<sub>λ</sub></th><th>G[V<sub>λ</sub>]</th><th>G[V \ V<sub>λ</sub>]</th></tr></thead><tbody><tr><td>2, 4, 6, 8, 10, 14, 16, 18</td><td>1</td><td>{u<sub>1</sub>}</td><td>P<sub>1</sub></td><td>Sun (2, c + 2)</td></tr><tr><td>2, 4, 6, 8, 10, 14, 16, 18</td><td>2</td><td>{x<sub>2</sub>, x<sub>3</sub>}</td><td>P<sub>2</sub></td><td>Cat (4, c + 3)</td></tr><tr><td>2, 4, 8, 10, 14, 16</td><td></td><td>{x<sub>1</sub>, v<sub>2</sub>, u<sub>2</sub>}</td><td>P<sub>3</sub></td><td>Cat (3, c + 3)</td></tr><tr><td>6, 18</td><td>3</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>}</td><td>P<sub>3</sub></td><td>Cat (5, c + 1)</td></tr><tr><td>2, 4, 6, 8, 10, 14, 16, 18</td><td>4</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>2</sub>, x<sub>3</sub>}</td><td>P<sub>4</sub></td><td>Cat (2, c + 3)</td></tr><tr><td>2, 4, 6, 8, 10, 14, 16, 18</td><td>5</td><td>{x<sub>1</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>2</sub>, x<sub>3</sub>}</td><td>Cat (2, 3)</td><td>P<sub>c+4</sub></td></tr><tr><td>4, 6, 8, 10, 14, 16, 18</td><td>6</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>2</sub>, x<sub>3</sub>, v<sub>3</sub>, u<sub>3</sub>}</td><td>P<sub>6</sub></td><td>Cat (2, c + 1)</td></tr><tr><td>6, 8, 10, 14, 16, 18</td><td>7</td><td>{x<sub>1</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>2</sub>, x<sub>3</sub>, v<sub>3</sub>, u<sub>3</sub>}</td><td>Cat (2, 5)</td><td>P<sub>c+2</sub></td></tr><tr><td>8, 10, 14, 16, 18</td><td>8</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>2</sub>, x<sub>3</sub>, v<sub>3</sub>, u<sub>3</sub>, x<sub>4</sub>, x<sub>5</sub>}</td><td>Cat (3, 5)</td><td>Cat (2, c - 1)</td></tr><tr><td>10, 14, 16, 18</td><td>9</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>2</sub>, x<sub>3</sub>, v<sub>3</sub>, u<sub>3</sub>}</td><td>Cat (4, 5)</td><td>P<sub>c</sub></td></tr><tr><td>14, 16, 18</td><td>10</td><td>{x<sub>2</sub>, x<sub>3</sub>, v<sub>3</sub>, u<sub>3</sub>, x<sub>4</sub>, ..., x<sub>9</sub>}</td><td>Cat (3, 7)</td><td>Cat (4, c - 5)</td></tr><tr><td>14</td><td></td><td>{x<sub>1</sub>, v<sub>1</sub>, u<sub>1</sub>, x<sub>c+3</sub>, ||dots, x<sub>c-4</sub>}</td><td>Cat (2, 9)</td><td>Cat (5, c - 7)</td></tr><tr><td>16, 18</td><td>11</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, v<sub>1</sub>, u<sub>1</sub>, x<sub>c+3</sub>, ||dots, x<sub>c-2</sub>}</td><td>Cat (4, 7)</td><td>Cat (3, c - 5)</td></tr><tr><td>16, 18</td><td>12</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>2</sub>, x<sub>3</sub>, v<sub>3</sub>, u<sub>3</sub>, x<sub>4</sub>, ..., x<sub>9</sub>}</td><td>Cat (5, 7)</td><td>Cat (2, c - 5)</td></tr><tr><td>18</td><td>13</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>1</sub>, v<sub>1</sub>, u<sub>1</sub>, x<sub>21</sub>, ..., x<sub>9</sub>}</td><td>Cat (4, 9)</td><td>Cat (3, 11)</td></tr></tbody></table>

<table><caption>**Table 13.** Values of $G[V_λ]$ and $G[V \setminus V_λ]$ for Sun (2, 3, 4)</caption><thead><tr><th>λ</th><th>V<sub>λ</sub></th><th>G[V<sub>λ</sub>]</th><th>G[V \ V<sub>λ</sub>]</th></tr></thead><tbody><tr><td>1</td><td>{u<sub>3</sub>}</td><td>P<sub>1</sub></td><td>Sun (2, 8)</td></tr><tr><td>2</td><td>{x<sub>1</sub>, x<sub>2</sub>}</td><td>P<sub>2</sub></td><td>Cat (6, 7)</td></tr><tr><td>3</td><td>{x<sub>3</sub>, x<sub>4</sub>, x<sub>5</sub>}</td><td>P<sub>3</sub></td><td>Cat (5, 7)</td></tr><tr><td>4</td><td>{x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>}</td><td>P<sub>4</sub></td><td>Cat (4, 7)</td></tr><tr><td>5</td><td>{x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>, x<sub>3</sub>}</td><td>Cat (2, 3)</td><td>Cat (3, 7)</td></tr><tr><td>6</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>1</sub>, x<sub>2</sub>, v<sub>2</sub>, u<sub>2</sub>}</td><td>P<sub>6</sub></td><td>Cat (4, 5)</td></tr><tr><td>7</td><td>{u<sub>2</sub>, v<sub>2</sub>, x<sub>3</sub>, x<sub>4</sub>, x<sub>5</sub>, v<sub>3</sub>, u<sub>3</sub>}</td><td>P<sub>7</sub></td><td>Cat (3, 5)</td></tr></tbody></table>

We prove that both Sun (0, 0, 1, 2) and Sun (0, 0, 1, 4) are R-AVD, by giving the values of $G[V_λ]$ and $G[V \setminus V_λ]$ in Table 14.

<table><caption>**Table 14.** Values of $G[V_λ]$ and $G[V \setminus V_λ]$ for Sun (0, 0, 1, d)</caption><thead><tr><th>d</th><th>λ</th><th>V<sub>λ</sub></th><th>G[V<sub>λ</sub>]</th><th>G[V \ V<sub>λ</sub>]</th></tr></thead><tbody><tr><td>2, 4</td><td>1</td><td>{u<sub>1</sub>}</td><td>P<sub>1</sub></td><td>Sun (0, 1, d + 1)</td></tr><tr><td>2, 4</td><td>2</td><td>{u<sub>2</sub>, v<sub>2</sub>}</td><td>P<sub>2</sub></td><td>Cat (4, d + 3)</td></tr><tr><td>2, 4</td><td>3</td><td>{u<sub>3</sub>, v<sub>3</sub>, x<sub>1</sub>}</td><td>P<sub>3</sub></td><td>Cat (3, d + 3)</td></tr><tr><td>2, 4</td><td>4</td><td>{u<sub>2</sub>, v<sub>2</sub>, v<sub>3</sub>, u<sub>3</sub>}</td><td>P<sub>4</sub></td><td>Cat (2, d + 3)</td></tr><tr><td>2, 4</td><td>5</td><td>{u<sub>2</sub>, v<sub>2</sub>, v<sub>3</sub>, u<sub>3</sub>, x<sub>1</sub>}</td><td>Cat (2, 3)</td><td>P<sub>d+4</sub></td></tr><tr><td>4</td><td>6</td><td>{u<sub>1</sub>, v<sub>1</sub>, x<sub>5</sub>, x<sub>4</sub>, x<sub>3</sub>, x<sub>2</sub>}</td><td>P<sub>6</sub></td><td>Cat (4, 3)</td></tr></tbody></table>

□
Acknowledgements

*This research was partially supported by the partnership Hubert Curien Polonium 22658VG.*

*The research of the third author was partially supported by the Polish Ministry of Science and Higher Education.*

REFERENCES

[1] O. Baudon, F. Gilbert, M. Woźniak, *Recursively arbitrarily vertex-decomposable graphs*, research report, 2010.

[2] R. Diestel, *Graph Theory*, Springer, 2005.

[3] M. Horňák, Z. Tuza, M. Woźniak, *On-line arbitrarily vertex decomposable trees*, Discrete Applied Mathematics **155** (2007), 1420–1429.

[4] R. Kalinowski, M. Pilśniak, M. Woźniak, I.A. Zioło. *On-line arbitrarily vertex decomposable suns*, Discrete Mathematics **309** (2009), 6328–6336.

Olivier Baudon
olivier.baudon@labri.fr

LaBRI, Université de Bordeaux
351, cours de la Libération, 33405 Talence Cedex, France

Frédéric Gilbert
frederic.gilbert@labri.fr

LaBRI, Université de Bordeaux
351, cours de la Libération, 33405 Talence Cedex, France

Mariusz Woźniak
mwozniak@agh.edu.pl

AGH University of Science and Technology
Faculty of Applied Mathematics
al. A. Mickiewicza 30, 30-059 Krakow, Poland

*Received: October 30, 2010.*

*Revised: March 26, 2010.*

*Accepted: March 28, 2010.*