## 3 Unions and Joins  
In this section we explore connectivity and Hamiltonian properties of graphs constructed by the operations of disjoint union and join. Our main focus is the situation where one of the graphs involved is complete, or has no edges. Figure 3: \(\mathcal{B}_{3}(P_{4})\), the \(3\)-Bell colouring graph of \(P_{4}\). The vertices are labeled by the partition of the path \(abcd\). Recall that the _disjoint union_ of disjoint graphs \(G_{1}\) and \(G_{2}\) is the graph \(G_{1}\cup G_{2}\) with vertex set \(V(G_{1})\cup V(G_{2})\) and edge set \(E(G_{1})\cup E(G_{2})\). The _join_ of disjoint graphs \(G_{1}\) and \(G_{2}\) is the graph \(G_{1}\lor G_{2}\) with vertex set \(V(G_{1})\cup V(G_{2})\) and edge set \(E(G_{1})\cup E(G_{2})\cup\{x_{1}x_{2}:x_{1}\in V(G_{1})\text{ and }x_{2}\in V(G_{2})\}\). We shall consider unions first, and joins second. Observe that the canonical \(k\)-colouring graph of \(\overline{K}_{n}=K_{1}\cup K_{1}\cup\dots\cup K_{1}\) is the graph of partitions of an \(n\)-set into at most \(k\) parts. Hence the number of vertices is the sum of Stirling numbers of the second kind, \(S(n,1)+S(n,2)+\dots+S(n,k)\). A Hamilton cycle in this graph corresponds to a cyclic Gray code for set partitions. Many different Gray codes, cyclic and otherwise, for set partitions are known to exist [19]; our method gives a different point of view and leads to a recursive algorithm similar to that of [PERSON] [2]. A related method that gives Hamilton paths rather than Hamilton cycles is given in Theorem 4. Theorem 4.1: _Let \(\pi\) be a vertex ordering such that \(\operatorname{Can}_{k}^{\pi}(G)\) is Hamiltonian. Then, for the vertex ordering \(\pi^{\prime}\) of \(G\cup K_{1}\) obtained by placing the vertex of \(K_{1}\) at the end of \(\pi\), the graph \(\operatorname{Can}_{k}^{\pi^{\prime}}(G\cup K_{1})\) is Hamiltonian._  
Proof: Since \(\operatorname{Can}_{k}^{\pi}(G)\) has at least three vertices, we have \(k\geq 2\). Suppose \(k=2\). Then, \(G\) is bipartite and has at least three components. Let \(X_{1}\) be the component of \(G\) containing the first vertex of \(\pi\). Then \(\operatorname{Can}_{k}^{\pi}(G)\) is isomorphic to the cube of dimension equal to the number of components of \(G-X_{1}\), and \(\operatorname{Can}_{k}^{\pi^{\prime}}(G\cup K_{1})\) is isomorphic to the cube of one higher dimension. Since the \(t\)-cube is Hamiltonian for all \(t\geq 2\), the statement follows. Now suppose \(k\geq 3\). If \(c\) is a canonical \(k\)-colouring of \(G\cup K_{1}\) with respect to \(\pi^{\prime}\), then the restriction of \(c\) to \(G\) is a canonical \(k\)-colouring of \(G\). We will say that the colouring \(c\) on \(G\cup K_{1}\) is an _extension_ of the colouring on \(G\). Furthermore, each canonical \(k\)-colouring of \(G\) has at least two extensions to a canonical \(k\)-colouring of \(G\cup K_{1}\), and there are exactly two extensions if and only if \(G\cong\overline{K}_{n}\) and only one colour is used on the vertices of \(G\). Notice that the set of canonical \(k\)-colourings of \(G\cup K_{1}\) which agree on their restriction to \(V(G)\) induces a complete subgraph of \(\operatorname{Can}_{k}^{\pi^{\prime}}(G\cup K_{1})\). By hypothesis, \(\operatorname{Can}_{k}^{\pi}(G)\) has a Hamilton cycle \(c_{1},c_{2},\dots,c_{t},c_{1}\). Thus \(t\geq 3\), and there exists \(i\) such that \(c_{i}\) and \(c_{i+1}\) both use at least two colours. Without loss of generality, \(i=t\). Thus, the canonical \(k\)-colourings \(c_{t}\) and \(c_{1}\) each have at least three extensions to canonical \(k\)-colouring of \(G\cup K_{1}\). For \(i=1,2,\dots,t\), let \(c_{i}\cdot\ell\) denote the extension of \(c_{i}\) to a canonical \(k\)-colouring of \(G\cup K_{1}\) in which the vertex of \(K_{1}\) is assigned colour \(\ell\). Observe that \(c_{i}\cdot 1\) and \(c_{i}\cdot 2\) are adjacent to \(c_{i+1}\cdot 1\) and \(c_{i+1}\cdot 2\), respectively, \(1\leq i\leq t-1\) and \(c_{t}\cdot 1,c_{t}\cdot 2\) and \(c_{t}\cdot 3\) are adjacent to \(c_{1}\cdot 1,c_{1}\cdot 2\) and \(c_{1}\cdot 3\), respectively.