# Measuring Colloidomer Hydrodynamics with Holographic Video Microscopy

Jatin Abacousnac  Jasna Brujic  David G. Grier  Department of Physics and
Center for Soft Matter Research, New York University, New York, NY 10003, USA

(June 2023)

###### Abstract

In-line holographic video microscopy records a wealth of information about the
microscopic structure and dynamics of colloidal materials. Powerful analytical
techniques are available to retrieve that information when the colloidal
particles are well-separated. Large assemblies of close-packed particles
create holograms that are substantially more challenging to interpret. We
demonstrate that Rayleigh-Sommerfeld back-propagation is useful for analyzing
holograms of colloidomer chains, close-packed linear assemblies of micrometer-
scale emulsion droplets. Colloidomers are fully flexible chains and undergo
three-dimensional configurational changes under the combined influence of
random thermal forces and hydrodynamic forces. We demonstrate the ability of
holographic reconstruction to track these changes as colloidomers sediment
through water in a horizontal slit pore. Comparing holographically measured
configurational trajectories with predictions of hydrodynamic models both
validates the analytical technique for this valuable class of self-organizing
materials and also provides insights into the influence of geometric
confinement on colloidomer hydrodynamics.

##  I Introduction

Figure 1: (a) Schematic view of a colloidomer’s confined sedimentation. A
chain of droplets is suspended in a layer of water between two horizontal
glass surfaces separated by height $H$. The colloidomer is lifted along the
vertical $\hat{z}$ axis and stretched to its full extent along $\hat{x}$ by a
pair of holographic optical tweezers. The traps then are extinguished,
allowing the colloidomer to sediment freely. The chain bends and coils as it
settles, and therefore is increasingly distorted relative to the ideal rod-
like structure, shown at height $h$. (b) Holographic image of a model
14-droplet chain at two different times during its descent. (c) Trajectory of
the chain from (b) obtained by analyzing holograms with Rayleigh-Sommerfeld
backpropagation. Each point represents the three-dimensional position of one
droplet, projected into the $x$-$z$ plane, and is colored by time.
Hydrodynamic coupling to the lower wall suppresses curvature at late times.

The conformational dynamics of a confined polymer is strongly influenced by
interactions with neighbors and hydrodynamic coupling to bounding surfaces.
Such systems typically are studied through numerical simulation because the
relevant length and time scales are not experimentally accessible. This
situation recently has changed with the introduction of micrometer-scale
colloidal analogs for molecular polymers. These include chains of colloidal
spheres [1, 2] and emulsion droplets [3, 4, 5], linked by complementary DNA or
nanoparticle bridges. These model soft-matter systems, known as colloidomers,
behave in much the same way as conventional polymers with the advantage that
they can be observed directly through optical microscopy. Experimental studies
of colloidomer dynamics not only offer insights into the microscopic
mechanisms of polymer physics, but also clarify how colloidomers can be
induced to self-organize into hierarchical structures with practical
applications [6].

The challenge in all such studies is to track the individual beads in a
colloidal chain as they move relative to each other in three dimensions.
Conventional microscopy cannot readily follow objects as they move out of the
focal plane. Confocal microscopy solves this problem, but is too slow to track
conformational changes. Lorenz-Mie analysis of holographic microscopy data
addresses both of these issues [7], but is impractical for complex assemblies
of particles [8], especially if their configuration changes over time. Here,
we introduce a general method based on holographic video microscopy to measure
the three-dimensional conformational trajectory of a colloidomer chain. We
demonstrate this technique with an experimental study of fully flexible
colloidomer chains sedimenting through a viscous fluid between two parallel
hard walls. In addition to validating the technique, these measurements reveal
the influence of hydrodynamic coupling on the dynamics of a flexible chain in
quantitative agreement with hydrodynamic models.

Our system is shown schematically in Fig. 1(a). Colloidomer chains are
assembled from monodisperse emulsion droplets composed of silicone oil
stabilized with lipid surfactant. The population of droplets has a mean radius
of $a_{p}=$1.58\pm 0.04\text{\,}\mathrm{\SIUnitSymbolMicro m}$$, as determined
by Total Holographic Characterization (xSight, Spheryx) [7]. Droplets are
linked into colloidomers using gold nanoparticles to act as bridges and are
dispersed in a layer of water between two horizontal glass surfaces that are
separated by $H\approx$24\text{\,}\mathrm{\SIUnitSymbolMicro m}$$. Links
between droplets can flow freely across the droplets’ surfaces. Colloidomers
therefore behave like freely jointed chains [4]. The sealed sample is mounted
on the stage of an in-line holographic video microscope that is outfitted with
holographic optical traps [9, 10]. Details of the colloidomers’ synthesis and
characterization are provided in Appendix A.

Holograms of colloidomers, such as the examples in Fig. 1(b), are analyzed
with Rayleigh-Sommerfeld back-propagation [11] to obtain the three-dimensional
position of each droplet in the chain. These coordinates are then linked into
the three-dimensional configuration of the chain at each recorded time step in
its sedimentation, as shown in Fig. 1(c). Measurements on chains of different
lengths reveal trends in sedimentation rate and curvature that can be compared
with predictions based on models for the forces acting on the chain.

Previous studies [12, 2, 13] have noted that hydrodynamic coupling among the
beads in a sedimenting chain reduces the viscous drag on beads near the center
relative to those at the ends. As a consequence, the central beads tend to
sediment faster, causing an initially linear chain to bend into a hairpin. The
representative data in Fig. 1(c) illustrate how confinement by rigid walls
suppresses the development of curvature, both at the beginning of the
trajectory and also at the end. Measuring the dynamics of sedimenting
colloidomers allows us to quantify the chains’ coupling to the walls and thus
to test idealized models for bead-chain hydrodynamics.

##  II Tracking sedimenting chains with Rayleigh-Sommerfeld Backpropagation

Figure 2: Holographic recording and reconstruction of a colloidomer’s three-
dimensional configuration. (a) A chain of droplets is illuminated with a
collimated laser beam. Interference between the scattered and incident light
creates an intensity pattern that is magnified by a microscope and recorded
with a video camera. (b) Hologram of a 10-droplet colloidomer stretched to its
full extent with holographic optical tweezers. (c) Rayleigh-Sommerfeld
reconstruction of the scattered intensity, $I_{R}(\boldsymbol{r},z)$, in the
plane $z=$18\text{\,}\mathrm{\SIUnitSymbolMicro m}$$ above the microscope’s
focal plane. (d) Axial dependence of the reconstructed intensity,
$I_{j}(z)=I_{R}(\boldsymbol{r}_{j},z)$, at the in-plane position,
$\boldsymbol{r}_{j}$, of one of the ten droplets. The inflection point is
identified with the droplet’s axial position, $z_{j}(t)$, at time $t$. Similar
reconstructions are performed for each droplet in the chain.

Figure 2 illustrates the measurement technique. The three-dimensional
configuration of a colloidomer is recorded through in-line holographic video
microscopy [14, 9]. As shown schematically in Fig. 2(a), the sample is
illuminated with a collimated laser beam. Light scattered by the droplets
interferes with the rest of the beam in the focal plane of a microscope. The
intensity of the magnified interference pattern is then recorded with a
standard video camera, as shown in Fig. 2(b). Each such video image is a
hologram of the colloidomer and encodes information about each droplet’s size,
refractive index and three-dimensional position [9]. Standard methods [7] to
extract this information are confounded by the strongly overlapping scattering
patterns from neighboring droplets. Rather than attempting to model such
complex light-scattering patterns [15], we instead localize the individual
droplets by numerically refocusing the hologram.

Given an estimate for the field scattered by a colloidomer into the focal
plane, $E_{s}(\boldsymbol{r},0)$, we can numerically reconstruct the scattered
field at height $z$ above the focal plane with the Rayleigh-Sommerfeld
diffraction integral [16, 9, 17]:

$E_{s}(\boldsymbol{r},z)=\int\tilde{E}_{s}(\boldsymbol{q},0)\,H(\boldsymbol{q},-z)\,e^{i\boldsymbol{q}\cdot\boldsymbol{r}}\,d^{2}q,$
(1a) where $\tilde{E}_{s}(\boldsymbol{q},0)=\int
E_{s}(\boldsymbol{r},0)\,e^{-i\boldsymbol{q}\cdot\boldsymbol{r}}\,d^{2}r,$
(1b) and where $H(\boldsymbol{q},-z)=e^{iz(k^{2}-q^{2})^{\frac{1}{2}}}$ (1c)
is the Fourier transform of the Rayleigh-Sommerfeld propagator [16]. The
associated estimate for the scattered light’s intensity at height $z$ is
$I_{s}(\boldsymbol{r},z)=\left|E_{s}(\boldsymbol{r},z)\right|^{2}.$ (1d)

The intensity distribution recorded by the camera can be modeled as the
superposition of the electric field due to the incident plane wave,
$\boldsymbol{E}_{0}(\boldsymbol{r})$, and the scattered field in the focal
plane, $\boldsymbol{E}_{s}(\boldsymbol{r},0)$ [9, 11]:

$\displaystyle I(\boldsymbol{r},0)$
$\displaystyle=\left|\boldsymbol{E}_{0}(\boldsymbol{r})+\boldsymbol{E}_{s}(\boldsymbol{r},0)\right|^{2}$
(2a) $\displaystyle\approx
I_{0}(\boldsymbol{r})+2\boldsymbol{E}_{0}^{\ast}(\boldsymbol{r})\cdot\boldsymbol{E}_{s}(\boldsymbol{r},0),$
(2b)

where
$I_{0}(\boldsymbol{r})=\left|\boldsymbol{E}_{0}(\boldsymbol{r})\right|^{2}$ is
the intensity of the illumination in the absence of scatterers and where we
assume that the intensity of the scattered wave is small enough compared with
the other terms to be omitted. If, furthermore, the scatterer is far enough
from the focal plane that polarization rotations can be neglected, the
normalized hologram,

$b(\boldsymbol{r})\equiv\frac{I(\boldsymbol{r},0)}{I_{0}(\boldsymbol{r})}-1,$
(3a) is related to the scattered field in the focal plane by
$b(\boldsymbol{r})\approx\frac{E_{s}(\boldsymbol{r},0)}{E_{0}^{\ast}(\boldsymbol{r})}+\frac{E_{s}^{\ast}(\boldsymbol{r},0)}{E_{0}(\boldsymbol{r})}.$
(3b)

This expression can be further simplified by modeling the collimated
illumination as a plane wave aligned with the imaging plane so that
$E_{0}^{\ast}(\boldsymbol{r})=E_{0}(\boldsymbol{r})=E_{0}$ [18].

Equation (3) shows that the normalized hologram records a superposition of the
field scattered by the colloidomer and also a fictive field propagating in the
opposite direction, which corresponds to the colloidomer’s mirror image in the
focal plane. The associated twin image can be suppressed numerically [19, 20,
11] at the cost of additional computational complexity. If the colloidomer is
far enough from the focal plane, however, perturbations due to the twin image
are weak enough to ignore without further processing [11]. In that case, the
scattered intensity, $I_{R}(\boldsymbol{r},z)$, at height $z$ above the focal
plane can be reconstructed numerically from a measured hologram by
substituting $b(\boldsymbol{r})$ for $E_{s}(\boldsymbol{r},0)$ in Eq. (1).

The image in Fig. 2(c) shows an estimate for the scattered intensity,
$I_{R}(\boldsymbol{r},z)$, obtained from the hologram in Fig. 2(b) in the
plane $z=$18\text{\,}\mathrm{\SIUnitSymbolMicro m}$$. Because this colloidomer
has been stretched into a straight line by optical tweezers, all of the
droplets come into sharpest focus in the same plane and appear in the
reconstructed image as an array of small bright spots. Interestingly, these
intensity maxima are offset from the brightest regions in the original
hologram, which illustrates the diffractive nature of the image-formation
process.

A quantitative estimate for a droplet’s three-dimensional position starts with
an estimate for its in-plane position, $\boldsymbol{r}_{p}$, which might be
obtained manually. The axial position, $z_{p}$, is then estimated by seeking
the point of inflection in the numerically reconstructed axial intensity
profile [9] along $\boldsymbol{r}_{p}$, as shown in Fig. 2(d). The image is
then refocused to $z_{p}$ and the estimate for $\boldsymbol{r}_{p}$ is refined
using standard particle-tracking algorithms [21]. Finally, $z_{p}$ is refined
using the improved estimate for $\boldsymbol{r}_{p}$. Numerical uncertainties
in the fit values suggest that this protocol achieves a precision of $\Delta
r_{p}=$0.1\text{\,}\mathrm{p}\mathrm{i}\mathrm{x}\mathrm{e}\mathrm{l}$=$5\text{\,}\mathrm{nm}$$
for the droplet’s in-plane position and $\Delta
z_{p}=$1\text{\,}\mathrm{p}\mathrm{i}\mathrm{x}\mathrm{e}\mathrm{l}$=$48\text{\,}\mathrm{nm}$$
along the axial direction.

The same procedure can be performed for each droplet in a chain and yields a
snapshot of the colloidomer’s instantaneous configuration. The mean separation
between droplet centers,

$\Delta
r=\frac{1}{N-1}\sum_{j=1}^{N-1}\left|\boldsymbol{r}_{j}(t)-\boldsymbol{r}_{j+1}(t)\right|,$
(4)

should be equal to the diameter of a single droplet. The data in Fig. 1 yield
$\Delta r/2=$1.5\pm 0.1\text{\,}\mathrm{\SIUnitSymbolMicro m}$$, which is
consistent with the holographically measured radius, $a_{p}=$1.58\pm
0.04\text{\,}\mathrm{\SIUnitSymbolMicro m}$$, for the population of emulsion
droplets used to assemble the chain. This agreement helps to validate the
tracking technique.

The data in Fig. 1(c) show the projection of a colloidomer’s three-dimensional
configuration onto the $x$-$z$ plane as it freely sediments within its sample
cell. Such configurational trajectories can be compared with predictions of
hydrodynamic models both to validate the tracking technique and also to cast
new light on the influence of confinement on colloidomer dynamics.

##  III Sedimentation of confined chains of beads

###  III.1 Sedimentation of a rigid chain

The drag force experienced by an isolated sphere of radius $a_{p}$ moving with
velocity $\boldsymbol{v}$ through a viscous fluid is given by [22],

$\displaystyle\boldsymbol{F}(\boldsymbol{v})=-\gamma_{0}\,\boldsymbol{v},\quad\text{where}$
(5a) $\displaystyle\gamma_{0}=6\pi\eta\,a_{p}$ (5b)

is the Stokes drag coefficient in a fluid of viscosity $\eta$. A fully
extended chain of spheres sedimenting perpendicularly to its axis can be
modeled as a long ellipsoid, for which the drag coefficient is [22]

$\gamma_{\infty}=\frac{8\pi\eta\,a}{\ln\left(2\frac{a}{b}\right)+\frac{1}{2}},$
(6)

where $a$ and $b$ are the semi-major and semi-minor axes, respectively.
Combining Eqs. (5b) and (6) suggests that the drag coefficient for an extended
chain of $N$ spheres is approximately

$\gamma_{N}=\frac{4}{3}\left(\frac{N}{\ln{2N}+\frac{1}{2}}\right)\gamma_{0}$
(7)

in the limit $N\gg 1$. The denominator of Eq. (7) implicitly incorporates
hydrodynamic coupling among the spheres, albeit without allowing the spheres
to rearrange themselves.

###  III.2 Confinement by a slit pore

Hydrodynamic coupling to bounding surfaces enhances the drag on a moving
object. For a sphere moving perpendicularly to a rigid wall, Faxén shows that
[23, 22]

$\gamma(h)\approx\gamma_{0}\left(1-\frac{9}{8}\frac{a_{p}}{h}\right)^{-1},$
(8)

where $h$ is the distance from the center of the sphere to the wall. The
analogous result for a horizontal chain of spheres at height $h$ above a
horizontal wall is [24]

$\gamma_{N}(h)=\gamma_{N}\left(1-\frac{9}{8}\frac{a_{p}}{h}\frac{\gamma_{N}}{\gamma_{0}}\right)^{-1}.$
(9)

Adding a second parallel wall at distance $H$ from the first, as shown in Fig.
1(a), disproportionately increases the complexity of the drag calculation
[25]. If $H\gg a_{p}$, however, we may invoke Oseen’s linear superposition
approximation [26],

$\gamma_{N}(h,H)\approx\gamma_{N}(h)+\gamma_{N}(H-h)-\gamma_{N}.$ (10)

With these simplifying approximations, a horizontally extended colloidomer
sedimenting through a viscous fluid in the space between two horizontal plane
walls should fall with a speed that depends on its height in the channel,

$\displaystyle v_{p}(h)=\frac{N}{\gamma_{N}(h,H)}\,\Delta
m_{p}g,\quad\text{where}$ (11a) $\displaystyle\Delta
m_{p}=\frac{4}{3}\pi\,a_{p}^{3}\,\Delta\rho_{p}$ (11b)

is the buoyant mass of a single droplet given its buoyant mass density,
$\Delta\rho_{p}$, and where
$g=$9.81\text{\,}\mathrm{m}\text{\,}{\mathrm{s}}^{-2}$$ is the acceleration
due to gravity.

##  IV Results

###  IV.1 Measured sedimentation of confined colloidomers

Figure 3: Velocity profiles of sedimenting colloidomers of chain lengths
$N=6$, 10 and 22. Monomer data ($N=1$) are fit to Eq. (11) with
$\gamma_{N}=\gamma_{0}$ . The fit yields the droplet’s buoyant density,
$\Delta\rho_{p}=$166\pm 7.\text{\,}\mathrm{kg}\text{\,}{\mathrm{m}}^{-3}$$,
and the wall separation, $H$. Colloidomer data are fit to Eq. (11) using the
same value for the droplet density, leaving only $H$ as an adjustable
parameter.

Figure 3 presents measurements of colloidomers’ sedimentation speed, $v(h)$,
as a function of height in the channel, $h$, and the number of droplets in the
chain, $N$. A measurement is initiated by trapping the two ends of a
colloidomer with a pair of holographic optical tweezers, stretching the chain
to its maximum extension, lifting it to a height $h$ above the sample
chamber’s lower wall, and then extinguishing the traps to let the chain
sediment freely. The optical traps are powered by a fiber laser (IPG
Photonics, YLR-LP-SF) operating at a vacuum wavelength of
$1064\text{\,}\mathrm{nm}$. The light is formed into programmable optical
traps by imprinting it with computer-generated holograms using a liquid-
crystal spatial light modulator (Holoeye PLUTO) [27, 28, 29, 10]. The
holograms are projected through the microscope’s objective lens using the
standard holographic optical trapping technique [30, 31] and are controlled
using the pyfab interface [32].

In-line holographic imaging is performed with a $3\text{\,}\mathrm{mW}$
collimated beam provided by a fiber-coupled diode laser (Coherent Cube)
operating at a vacuum wavelength of $\lambda=$447\text{\,}\mathrm{nm}$$. The
beam’s $3\text{\,}\mathrm{mm}$ waist barely overfills the input pupil of the
microscope’s objective lens (Nikon Plan Apo, 100×, numerical aperture 1.4, oil
immersion). A small proportion of the incident light is scattered by the chain
of droplets and interferes with the remainder of the beam in the focal plane
of the objective lens. The magnified interference pattern is relayed to a
monochrome video camera (FLIR Flea3 USB 3.0) that records its intensity every
$\Delta t=$66\text{\,}\mathrm{ms}$$. The exposure time of
$100\text{\,}\mathrm{\SIUnitSymbolMicro s}$ is fast enough to avoid
distortions due to motion blurring [33].

Each holographic snapshot in the video stream is analyzed with the methods of
Sec. II. A colloidomer’s height, $h(t)$, at time $t$ is computed as the
average of the axial positions of its constituent droplets. The uncertainty in
the height consists of the standard deviation of the droplets’ axial positions
in quadrature with the numerical error in the single-droplet measurements. The
colloidomer’s sedimentation speed is computed as the change in height during
the camera’s frame interval, $\Delta t$. All speeds are scaled by the
sedimentation speed for a single sphere at the midplane,

$\displaystyle v_{0}=\frac{\Delta
m_{p}g}{\gamma_{0}}\left(1-\frac{9}{2}\frac{a_{p}}{H}\right),$ (12)

which is found to be $v_{0}=$0.79(0.02)\text{\,}\mathrm{\SIUnitSymbolMicro
m}\text{\,}{\mathrm{s}}^{-1}$$ by fitting to the unscaled data for $N=1$.
Figure 3 presents the scaled results for the single droplet.

The single-droplet fit yields the buoyant density of the silicone oil mixture,
$\Delta\rho_{p}=$166\pm 7.\text{\,}\mathrm{kg}\text{\,}{\mathrm{m}}^{-3}$$,
and the height of the channel, $H$. The former is consistent with independent
measurements using a density meter (DMA 4500 M, Anton Paar) and is treated as
a fixed parameter when analyzing the data for colloidomers. Because different
sample cells have slightly different heights,
$H\approx$25\text{\,}\mathrm{\SIUnitSymbolMicro m}$$ is treated as an
adjustable parameter for each experiment and is resolved to within
$100\text{\,}\mathrm{nm}$.

The solid curves in Fig 3 are single-parameter fits to Eq. (11) for chains of
length $N=6$, 10 and 22. Predictions of the rigid-chain model agree well with
the measured sedimentation profiles of colloidomers despite the colloidomers’
flexibility.

Colloidomers sediment more slowly near walls than individual spheres because
of the length-dependent enhancement to hydrodynamic coupling described by Eq.
(9). This effect is stronger for longer chains. Conversely, colloidomers
sediment more rapidly than individual spheres near the middle of the channel
where wall-induced drag has less influence than the drag reduction afforded by
coupling to neighboring droplets. The crossover between these two effects is
modeled by the length-dependent denominator in Eq. (7). None of these
comparisons, however, take account of the curvature that develops as
colloidomers sediment.

###  IV.2 Curvature of confined sedimenting colloidomers

Hydrodynamic coupling reduces the drag on droplets near the center of the
chain relative to those at the ends. The central droplets therefore should
sediment faster, causing the chain to bend, and eventually to adopt a hairpin
configuration [12, 2]. The tendency for the center of a flexible chain to
sediment fastest is evident in the early stages of the trajectory plotted in
Fig. 1(c).

Hydrodynamic coupling to the upper wall complicates this process because the
associated contribution to the drag tends to be greater for spheres near the
center of the chain, which have more neighbors. The additional drag tends to
suppress the emergence of curvature relative to a free chain. Once curvature
develops, however, this contribution to the wall-associated drag will most
strongly affect the droplets that remain closest to the wall, accelerating the
evolution of curvature. Depending on chain length and its initial distance
from the upper wall, this competition could favor the development of negative
curvature, with the end droplets initially falling faster than the central
droplets [34].

We avoid this complication by releasing the chains away from the upper wall
thereby weakening that wall’s influence on the chains’ dynamics and focusing
attention on the lower wall’s influence. As indicated in Fig. 1(c),
colloidomers are stretched to their full extent with optical tweezers, lifted
to height $h=$0.7$H$ in the channel and then released to sediment freely.
Figure 4 shows how a colloidomer’s curvature evolves as it sediments. The
instantaneous curvature at arc length $s$ along the time-evolving three-
dimensional conformation, $\boldsymbol{r}(s,t)$, may be computed as

$\kappa(s,t)=\frac{\left|\boldsymbol{r}^{\prime}\times\boldsymbol{r}^{\prime\prime}\right|}{\left|\boldsymbol{r}^{\prime}\right|^{3}},$
(13)

where primes denote derivatives with respect to $s$. Equation (13) can be
approximated for the discrete vertices of a colloidomer by the three-point
Menger curvature. The discrete points in Fig. 4(a) report the maximum
curvature, $\kappa(h)=\max\\{\kappa(s,h)\\}$, for colloidomers of length
$N=10$, 14 and 22, where $h=h(t)$ is the colloidomer’s mean height in the
channel at time $t$. The shaded regions indicate the range of curvature values
between the mean curvature and the maximum.

Introducing curvature into a colloidomer involves moving droplets
longitudinally along the chain to conserve the chain’s length. The associated
contribution to the drag is proportional to the total amount of longitudinal
displacement and therefore is proportional to the length of the chain. Scaling
the curvature by the chain length therefore yields a dimensionless curvature
that should increase linearly with time as the chain sediments [2]. The data
collapse in Fig. 4(b) is consistent with this interpretation under conditions
where the chains are near the channel’s midplane and confinement effects are
weak.

Hydrodynamically mediated curvature is augmented by Brownian coiling [4],
whose influence can be seen in Fig. 1(b). The curvature due to coiling can
exceed that for hydrodynamic bending in a long chain that sediments slowly.
The curvature plotted in Fig. 4 therefore becomes increasingly noisy at later
times, especially for the longest chain with $N=22$.

As the chain sediments below the midplane of the channel, its hydrodynamic
coupling to the lower wall increases. This tends to reduce its
hydrodynamically induced curvature even before the bottom-most droplets touch
down. Once the chain makes contact, the vertical component of its curvature is
mechanically suppressed, leaving only the in-plane curvature due to coiling.

Figure 4: (a) The maximum three-point curvature of a colloidomer chain,
$\kappa(h)$, as a function of the colloidomer’s mean height in the channel.
Data are shown for $N=10$ (green squares), $N=14$ (gold inverted triangles),
and $N=22$ (red diamonds). Shaded areas show the range between mean and
maximum values. (b) Scaling the curvature by the chain length effectively
collapses the three data sets.

##  V Discussion

Holographic microscopy is a powerful tool for measuring the three-dimensional
trajectories of micrometer-scale objects [9, 7]. Taking a targeted approach to
Rayleigh-Sommerfeld reconstruction extends these capabilities to systems, such
as colloidomers, that consist of close-packed particles. Measurements of
colloidomer sedimentation in a slit pore validate the technique by yielding
results for chains’ trajectories that are consistent with hydrodynamic models.

###### Acknowledgements.

This work was supported by the National Science Foundation through Award
Number DMR-2104837 and Award Number DMR-2105255. The xSight holographic
particle characterization instrument was acquired as shared instrumentation
with support from the MRSEC program of the NSF under Award No. DMR-1420073.
The integrated holographic trapping and holographic microscopy instrument used
for this study was constructed as shared instrumentation with support from the
NSF under Award No. DMR-0922680. We gratefully acknowledge extensive
discussions with Angus McMullen regarding the preparation of colloidomer
chains.

##  Appendix A Colloidomer Synthesis

Our emulsion droplets are created from a 1:1:1 mixture by volume fraction of
three types of silane monomers: (a) dimethyldiethoxysilane (Sigma-Aldrich),
commonly known as DMDES, (b) (3,3,3-trifluoropropyl) methyldimethoxysilane
(Gelest), and (c) 3-glycidoxypropylmethyldiethoxysilane (Gelest). Droplets are
condensed out of an aqueous monomer solution by ammonia-catalyzed hydrolysis
and condensation following the procedure described in Ref. [35]. Specifically,
$175\text{\,}\mathrm{\SIUnitSymbolMicro L}$ of monomer is dissolved in
$3.115\text{\,}\mathrm{mL}$ of deionized water by vortexing. Droplet
nucleation is initiated by adding $1\text{\,}\mathrm{\char
37\relax}\mathrm{v}\mathrm{/}\mathrm{v}$ of $27\text{\,}\mathrm{\char
37\relax}$ ammonium hydroxide solution (Sigma-Aldrich). Droplet growth is
stopped after 6 hours by washing the sample with $1\text{\,}\mathrm{mM}$
sodium dodecyl sulfate solution (SDS, Sigma-Aldrich). The sample is
centrifuged and resuspended with $1\text{\,}\mathrm{mM}$ SDS solution three
times. The completed emulsion is stored in $5\text{\,}\mathrm{mM}$ SDS.

The droplets are stabilized with lipid surfactants. Lipid labeling is achieved
by diluting $10\text{\,}\mathrm{\SIUnitSymbolMicro L}$ of packed droplets with
$190\text{\,}\mathrm{\SIUnitSymbolMicro L}$ of $5\text{\,}\mathrm{mM}$ SDS
solution containing $1\text{\,}\mathrm{\SIUnitSymbolMicro L}$ DSPE-PEG-SH
thiol-terminated lipid (Avanti Polar Lipids, MW 2000). The mixture is kept on
a rotary mixer overnight. Excess lipid is washed off by centrifuging, and
replacing the supernatant layer with $1\text{\,}\mathrm{mM}$ SDS each time.

Droplets are assembled into linear chains using methods described in Refs.
[36, 35, 37]. The emulsion droplets are first concentrated by centrifugation
before being redispersed in a commercial ferrofluid (EMG 707, Ferrotec) along
with $1\text{\,}\mathrm{mM}$ Tris-EDTA (Thermo Fischer Scientific) at pH 8 and
$30\text{\,}\mathrm{nm}$-diameter gold nanoparticles (BBI Solutions, EMGC30)
at a concentration of ${10}^{11}\text{\,}{\mathrm{mL}}^{-1}$. This mixture is
imbibed into a rectangular capillary tube (VitroCom) by capillary action and
is subjected to an external magnetic field of roughly $1\text{\,}\mathrm{T}$
aligned with the capillary’s long axis that is applied with a pair of
neodymium rare-earth magnets. The emulsion droplets act as diamagnetic bubbles
in the ferrofluid and are organized into chains aligned with the field by
induced-dipole interactions.

Individual droplets become decorated with gold nanoparticles that bind
irreversibly to the lipids’ terminal thiol groups. Once bound, the gold
nanoparticles diffuse across the droplets’ fluid surfaces until they reach the
contact region between neighboring droplets. There, they form bridges between
the droplets, binding the field-induced lines of droplets into permanent
colloidomer chains. The droplets remain in a fluid state so that the inter-
droplet bonds are fully flexible. Hematite nanoparticles from the ferrofluid
are prevented from binding to the thiol groups through the addition of EDTA.

Stable colloidomer chains form after roughly two hours at room temperature,
after which they are washed out of the capillary into
$100\text{\,}\mathrm{\SIUnitSymbolMicro L}$ of $0.5\text{\,}\mathrm{\char
37\relax}\mathrm{v}\mathrm{/}\mathrm{v}$ Pluronic F-108 solution (Sigma-
Aldrich). Excess ferrofluid is pipetted off the top with the help of a bar
magnet. The remaining sample is pipetted between a glass microscope slide and
a glass #1.5 coverslip (Globe Scientific), and sealed using UV-cured adhesive
(LOON, UV Clear Fly Finish).

## References

  * Byrom  _et al._ [2014] J. Byrom, P. Han, M. Savory, and S. L. Biswal, Directing assembly of DNA-coated colloids with magnetic fields to generate rigid, semiflexible, and flexible chains, Langmuir 30, 9045 (2014).
  * Cunha  _et al._ [2022] L. H. Cunha, J. Zhao, F. C. MacKintosh, and S. L. Biswal, Settling dynamics of Brownian chains in viscous fluids, Phys. Rev. Fluids 7, 034303 (2022).
  * Feng  _et al._ [2013] L. Feng, L.-L. Pontani, R. Dreyfus, P. Chaikin, and J. Brujic, Specificity, flexibility and valence of DNA bonds guide emulsion architecture, Soft Matter 9 (2013).
  * McMullen  _et al._ [2018] A. McMullen, M. Holmes-Cerfon, F. Sciortino, A. Y. Grosberg, and J. Brujic, Freely jointed polymers made of droplets, Phys. Rev. Lett. 121, 138002 (2018).
  * McMullen  _et al._ [2022] A. McMullen, M. Muñoz Basagoiti, Z. Zeravcic, and J. Brujic, Self-assembly of emulsion droplets through programmable folding, Nature 610, 502–506 (2022).
  * Coulais  _et al._ [2018] C. Coulais, A. Sabbadini, F. Vink, and M. van Hecke, Multi-step self-guided pathways for shape-changing metamaterials, Nature 561, 512 (2018).
  * Lee  _et al._ [2007] S.-H. Lee, Y. Roichman, G.-R. Yi, S.-H. Kim, S.-M. Yang, A. Van Blaaderen, P. Van Oostrum, and D. G. Grier, Characterizing and tracking single colloidal particles with video holographic microscopy, Opt. Express 15, 18275 (2007).
  * Fung  _et al._ [2012] J. Fung, R. W. Perry, T. G. Dimiduk, and V. N. Manoharan, Imaging multiple colloidal particles by fitting electromagnetic scattering solutions to digital holograms, J. Quant. Spectrosc. Radiat. Transf. 113, 2482 (2012).
  * Lee and Grier [2007] S.-H. Lee and D. G. Grier, Holographic microscopy of holographically trapped three-dimensional structures, Opt. Express 15, 1505 (2007).
  * O’Brien and Grier [2019] M. J. O’Brien and D. G. Grier, Above and beyond: Holographic tracking of axial displacements in holographic optical tweezers, Opt. Express 27, 25375 (2019).
  * Dixon  _et al._ [2011a] L. Dixon, F. C. Cheong, and D. G. Grier, Holographic deconvolution microscopy for high-resolution particle tracking, Opt. Express 19, 16410 (2011a).
  * Li  _et al._ [2013] L. Li, H. Manikantan, D. Saintillan, and S. E. Spagnolie, The sedimentation of flexible filaments, J. Fluid Mech. 735, 705–736 (2013).
  * Shashank  _et al._ [2023] H. Shashank, Y. Melikhov, and M. L. Ekiel-Jeżewska, Dynamics of ball chains and highly elastic fibres settling under gravity in a viscous fluid, Soft Matter 19, 4829 (2023).
  * Sheng  _et al._ [2006] J. Sheng, E. Malkiel, and J. Katz, Digital holographic microscope for measuring three-dimensional particle distributions and motions, Appl. Opt. 45, 3893 (2006).
  * Martin  _et al._ [2022] C. Martin, L. E. Altman, S. Rawat, A. Wang, D. G. Grier, and V. N. Manoharan, In-line holographic microscopy with model-based analysis, Nat. Rev. Methods Primers 2, 83 (2022).
  * Goodman [2005] J. W. Goodman,  _Introduction to Fourier Optics_ , 3rd ed. (McGraw-Hill, New York, 2005).
  * Cheong  _et al._ [2010] F. C. Cheong, B. J. Krishnatreya, and D. G. Grier, Strategies for three-dimensional particle tracking with holographic video microscopy, Opt. Express 18, 13563 (2010).
  * Moyses  _et al._ [2013] H. W. Moyses, B. J. Krishnatreya, and D. G. Grier, Robustness of Lorenz-Mie microscopy against defects in illumination, Opt. Express 21, 5968 (2013).
  * Latychevskaia and Fink [2007] T. Latychevskaia and H.-W. Fink, Solution to the twin image problem in holography, Phys. Rev. Lett. 98, 233901 (2007).
  * Zhang  _et al._ [2018] W. Zhang, L. Cao, D. J. Brady, H. Zhang, J. Cang, H. Zhang, and G. Jin, Twin-image-free holography: a compressive sensing approach, Phys. Rev. Lett. 121, 093902 (2018).
  * Crocker and Grier [1996] J. C. Crocker and D. G. Grier, Methods of digital video microscopy for colloidal studies, J. Colloid Interf. Sci. 179, 298 (1996).
  * Happel and Brenner [1991] J. Happel and H. Brenner,  _Low Reynolds Number Hydrodynamics_ (Kluwer, Dordrecht, 1991).
  * Brenner [1962] H. Brenner, Effect of finite boundaries on the Stokes resistance of an arbitrary particle, J. Fluid Mech. 12, 35 (1962).
  * Hadamard [1911] J. S. Hadamard, Mouvement permanent lent d’une sphère liquide et visqueuse dans un liquide visqueux, C. R. Acad. Sci. 152, 1735 (1911).
  * Liron and Mochon [1976] N. Liron and S. Mochon, Stokes flow for a stokeslet between two parallel flat plates, J. Eng. Math. 10 (1976).
  * Dufresne  _et al._ [2000] E. R. Dufresne, D. Altman, and D. G. Grier, Brownian dynamics of a sphere between parallel walls, EPL 53, 264 (2000).
  * Reicherter  _et al._ [1999] M. Reicherter, T. Haist, E. U. Wagemann, and H. J. Tiziani, Optical particle trapping with computer-generated holograms written on a liquid-crystal display, Opt. Lett. 24, 608 (1999).
  * Curtis  _et al._ [2002] J. E. Curtis, B. A. Koss, and D. G. Grier, Dynamic holographic optical tweezers, Opt. Commun. 207, 169 (2002).
  * Polin  _et al._ [2005] M. Polin, K. Ladavac, S.-H. Lee, Y. Roichman, and D. G. Grier, Optimized holographic optical traps, Opt. Express 13, 5831–5845 (2005).
  * Grier [2003] D. G. Grier, A revolution in optical manipulation, Nature 424, 810–816 (2003).
  * Dufresne and Grier [1998] E. R. Dufresne and D. G. Grier, Optical tweezer arrays and optical substrates created with diffractive optical elements, Rev. Sci. Instrum. 69, 1974–1977 (1998).
  * Grier  _et al._ [2024] D. G. Grier, J. Sustiel, S. Zare, and N. Wittler, pyfab: Platform for holographic optical trapping, Zenodo 10.5281/zenodo.10719303 (2024).
  * Dixon  _et al._ [2011b] L. Dixon, F. C. Cheong, and D. G. Grier, Holographic particle-streak velocimetry, Opt. Express 19, 4393 (2011b).
  * Perrin  _et al._ [2019] H. Perrin, A. Eddi, S. Karpitschka, J. H. Snoeijer, and B. Andreotti, Peeling an elastic film from a soft viscoelastic adhesive: experiments and scaling laws, Soft Matter 15, 770 (2019).
  * Elbers  _et al._ [2015] N. A. Elbers, J. Jose, A. Imhof, and A. van Blaaderen, Bulk scale synthesis of monodisperse PDMS droplets above 3 $\mu$m and their encapsulation by elastic shells, Chem. Mater. 27, 1709 (2015).
  * Obey and Vincent [1994] T. M. Obey and B. Vincent, Novel Monodisperse “Silicone Oil”/Water Emulsions, J. Colloid Interf. Sci. 163, 454 (1994).
  * McMullen  _et al._ [2021] A. McMullen, S. Hilgenfeldt, and J. Brujic, DNA self-organization controls valence in programmable colloid design, PNAS 118, e2112604118 (2021).


#  sbi \- a toolkit for simulation-based inference

Álvaro Tejero-Cantero$\;{}^{\,,\,1},\;$ Jan Boelts${}^{*,\,1},\;$ Michael
Deistler${}^{*,\,1},\;$ Jan-Matthis Lueckmann${}^{*,\,1},\;$
Conor Durkan∗, 2, Pedro J. Gonçalves${}^{1,\,3},\;$ David S.
Greenberg${}^{1,\,4},\;$ Jakob H. Macke1, 5, 6
Computational Neuroengineering, TU Munich1, School of Informatics, University
of Edinburgh2,
Neural Systems Analysis, Center of Advanced European Studies and Research
(caesar), Bonn3,
Model-Driven Machine Learning, Centre for Materials and Coastal Research,
Helmholtz-Zentrum Geesthacht4,
Machine Learning in Science, University of Tübingen5,
Empirical Inference, Max Planck Institute for Intelligent Systems, Tübingen6
{alvaro.tejero, jan.boelts, michael.deistler<EMAIL_ADDRESS>equally contributing.

###### Abstract

Scientists and engineers employ stochastic numerical simulators to model
empirically observed phenomena. In contrast to purely statistical models,
simulators express scientific principles that provide powerful inductive
biases, improve generalization to new data or scenarios and allow for fewer,
more interpretable and domain-relevant parameters. Despite these advantages,
tuning a simulator’s parameters so that its outputs match data is challenging.
Simulation-based inference (SBI) seeks to identify parameter sets that a) are
compatible with prior knowledge and b) match empirical observations.
Importantly, SBI does not seek to recover a single ‘best’ data-compatible
parameter set, but rather to identify all high probability regions of
parameter space that explain observed data, and thereby to quantify parameter
uncertainty. In Bayesian terminology, SBI aims to retrieve the posterior
distribution over the parameters of interest. In contrast to conventional
Bayesian inference, SBI is also applicable when one can run model simulations,
but no formula or algorithm exists for evaluating the probability of data
given parameters, i.e. the likelihood.

We present sbi, a PyTorch-based package111sbi is available at mackelab.org/sbi
under the AGPLv3 license. that implements SBI algorithms based on neural
networks. sbi facilitates inference on black-box simulators for practising
scientists and engineers by providing a unified interface to state-of-the-art
algorithms together with documentation and tutorials.

_K_ eywords Simulation $\cdot$ Bayesian inference $\cdot$ Simulation-based
inference $\cdot$ System identification

##  1 Motivation

Bayesian inference is a principled approach for determining parameters
consistent with empirical observations: Given a prior over parameters, a
stochastic simulator, and observations, it returns a posterior distribution.
In cases where the simulator likelihood _can_ be evaluated, many methods for
approximate Bayesian inference exist (e.g., [1, 2, 3, 4, 5]). For more general
simulators, however, evaluating the likelihood of data given parameters might
be computationally intractable. Traditional algorithms for this ‘likelihood-
free’ setting [6] are based on Monte-Carlo rejection [7, 8], an approach known
as _Approximate Bayesian Computation_ (ABC). More recently, algorithms based
on neural networks have been developed [9, 10, 11, 12, 13]. These algorithms
are not based on rejecting simulations, but rather train deep neural
conditional density estimators or classifiers on simulated data. To aid in
effective application of these algorithms to a wide range of problems, sbi
closely integrates with PyTorch and offers state-of-the-art neural network-
based SBI algorithms [11, 13, 12] with flexible choice of network
architectures and flow-based density estimators. With sbi, researchers can
easily implement new neural inference algorithms, benefiting from the
infrastructure to manage simulators and a unified posterior representation.
Users, in turn, can profit from a single inference interface that allows them
to either use their own custom neural network, or choose from a growing
library of preconfigured options provided with the package.

###  1.1 Related software and use in research

We are aware of several mature packages that implement SBI algorithms. elfi
[14] is a package offering BOLFI, a Gaussian process-based algorithm [15], and
some classical ABC algorithms. The package carl [16] implements the algorithm
described in [17]. Two other SBI packages, currently under development, are
hypothesis [18] and pydelfi [19]. pyabc [20] and ABCpy [21] are two packages
offering a diversity of ABC algorithms.

sbi is closely integrated with PyTorch [22] and uses nflows [23] for flow-
based density estimators. sbi builds on experience accumulated developing
delfi [24], which it succeeds. delfi was based on theano [25] (development
discontinued) and developed both for SBI research [12, 10] and for scientific
applications [26]. The sbi codebase started as a fork of lfi [27], developed
for [28].

##  2 Description

sbi currently implements three families of neural inference algorithms:

  * •

Sequential Neural _Posterior_ Estimation (SNPE) trains a deep neural density
estimator that directly estimates the posterior distribution of parameters
given data. Afterwards, it can sample parameter sets from the posterior, or
evaluate the posterior density on any parameter set. Currently, SNPE-C [12] is
implemented in sbi.

  * •

Sequential Neural _Likelihood_ Estimation (SNLE) [11] trains a deep neural
density estimator of the likelihood, which then allows to sample from the
posterior using e.g. MCMC.

  * •

Sequential Neural _Ratio_ Estimation (SNRE) [13, 28] trains a classifier to
estimate density ratios, which in turn can be used to sample from the
posterior e.g. with MCMC.

The inference step returns a NeuralPosterior object that represents the
uncertainty about the parameters conditional on an observation, i.e. the
posterior distribution. This object can be sampled from —and if the chosen
algorithm allows, evaluated— with the same API as a standard PyTorch
probability distribution.

An important challenge in making SBI algorithms usable by a broader community
is to deal with diverse, often pre-existing, complex simulators. sbi works
with any simulator as long as it can be wrapped in a Python callable.
Furthermore, sbi ensures that custom simulators work well with neural
networks, e.g. by performing automatic shape inference, standardizing inputs
or handling failed simulations. To maximize simulator performance, sbi
leverages vectorization where available and optionally parallelizes
simulations using joblib [29]. Moreover, if dimensionality reduction of the
simulator output is desired, sbi can use a trainable summarizing network to
extract relevant features from raw simulator output and spare the user manual
feature engineering.

In addition to the full-featured interface, sbi provides also a _simple_
interface which consists of a single function call with reasonable defaults.
This allows new users to get familiarized with simulation-based inference and
quickly obtain results without having to define custom networks or tune
hyperparameters.

With sbi, we aim to support scientific discovery and computational engineering
by making Bayesian inference applicable to the widest class of models
(simulators with no likelihood available), and practical for complex problems.
We have designed an open architecture and adopted community-oriented
development practices in order to invite other machine-learning researchers to
join us in this long-term vision.

### Acknowledgements

This work has been supported by the German Federal Ministry of Education and
Research (BMBF, project ‘ADIMEM’, FKZ 01IS18052 A-D), the German Research
Foundation (DFG) through SFB 1089 ‘Synaptic Microcircuits’, SPP 2041
‘Computational Connectomics’ and Germany’s Excellence Strategy – EXC-Number
2064/1 – Project number 390727645.

Conor Durkan was supported by the EPSRC Centre for Doctoral Training in Data
Science, funded by the UK Engineering and Physical Sciences Research Council
(grant EP/L016427/1) and the University of Edinburgh.

We are grateful to Artur Bekasov, George Papamakarios and Iain Murray for
making nflows [23] available, a package for normalizing flow-based density
estimation which sbi leverages extensively.

## References

  * [1] Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller.  Equation of state calculations by fast computing machines.  The journal of chemical physics, 21(6):1087–1092, 1953.
  * [2] Radford M Neal.  Slice sampling.  The Annals of Statistics, 31(3):705–741, 2003.
  * [3] Matthew M. Graham and Amos J. Storkey.  Asymptotically exact inference in differentiable generative models.  Electronic Journal of Statistics, 11(2):5105–5164, 2017.
  * [4] Tuan Anh Le, Atilim Gunes Baydin, and Frank Wood.  Inference compilation and universal probabilistic programming.  Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS) 2017, 54, 2017.
  * [5] Atilim Güneş Baydin, Lei Shao, Wahid Bhimji, Lukas Heinrich, Lawrence Meadows, Jialin Liu, Andreas Munk, Saeid Naderiparizi, Bradley Gram-Hansen, Gilles Louppe, et al.  Etalumis: bringing probabilistic programming to scientific simulators at scale.  In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1–24, 2019.
  * [6] Kyle Cranmer, Johann Brehmer, and Gilles Louppe.  The frontier of simulation-based inference.  Proceedings of the National Academy of Sciences, 2020.
  * [7] Jonathan K Pritchard, Mark T Seielstad, Anna Perez-Lezaun, and Marcus W Feldman.  Population growth of human y chromosomes: a study of y chromosome microsatellites.  Molecular biology and evolution, 16(12):1791–1798, 1999.
  * [8] Scott A Sisson, Yanan Fan, and Mark M Tanaka.  Sequential monte carlo without likelihoods.  Proceedings of the National Academy of Sciences, 104(6):1760–1765, 2007.
  * [9] George Papamakarios and Iain Murray.  Fast $\epsilon$-free inference of simulation models with bayesian conditional density estimation.  In Advances in Neural Information Processing Systems 29, pages 1028–1036. 2016.
  * [10] Jan-Matthis Lueckmann, Pedro J Goncalves, Giacomo Bassetto, Kaan Öcal, Marcel Nonnenmacher, and Jakob H Macke.  Flexible statistical inference for mechanistic models of neural dynamics.  In Advances in Neural Information Processing Systems 30, pages 1289–1299. 2017.
  * [11] George Papamakarios, David Sterratt, and Iain Murray.  Sequential neural likelihood: Fast likelihood-free inference with autoregressive flows.  Proceedings of Machine Learning Research, 89:837–848, 2019.
  * [12] David Greenberg, Marcel Nonnenmacher, and Jakob Macke.  Automatic posterior transformation for likelihood-free inference.  In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2404–2414. PMLR, 2019.
  * [13] Joeri Hermans, Volodimir Begy, and Gilles Louppe.  Likelihood-free mcmc with approximate likelihood ratios.  In Proceedings of the 37th International Conference on Machine Learning, volume 98 of Proceedings of Machine Learning Research. PMLR, 2020\.
  * [14] Jarno Lintusaari, Henri Vuollekoski, Antti Kangasrääsiö, Kusti Skytén, Marko Järvenpää, Pekka Marttinen, Michael U Gutmann, Aki Vehtari, Jukka Corander, and Samuel Kaski.  Elfi: engine for likelihood-free inference.  The Journal of Machine Learning Research, 19(1):643–649, 2018.
  * [15] Michael U Gutmann and Jukka Corander.  Bayesian optimization for likelihood-free inference of simulator-based statistical models.  The Journal of Machine Learning Research, 17(1):4256–4302, 2016\.
  * [16] Gilles Louppe, Kyle Cranmer, and Juan Pavez.  carl: a likelihood-free inference toolbox.  Journal of Open Source Software, 1(1):11, 2016.
  * [17] Kyle Cranmer, Juan Pavez, and Gilles Louppe.  Approximating likelihood ratios with calibrated discriminative classifiers.  arXiv preprint arXiv:1506.02169, 2015.
  * [18] Joeri Hermans.  Hypothesis.  https://github.com/montefiore-ai/hypothesis, 2019.
  * [19] Justin Alsing.  pydelfi: Density estimation likelihood-free inference.  https://github.com/justinalsing/pydelfi, 2019.
  * [20] Emmanuel Klinger, Dennis Rickert, and Jan Hasenauer.  pyabc: distributed, likelihood-free inference.  Bioinformatics, 34(20):3591–3593, 2018.
  * [21] The ABCpy authors.  Abcpy.  https://github.com/eth-cscs/abcpy, 2017.
  * [22] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  pages 8024–8035. 2019.
  * [23] Conor Durkan, Artur Bekasov, George Papamakarios, and Iain Murray.  nflows: Normalizing flows in pytorch.  https://github.com/bayesiains/nflows, 2019.
  * [24] mackelab.org.  Delfi: Density estimation likelihood-free inference.  https://github.com/mackelab/delfi, 2017.
  * [25] Rami Al-Rfou, Guillaume Alain, Amjad Almahairi, Christof Angermueller, Dzmitry Bahdanau, Nicolas Ballas, Frédéric Bastien, Justin Bayer, Anatoly Belikov, Alexander Belopolsky, et al.  Theano: A python framework for fast computation of mathematical expressions.  arXiv, pages arXiv–1605, 2016.
  * [26] Pedro J Gonçalves, Jan-Matthis Lueckmann, Michael Deistler, Marcel Nonnenmacher, Kaan Öcal, Giacomo Bassetto, Chaitanya Chintaluri, William F Podlaski, Sara A Haddad, Tim P Vogels, David S. Greenberg, and Jakob H. Macke.  Training deep neural density estimators to identify mechanistic models of neural dynamics.  bioRxiv, page 838383, 2019.
  * [27] Conor Durkan.  lfi.  https://github.com/conormdurkan/lfi, 2020.
  * [28] Conor Durkan, Iain Murray, and George Papamakarios.  On contrastive learning for likelihood-free inference.  Proceedings of the 36th International Conference on Machine Learning, 98, 2020.
  * [29] Gael Varoquaux.  joblib.  https://github.com/joblib/joblib, 2008.


# Eulerian $k$-dominating reconfiguration graphs

M.E. Messinger, Amanda Porter∗ Department of Mathematics and Computer Science,
Mount Allison University, Sackville, NB, Canada

###### Abstract

For a graph $G$, the vertices of the $k$-dominating graph, denoted
$\mathcal{D}_{k}(G)$, correspond to the dominating sets of $G$ with
cardinality at most $k$. Two vertices of $\mathcal{D}_{k}(G)$ are adjacent if
and only if the corresponding dominating sets in $G$ can be obtained from one
other by adding or removing a single vertex of $G$. Since $\mathcal{D}_{k}(G)$
is not necessarily connected when $k<|V(G)|$, much research has focused on
conditions under which $\mathcal{D}_{k}(G)$ is connected and recent work has
explored the existence of Hamilton paths in the $k$-dominating graph. We
consider the complementary problem of determining the conditions under which
the $k$-dominating graph is Eulerian. In the case where $k=|V(G)|$, we
characterize those graphs $G$ for which $\mathcal{D}_{k}(G)$ is Eulerian. In
the case where $k$ is restricted, we determine for a number of graph classes,
the conditions under which the $k$-dominating graph is Eulerian.

keywords and phrases: domination, reconfiguration, $k$-dominating graph,
Eulerian graphs

2020 AMS subject classification: 05C45, 05C69

##  1 Introduction

Reconfiguration examines the relationships between feasible solutions to a
problem. Each feasible solution is represented by a vertex in a
reconfiguration graph, where two vertices are adjacent if and only if the
associated solutions are related according to some predetermined rule.
Research has focused on determining structural properties of reconfiguration
graphs, with considerable interest in determining the conditions required for
a reconfiguration graph to be connected (see the surveys [9, 11]). While many
different problems could be modeled with a reconfiguration graph (see [11] for
examples), to date, most research has considered the underlying problem to be
graph-theoretic, such as colouring or domination.

In this paper, we consider the $k$-dominating graph, which was first
introduced in 2014 [7]. Given a graph $G$, each dominating set of cardinality
at most $k$, is represented by a vertex in the $k$-dominating graph. Two
vertices in the $k$-dominating graph are adjacent if and only if one of the
associated dominating sets can be obtained from the other by adding or
removing a single vertex. Given a graph $G$, its $k$-dominating graph is
denoted by $\mathcal{D}_{k}(G)$. In the case where $k=|V(G)|$, we omit the
subscript and simply refer to $\mathcal{D}(G)$ as the dominating graph of $G$.
The dominating graph of $P_{4}$ is illustrated in Figure 1 (b) and the
$k$-dominating graph with $k=3$ is illustrated in Figure 1 (c).

Figure 1: An example of $k$-dominating graphs of $P_{4}$.

For a graph $G$, the $k$-dominating graph is always connected when $k=|V(G)|$:
for any dominating set, add any unused vertex to obtain another dominating
set. This is not always the case when $k<|V(G)|$; a simple example is
$\mathcal{D}_{3}(K_{1,3})$. The dominating set consisting of the three
vertices of degree one is a minimal dominating set of $K_{1,3}$. If $k=3$,
then the corresponding vertex in $\mathcal{D}_{3}(K_{1,3})$ is isolated.
Consequently, research has focussed on the conditions required for a
$k$-dominating graph to be connected (see [10], for example). In terms of
complexity, determining whether $\mathcal{D}_{k}(G)$ is connected, is PSPACE-
complete even for graphs of bounded bandwidth, split graphs, planar graphs,
and bipartite graphs [8] (see the survey [11] for additional algorithmic
results).

In [7], Haas and Seyffarth asked about the conditions required for a
$k$-dominating graph to be Hamiltonian. Adaricheva et al. [1] showed that no
dominating graph contains a Hamilton cycle because dominating graphs are
inherently bipartite and contain an odd number of vertices. Adaricheva et al.
[2] subsequently proved that the dominating graph of a tree always contains a
Hamilton path and that the dominating graph of a cycle on $n$ vertices
contains a Hamilton path if and only if $n\not\equiv 0$ (mod $4$).

Determining whether a graph is Eulerian is generally very easy when compared
to determining the existence of a Hamilton path or cycle and this motivates us
to ask the following questions.

######  Question 1.

For which graphs $G$, is $\mathcal{D}(G)$ Eulerian?

######  Question 2.

For which graphs $G$ and integers $k$, where $\gamma(G)<k<|V(G)|$, is
$\mathcal{D}_{k}(G)$ Eulerian?

In Section 2, we answer Question 1 by providing a characterization of Eulerian
dominating graphs. In Section 3, we answer Question 2 for various classes of
graphs $G$, including paths, cycles, cocktail party graphs, complete graphs,
and complete bipartite graphs. We conclude with observations relating to well-
dominated graphs.

We end this section with a few definitions and comments on notation. A graph
is Eulerian if and only if every vertex has even degree. To reduce confusion,
we refer to graph $G$ as the seed graph of $\mathcal{D}_{k}(G)$. A dominating
set in seed graph $G$ will be denoted by a capital letter and the vertex in
$\mathcal{D}_{k}(G)$ or $\mathcal{D}(G)$ corresponding to that dominating set
is denoted by the lowercase letter; for example, if $S$ is a dominating set in
$G$ of cardinality at most $k$, then $s$ is the vertex in $\mathcal{D}_{k}(G)$
corresponding to set $S$. If vertex $x$ is adjacent to vertex $y$, then we say
$x$ dominates $y$ (and vice versa). Similarly, if every vertex in set $T$ has
a neighbour in set $S$, then we say that set $S$ dominates $T$. Finally, we
use the notation $[n]$ to denote the set $\\{1,\dots,n\\}$. Any undefined
terms can be found in [13].

##  2 Eulerian dominating graphs

In this section, we consider dominating graphs: there is no restriction on the
cardinalities of dominating sets in seed graphs. We begin by stating a useful
(unpublished) result due to Brouwer, Csorba, and Schrijver [4].

######  Theorem 3.

[4] The number of dominating sets of a finite graph is odd.

A proof of Theorem 3 was in [1] and it is important to note that the result
holds for any finite graph, not simply connected graphs. Theorem 3 and the
Handshaking Lemma111The Handshaking Lemma [13] states that a graph cannot have
an odd number of vertices of odd degree. imply that every dominating graph has
at least one vertex of even degree.

For a disconnected graph $G$, every dominating set of $G$ is the union of
dominating sets of its components. Consequently, the Cartesian product of the
dominating graphs of the components precisely describes the structure of
$\mathcal{D}(G)$, as stated in Observation 4. The Cartesian product of graphs
$H$ and $H^{\prime}$, denoted $H\hskip 1.42262pt\square\hskip
1.42262ptH^{\prime}$ is the graph with vertex set $V(H)\hskip
1.42262pt\square\hskip 1.42262ptV(H^{\prime})$. Vertices $(u,v)$ and $(x,y)$
in $H\hskip 1.42262pt\square\hskip 1.42262ptH^{\prime}$ are adjacent if and
only if $u=x$ and $v$ is adjacent to $y$ in $H^{\prime}$; or $v=y$ and $u$ is
adjacent to $x$ in $H$.

######  Observation 4.

Let $G$ be a graph with exactly $m$ components $G_{1},\dots,G_{m}$. Then

$\mathcal{D}(G_{1})~{}\square~{}\mathcal{D}(G_{2})~{}\square~{}\cdots~{}\square~{}\mathcal{D}(G_{m})\cong\mathcal{D}(G).$

Given a seed graph $G$ with $m$ components $G_{1},\dots,G_{m}$, Observation 4
implies that $\mathcal{D}(G)$ is Eulerian if and only $\mathcal{D}(G_{i})$ is
Eulerian for each $i\in[m]$. To see this, for each $i\in[m]$, let $X_{i}$ be
an arbitrary dominating set of the subgraph of $G$ induced by the vertices of
$G_{i}$. If $\mathcal{D}(G_{i})$ is Eulerian for all $i\in[m]$, then

$\deg_{\mathcal{D}(G)}\big{(}(x_{1},\dots,x_{m})\big{)}=\deg_{\mathcal{D}(G_{1})\square\cdots\square\mathcal{D}(G_{m})}\big{(}(x_{1},\dots,x_{m})\big{)}=\sum_{i=1}^{m}\deg_{\mathcal{D}(G_{i})}(x_{i})$

is even and thus $\mathcal{D}(G)$ is Eulerian. Conversely, suppose
$\mathcal{D}(G)$ is Eulerian and, without loss of generality,
$\mathcal{D}(G_{1})$ is not Eulerian. Then there exists a vertex $x_{1}$ with
odd degree in $\mathcal{D}(G_{1})$. As noted above, the dominating graph of a
connected seed graph contains at least one vertex of even degree. So for every
$i\in\\{2,\dots,m\\}$ there exists a vertex $y_{i}$ with even degree in
$\mathcal{D}(G_{i})$. By Observation 4, the degree of
$(x_{1},y_{2},y_{3},\dots,y_{m})$ in $\mathcal{D}(G)$ is odd, which yields a
contradiction. Thus, Corollary 5 follows.

######  Corollary 5.

Let $G$ be a graph with exactly $m$ components $G_{1},\dots,G_{m}$. Then
$\mathcal{D}(G)$ is Eulerian if and only if $\mathcal{D}(G_{i})$ is Eulerian
for all $i\in[n]$.

A consequence of Corollary 5 is that to complete the characterization of seed
graphs $G$ for which $\mathcal{D}(G)$ is Eulerian, we need only consider
connected seed graphs. A graph with only one vertex has exactly one dominating
set and is therefore trivially Eulerian; thus, the remaining results of this
section consider connected seed graphs with at least two vertices.

######  Lemma 6.

Let $G$ be a connected graph on $n\geq 2$ vertices. If for some
$\ell\in[n-1]$,

  1. 1.

there is a set of cardinality $\ell$ that dominates $G$,

  2. 2.

there is a set of cardinality $\ell$ that does not dominate $G$, and

  3. 3.

every set of cardinality $\ell+1$ dominates $G$;

then $\mathcal{D}(G)$ has at least one vertex of even degree and at least one
vertex of odd degree.

###### Proof.

For a contradiction, suppose 1., 2., and 3. hold, but the vertex degrees in
$\mathcal{D}(G)$ are all of the same parity. Since $G$ is connected and
$\ell<n$, the vertex in $\mathcal{D}(G)$ corresponding to the dominating set
that contains all vertices of $G$, will have degree $n$; and the claim
follows:

Claim: Every vertex degree in $\mathcal{D}(G)$ has the same parity as $n$.

By 2., let $A\subset V(G)$ be a set of cardinality $\ell$ that does not
dominate $G$. Consequently, there exists $x\in V(G)$ that is not adjacent to
any vertex in $A$. By 3., $A\cup\\{x\\}$ dominates $G$, so let
$B=V(G)\backslash(A\cup\\{x\\})$. Observe that $B\neq\emptyset$; otherwise $x$
is an isolated vertex in $G$. By 3., $A\cup\\{v\\}$ dominates $G$ for each
$v\in B$. Since $A$ does not dominate $x$, this implies $x$ must be adjacent
to every vertex in $B$.

Let $I(A)$ denote the set of vertices of $A$ that have no neighbour in $A$. If
a vertex (other than $x$) is removed from $A\cup\\{x\\}$, then whether the
remaining vertices dominate $G$ depend entirely on whether the removed vertex
has a neighbour in $A$ or not; i.e. whether or not the removed vertex is in
$I(A)$. We next show that $I(A)\neq\emptyset$ and then to complete the proof,
consider two cases: $|I(A)|=1$ and $|I(A)|\geq 2$.

Suppose $I(A)=\emptyset$. This implies that $A\backslash\\{a\\}$ dominates $A$
for all $a\in A$. Consequently, $(A\cup\\{x\\})\backslash\\{a\\}$ dominates
$G$ for all $a\in A$. Additionally, $(A\cup\\{x\\})\cup\\{v\\}$ dominates $G$
for all $v\in B$. Therefore, the vertex of $\mathcal{D}(G)$ corresponding to
dominating set $A\cup\\{x\\}$ therefore has degree $n-1$ in $\mathcal{D}(G)$,
which contradicts the claim. Thus, $I(A)$ is non-empty; let $a\in I(A)$. By
3., $(A\cup\\{x,v\\})\backslash\\{a\\}$ dominates $G$ for every $v\in B$.
Since $v\in B$ is arbitrary, this implies every vertex in $I(A)$ must be
adjacent to every vertex in $B$; see Figure 2 where the dotted line represents
non-adjacency.

Figure 2: A visualization of some of the adjacencies (and non-adjacencies) in
$G$.

Case 1. Suppose $I(A)=\\{a\\}$. If $A\backslash\\{a\\}=\emptyset$ then
$A=\\{a\\}$ and so $\ell=1$. Then by 1., there exists some vertex $y\in V(G)$
that dominates $G$. However, the vertex in $\mathcal{D}(G)$, corresponding to
dominating set $\\{y\\}$, has degree $n-1$, which contradicts the claim. Thus,
$|A\backslash\\{a\\}|\geq 1$. Let $c$ be a vertex in $B$ that has a neighbour
in $A\backslash\\{a\\}$. (Such a vertex necessarily exists; otherwise $G$ is
disconnected.) By 3., $A\cup\\{c\\}$ has cardinality $\ell+1$ and dominates
$G$. We list the subsets of $A\cup\\{c\\}$, of cardinality $\ell$:

  * •

$A$ – this set does not dominate $G$ by assumption;

  * •

$(A\cup\\{c\\})\backslash\\{a^{\prime}\\}$ for each $a^{\prime}\in
A\backslash\\{a\\}$ – this set dominates $G$ because $a$ dominates $B$, $c$
dominates $x$, and $A\backslash\\{a^{\prime}\\}$ dominates $A$;

  * •

$(A\cup\\{c\\})\backslash\\{a\\}$.

Observe that $(A\cup\\{c\\})\backslash\\{a\\}$ must not dominate $G$;
otherwise there is a vertex of degree $n-1$ in $\mathcal{D}(G)$, which
contradicts the claim. Since $(A\cup\\{c\\})\backslash\\{a\\}$ does not
dominate $G$, Property 1.a. must hold:

Property 1.a. $\exists c^{\prime}\in B$ ($c^{\prime}\neq c$) such that
$c^{\prime}$ has no neighbour in $(A\cup\\{c\\})\backslash\\{a\\}$.

By considering the subsets of $A\cup\\{c^{\prime}\\}$ of cardinality $\ell$,
we similarly conclude $(A\cup\\{c^{\prime}\\})\backslash\\{a\\}$ must not
dominate $G$. However, as $c$ has a neighbour in $A\backslash\\{a\\}$, this
implies Property 1.b.:

Property 1.b. $\exists c^{\prime\prime}\in B$ ($c^{\prime\prime}\neq
c^{\prime}$) such that $c^{\prime\prime}$ has no neighbour in
$(A\cup\\{c^{\prime}\\})\backslash\\{a\\}$.

Since $(A\cup\\{c,c^{\prime\prime}\\})\backslash\\{a\\}$ has cardinality
$\ell+1$, it dominates $G$, which tells us that $c^{\prime}$ has a neighbour
in $(A\cup\\{c,c^{\prime\prime}\\})\backslash\\{a\\}$, which contradicts
Property 1.a. and Property 1.b. Thus, $|I(A)|\neq 1$.

Case 2. Suppose $|I(A)|\geq 2$. For a pair $a\in I(A)$ and $v\in B$, we list
the subsets of $(A\cup\\{x,v\\})\backslash\\{a\\}$ of cardinality $\ell$:

  * •

$(A\cup\\{x\\})\backslash\\{a\\}$ – this set does not dominate $G$ because
$a\in I(A)$ is not dominated;

  * •

$(A\cup\\{v\\})\backslash\\{a\\}$ – this set dominates $G$ because
$a^{\prime}\in I(A)\backslash\\{a\\}$ dominates $B$, $A\backslash\\{a\\}$
dominates itself, and $v$ dominates $x$ and $a$;

  * •

$(A\cup\\{x,v\\})\backslash\\{a,a^{\prime}\\}$ – this set dominates $G$ for
any $a^{\prime}\in I(A)\backslash\\{a\\}$ because $v$ dominates
$\\{a,a^{\prime}\\}$, $x$ dominates $B$, and $A\backslash\\{a,a^{\prime}\\}$
dominates itself;

  * •

$(A\cup\\{x,v\\})\backslash\\{a,a^{*}\\}$ dominates $G$ for any $a^{*}\in
A\backslash I(A)$ because $x$ dominates $B$, $v$ dominates $a$, and
$A\backslash\\{a,a^{*}\\}$ dominates $A\backslash\\{a\\}$.

Consequently, the degree of the vertex in $\mathcal{D}(G)$, corresponding to
dominating set $(A\cup\\{x,v\\})\backslash\\{a\\}$, is $\ell+n-(\ell+1)=n-1$,
which contradicts the claim.∎

For a connected graph $G$ on $n$ vertices, every set of cardinality $n-1$
dominates $G$. Thus, there exists a minimum positive integer $\ell+1$ such
that every set of cardinality $\ell+1$ dominates $G$. Consequently, either no
set of cardinality $\ell$ dominates $G$ or the conditions of Lemma 6 are
satisfied. In the latter case, $\mathcal{D}(G)$ is not Eulerian by Lemma 6.
Thus, if $\mathcal{D}(G)$ is Eulerian, then there is a minimum positive
integer $\ell+1$ such that every set of cardinality $\ell+1$ dominates $G$ and
no set of cardinality $\ell$ dominates $G$. We use this implication in Theorem
7, to characterize the connected graphs $G$, for which $\mathcal{D}(G)$ is
Eulerian.

A perfect matching in a graph $G$ is a subset $M$ of edges of $G$ such that
every vertex in $V(G)$ is adjacent to exactly one edge in $M$. For an even
integer $n\geq 4$, the cocktail party graph on $n$ vertices222The graph
represents the handshakes that occur if $n$ couples shake hands with everyone
but their partner at a cocktail party. is the graph obtained by removing a
perfect matching from the complete graph $K_{n}$ [12]. It is also the Turán
graph $T(n,n/2)$. The Turán graph $T(n,r)$ is a complete multipartite graph
formed by partitioning $n$ vertices into $r$ subsets, with cardinalities as
equal as possible, with two vertices adjacent if and only they belong to
different subsets.

######  Theorem 7.

For a connected graph $G$ on at least two vertices, $\mathcal{D}(G)$ is
Eulerian if and only if $G$ is the cocktail party graph on $n\geq 4$ vertices.

###### Proof.

First we consider, all connected graphs on $2$ and $3$ vertices; that is
$P_{2}$, $P_{3}$, $C_{3}$ and prove their dominating graphs are not Eulerian.
Since a single vertex dominates $P_{2}$ and the addition of the other vertex
will result in a dominating set, the dominating set of cardinality $1$
corresponds to a vertex of degree $1$ in $\mathcal{D}(P_{2})$. The dominating
set of cardinality $3$ in $P_{3}$ and $C_{3}$ corresponds to a vertex of
degree $3$ in the dominating graph because every pair of vertices dominates
$P_{3}$ and $C_{3}$. Thererfore, no connected graph on $2$ or $3$ vertices has
an Eulerian dominating graph.

Let $H_{n}$ denote the cocktail party graph on $n\geq 4$ vertices. Any two
vertices dominate $H_{n}$, but no single vertex dominates $H_{n}$.
Consequently, each vertex in $\mathcal{D}(H_{n})$ corresponds to a subset of
$V(H_{n})$ of cardinality at least two. Let $T$ be an $r$-element subset of
$V(H_{n})$ for some $r\in\\{2,\dots,n\\}$. If $r>2$, we can delete a vertex
from $T$ and the remaining vertices of $T$ will still dominate $H_{n}$. If
$r<n$, we can add any of the $n-r$ vertices from $V(H_{n})\backslash T$ to $T$
and form a new dominating set of $H_{n}$. Thus, $t\in V(\mathcal{D}(H_{n}))$
will have degree $r+(n-r)=n$ if $2<r<n$. Furthermore, $t$ has degree $n-2$ if
$r=2$ and degree $n$ if $r=n$. Since $n$ is even, every vertex in
$\mathcal{D}(H_{n})$ has even degree, and so $\mathcal{D}(H_{n})$ is Eulerian.

For the other direction, let $G$ be a connected graph on $n\geq 4$ vertices
with $\mathcal{D}(G)$ Eulerian. Since $S=V(G)$ dominates $G$, $s\in
V(\mathcal{D}(G))$ has degree $n$, which implies $n$ is even. Let $\ell$ be
the smallest positive integer such that every set of cardinality $\ell+1$
dominates $G$. Note that $\ell$ necessarily exists because every set of
cardinality $n-1$ (and the single set of cardinality $n$) dominates connected
graph $G$. Then either

  1. 1.

no set of cardinality $\ell$ dominates $G$; or

  2. 2.

there is a set of cardinality $\ell$ that dominates $G$ and there is a set of
cardinality $\ell$ that does not dominate $G$.

We first note that 2. cannot occur. Otherwise, by Lemma 6, $\mathcal{D}(G)$
has a vertex of odd degree, which contradicts the assumption that
$\mathcal{D}(G)$ is Eulerian. Suppose 1. holds. Then each vertex in
$\mathcal{D}(G)$ that corresponds to a dominating set of cardinality $\ell+1$,
has degree $n-(\ell+1)$. Since $\mathcal{D}(G)$ is Eulerian and $n$ is even,
this forces $\ell$ to be odd. If $\ell=1$ then $G$ has no universal vertex,
but every $2$-element subset of $V(G)$ dominates $G$. In this case, $G$ is the
cocktail party graph.

Suppose $\ell\geq 3$ and let $S\subset V(G)$ be of cardinality $\ell$. Since
$S$ does not dominate $G$, $\exists~{}x\in V(G)$ that is not adjacent to any
vertex in $S$. However, as every set of cardinality $\ell+1$ dominates $G$,
$x$ must be adjacent to every vertex in $T=V(G)\backslash(S\cup\\{x\\})$.
Since $\ell+1\leq n-1$, we know $n-(\ell+1)\geq 1$ and therefore
$T\neq\emptyset$. For any $u\in S$, $(S\cup\\{x\\})\backslash\\{u\\}$ has
cardinality $\ell$ and therefore is not a dominating set of $G$. Since $x$ is
adjacent to every vertex in $T$, this implies $u$ has no neighbour in
$S\cup\\{x\\}$. Since $u$ is an arbitrary vertex in $S$, this implies the
subgraph of $G$, induced by $S\cup\\{x\\}$, is an independent set.

Finally, observe that for any $u\in S$ and $v\in T$,
$(S\cup\\{x,v\\})\backslash\\{u\\}$ has cardinality $\ell+1$ and is therefore
a dominating set of $G$. Since the subgraph induced by $S\cup\\{x\\}$ is an
independent set, every vertex in $S$ must be adjacent to every vertex in $T$;
otherwise $u$ is not dominated by $(S\cup\\{x,v\\})\backslash\\{u\\}$.
Consequently, for any $v\in T$, the set $\\{x,v\\}$ dominates $G$. This
contradicts the earlier assumption that $\ell\geq 3$.

Thus, $\ell=1$ and is therefore the cocktail party graph.∎

##  3 Eulerian $k$-dominating graphs

In Section 2, we characterized those graphs $G$ for which $\mathcal{D}(G)$ is
Eulerian. In this section, we consider $k<|V(G)|$ and determine, for a variety
of classes of graph $G$, the necessary and sufficient conditions on $k$ and
$|V(G)|$ for $\mathcal{D}_{k}(G)$ to be Eulerian. For a graph $G$, if
$k=\gamma(G)$, then $\mathcal{D}_{k}(G)$ is simply a set of isolated vertices,
each trivially Eulerian. For this reason, and the fact that
$\mathcal{D}_{k}(G)\cong\mathcal{D}(G)$ when $k=|V(G)|$, we assume
$\gamma(G)<k<|V(G)|$ throughout this section. We begin by considering two
simple graph classes: paths and cycles. From [6], $\gamma(P_{n})=\lceil
n/3\rceil$ for $n\geq 1$ and $\gamma(C_{n})=\lceil n/3\rceil$ for $n\geq 3$.

######  Theorem 8.

Let $n$ and $k$ be integers such that $n\geq 3$ and $\lceil n/3\rceil<k<n$.
Then

  * •

$\mathcal{D}_{k}(P_{n})$ is Eulerian if and only if $n=4$ and $k=3$; and

  * •

$\mathcal{D}_{k}(C_{n})$ is Eulerian if and only if either $n=7$ and $k=4$, or
$n=3$ and $k=2$.

###### Proof.

Vertices in $\mathcal{D}_{k}(P_{n})$ and $\mathcal{D}_{k}(C_{n})$ that
correspond to minimum dominating sets in $P_{n}$ and $C_{n}$, have degree
$(n-\lceil n/3\rceil)$, which is odd when $n\equiv 2$ (mod $3$). Thus, neither
$\mathcal{D}_{k}(P_{n})$ nor $\mathcal{D}_{k}(C_{n})$ is Eulerian when
$n\equiv 2$ (mod $3$).

Let $n=3\ell+j$ for some integers $\ell,j$ such that $\ell\geq 3$ and
$j\in\\{0,1\\}$. We will consider cases $\ell=1$ and $\ell=2$ at the end. Let
$P_{n}=(v_{0},v_{1},\dots,v_{n-1})$ and $C_{n}=(v_{0},v_{1},\dots,v_{n-1})$,
with adjacencies modulo $n$ for $C_{n}$. Let

$S=\Big{\\{}v_{3i+1}:0\leq
i\leq\lceil(n-4)/3\rceil\Big{\\}}\cup\begin{cases}\emptyset&\text{ if $n\equiv
0$ (mod $3$)}\\\ \\{v_{n-2}\\}&\text{ if $n\equiv 1$ (mod $3$).}\end{cases}$

as highlighted in Figure 3 (a) for $n\equiv 0$ (mod $3$) and (b) for $n\equiv
1$ (mod $3$). Observe that $S$ is a minimum dominating set on both $P_{n}$ and
$C_{n}$. Let $S^{\prime}=S\cup\\{v_{3}\\}$. If $k=\lceil n/3\rceil+1$, then
$s^{\prime}$ has degree $1$ in both $\mathcal{D}_{k}(P_{n})$ and
$\mathcal{D}_{k}(C_{n})$ as $v_{3}$ is the only vertex of $S^{\prime}$ whose
removal yields a dominating set. Therefore, neither $\mathcal{D}_{k}(P_{n})$
nor $\mathcal{D}_{k}(C_{n})$ is Eulerian when $k=\lceil n/3\rceil+1$. Let
$S^{\prime\prime}=(S\backslash\\{v_{4}\\})\cup\\{v_{3},v_{5}\\}$ and note that
$S^{\prime\prime}$ is a minimal dominating set in both $P_{n}$ and $C_{n}$. If
$k>\lceil n/3\rceil+1$, then $s^{\prime\prime}$ has degree $(n-\lceil
n/3\rceil-1)$ in both $\mathcal{D}_{k}(P_{n})$ and $\mathcal{D}_{k}(C_{n})$.
The quantity $(n-\lceil n/3\rceil-1)$ is odd when $n\equiv 0,1$ (mod $3$).
Therefore, neither $\mathcal{D}_{k}(P_{n})$ nor $\mathcal{D}_{k}(C_{n})$ is
Eulerian for $k>\lceil n/3\rceil$.

Figure 3: Dominating sets on paths and cycles with $n\equiv 0,1$ (mod $3$).

It remains to consider the cases where $n\equiv 0,1$ (mod $3$) and
$\ell\in\\{1,2\\}$; that is $n\in\\{3,4,6,7\\}$. Every vertex in
$\mathcal{D}_{2}(C_{3})$ has degree two: removing one of the two vertices in a
dominating set of $C_{3}$ of cardinality two results in a dominating set;
adding one of the two vertices not in a dominating set of cardinality one
results in a dominating set. However, $\mathcal{D}_{2}(P_{3})$ is not Eulerian
as the dominating set $\\{v_{0},v_{1}\\}$ corresponds to a vertex of degree
$1$ in $\mathcal{D}_{2}(P_{3})$. From Figure 1, we see
$\mathcal{D}_{3}(P_{4})$ is Eulerian. However, $\mathcal{D}_{3}(C_{4})$ is not
Eulerian: the dominating set $\\{v_{0},v_{1},v_{2}\\}$ corresponds to a vertex
of degree $3$ in $\mathcal{D}_{3}(C_{4})$ as the removal of any vertex from
the set leaves a dominating set. We note that sets
$S,S^{\prime},S^{\prime\prime}$ and argument from the previous paragraph can
be applied to both $P_{6}$ and $C_{6}$ in order to conclude that
$\mathcal{D}_{k}(P_{6})$ and $\mathcal{D}_{k}(C_{6})$ are not Eulerian for
$k>\lceil 6/3\rceil=2$.

Finally, for $n=7$, let $S_{7}$ denote the dominating set in Figure 4 (a).
Note that $S_{7}\backslash\\{v_{3}\\}$ and $S_{7}\backslash\\{v_{4}\\}$ are
dominating sets. If $k\in\\{5,6\\}$, then adding one of three vertices to
$S_{7}$ forms a dominating set. Thus $s_{7}$ has degree $5$ in
$\mathcal{D}_{k}(P_{n})$ and $\mathcal{D}_{k}(C_{n})$. Consider the dominating
set of $P_{7}$ in Figure 4 (b). The corresponding vertex in
$\mathcal{D}_{4}(P_{7})$ has degree $1$ because the only vertex that can be
removed from the set and leave a dominating set is $v_{0}$. To conclude the
proof, it remains to show that $\mathcal{D}_{4}(C_{7})$ is Eulerian.

Every dominating set of cardinality $3$ in $C_{7}$ is minimal and therefore
corresponds to a vertex of degree $4$ in $\mathcal{D}_{4}(C_{7})$ (as any one
of $4$ vertices can be added to the set). Every dominating set of cardinality
$4$ contains at least $2$ adjacent vertices. Let $\mathcal{S}$ denote the
collection of dominating sets of $C_{7}$ with cardinality $4$ that contain
$v_{0}$ and $v_{1}$. Each set in $\mathcal{S}$ contains an additional two of
the remaining $5$ vertices. Up to a relabelling of vertices, there are three
sets in $\mathcal{S}$; these are highlighted in Figure 5. By inspection, we
see that for each set in $\mathcal{S}$, one of two vertices can be removed to
leave a dominating set, thus, each dominating set in $\mathcal{S}$ corresponds
to a vertex of degree two in $\mathcal{D}_{4}(C_{7})$. ∎

Figure 4: Dominating sets on $P_{7}$. Figure 5: Sets of cardinality $4$ on
$C_{7}$ that contain $v_{0}$ and $v_{1}$.

We next characterize the complete bipartite graphs whose $k$-dominating graphs
are Eulerian.

######  Theorem 9.

Let $m$, $n$, and $k$ be integers such that $m\leq n$ and
$\gamma(K_{m,n})<k<m+n$. Then $\mathcal{D}_{k}(K_{m,n})$ is Eulerian if and
only if

  * •

$m=1$, $n$ is even, and $k$ is odd; or

  * •

$m\geq 3$, $m\equiv n$ (mod $2$), and $k=3$.

###### Proof.

Label the vertices in the partite sets of $K_{m,n}$ as
$X=\\{x_{1},\dots,x_{m}\\}$ and $Y=\\{y_{1},\dots,y_{n}\\}$. First, suppose
$m=1$. Let $A$ be a dominating set with cardinality $|A|<n-1$; this implies
$x_{1}\in A$. The addition of any vertex in $Y\backslash A$ to $A$; or the
removal of any vertex from $Y\cap A$ from $A$ yields a dominating set. Thus,
if $k>|A|$, vertex $a$ has degreee $n$ in $\mathcal{D}_{k}(K_{1,n})$ and if
$k=|A|$, vertex $a$ has degree $(|A|-1)=k-1$ in $\mathcal{D}_{k}(K_{1,n})$.
Consequently, $\mathcal{D}_{k}(K_{1,n})$ is Eulerian precisely when $n$ is
even and $k$ is odd.

Second, suppose $m=2$. As $K_{2,2}\cong C_{4}$, by Theorem 10,
$\mathcal{D}_{k}(K_{2,2})$ is not Eulerian. Thus, we assume $n>m=2$;
consequently, $k\geq 3$. Let $S=\\{x_{1},x_{2},y_{1}\\}$ and observe that the
removal of any vertex from $S$ yields a dominating set. So if $k=3$, $s$ has
degree $3$ in $\mathcal{D}_{3}(K_{2,n})$, which is therefore not Eulerian. For
$k\geq 4$, let $T=\\{x_{1},y_{1},y_{2}\\}$. Then $t$ has degree $n+1$ (from
$T$: add $x_{2}$, remove one of $y_{1},y_{2}$, or add a vertex from
$Y\backslash\\{y_{1},y_{2}\\}$). Dominating set $\\{x_{1},x_{2}\\}$
corresponds to a vertex of degree $n$ in $\mathcal{D}_{k}(K_{2,n})$, so
$\mathcal{D}_{k}(K_{2,n})$ has vertices of both degree $n-1$ and $n$ when
$k\geq 4$. Thus $\mathcal{D}_{k}(K_{2,n})$ is not Eulerian for $n\geq m=2$ and
$\gamma(K_{2,n})<k<m+n$.

Third, suppose $n\geq m\geq 3$. Dominating set $\\{x_{1},y_{1}\\}$ corresponds
to a vertex of degree $m+n-2$ in $\mathcal{D}_{k}(K_{m,n})$. As a result, for
$\mathcal{D}_{k}(K_{m,n})$ to be Eulerian, $m$ and $n$ must be of the same
parity. If $k>3$, consider $T=\\{x_{1},x_{2},y_{1}\\}$. Then $t$ has degree
$m+n-1$ in $\mathcal{D}_{k}(K_{m,n})$: we can add one of $(m-2)+(n-1)$
vertices to $T$ or remove one of $x_{1},x_{2}$ from $T$ and the resulting set
is a dominating set. Thus, $\mathcal{D}_{k}(K_{m,n})$ is not Eulerian for
$n\geq m\geq 3$ and $k>3$. Assume $k=3$ and let $A$ be a dominating set of
$K_{m,n}$ that contains, without loss of generality, two vertices of $X$ and
one vertex of $Y$. Then $a$ has degree $2$ in $\mathcal{D}_{3}(K_{m,n})$
because one vertex of $A\cap X$ can be removed from $A$ to yield a dominating
set, but the removal of the vertex $A\cap Y$ from $A$ does not yield a
dominating set. If $n>m=3$, the dominating set $\\{x_{1},x_{2},x_{3}\\}$
corresponds to an isolated vertex in $\mathcal{D}_{3}(K_{3,n})$ (which is a
trivially Eulerian component). Similarly, if $n=m=3$, dominating set
$\\{y_{1},y_{2},y_{3}\\}$ corresponds to an isolated vertex in
$\mathcal{D}_{3}(K_{3,3})$. Thus $\mathcal{D}_{3}(K_{m,n})$ is Eulerian
provided $m$ and $n$ are of the same parity and $n\geq m\geq 3$.∎

Motivated by the fact that the dominating graph of a cocktail party graph is
Eulerian, we next consider $k$-dominating graphs of cocktail party graphs.

######  Theorem 10.

Let $H_{n}$ be the cocktail party graph on $n\geq 4$ vertices. For any integer
$k$ such that $2<k<n$, $\mathcal{D}_{k}(H_{n})$ is Eulerian if and only if $k$
is even.

###### Proof.

Let $\mathcal{S}$ be the collection of $p$-element subsets of $V(H_{n})$ for
$p\in\\{2,\dots,k\\}$. Since every pair of vertices dominate $H_{n}$, but no
single vertex dominates $H_{n}$, the elements of $\mathcal{S}$ are precisely
the dominating sets of $H_{n}$. Let $S$ be an arbitrarily element of
$\mathcal{S}$; then $s$ is the vertex in $\mathcal{D}_{k}(H_{n})$
corresponding to set $S$.

If $p=2$, then $s$ has degree $n-2$ as any vertex of $V(H_{n})\backslash S$
can be added to $S$. If $p\in\\{3,\dots,k-1\\}$, then $s$ has degree $n$
because every subset of cardinality $p-1$ dominates $H_{n}$ and, adding one of
the $n-p$ vertices of $V(H_{n})\backslash S$ to $S$ will form a dominating set
of cardinality $p+1\leq k$. Finally, if $p=k$, every subset of $S$ with
cardinality $p-1$ dominates $H_{n}$ and so $s$ has degree $p=k$. Thus,
$\mathcal{D}_{k}(H_{n})$ is Eulerian if and only if $k$ is even. ∎

For the cocktail party graph $H_{n}$, every set of cardinality $\gamma(H_{n})$
dominates $H_{n}$. This motivates us to consider complete graphs, $K_{n}$, as
they have the same property: every set of cardinality $\gamma(K_{n})$
dominates $K_{n}$. For $n\geq 1$ and $k\geq 2$, certainly
$\mathcal{D}_{k}(K_{n})$ is not Eulerian when $n$ is even; otherwise the
vertex in $\mathcal{D}_{k}(K_{n})$ corresponding to a dominating set of
cardinality $1$ has degree $n-1$, which is odd. If $n$ is odd and $k>2$ the
vertex in $\mathcal{D}_{k}(K_{n})$, corresponding to a dominating set of
cardinality $2$, has degree $n$, which is odd. Finally, for odd $n$,
$\mathcal{D}_{2}(K_{n})$ contains only vertices of degree $2$ and $n-1$ and
hence, is Eulerian.

######  Observation 11.

Let $n$ and $k$ be integers such that $n\geq 2$ and $1<k<n$. Then
$\mathcal{D}_{k}(K_{n})$ is Eulerian if and only if $n$ is odd and $k=2$.

######  Corollary 12.

Let $G$ be a connected graph on $n>1$ vertices with the property that every
set of cardinality $\gamma(G)$ dominates $G$. For integer $k$ such that
$\gamma(G)<k<n$, $\mathcal{D}_{k}(G)$ is Eulerian if and only if

  1. 1.

$G$ is a complete graph on $n>1$ vertices where $n$ is odd and $k=2$; or

  2. 2.

$G$ is a cocktail party graph on $n\geq 4$ vertices and $k$ is even.

###### Proof.

Let $G$ be a connected graph on $n>1$ vertices with the property that every
set of cardinality $\gamma(G)$ dominates $G$. If $\gamma(G)=1$, then 1.
follows from Observation 11. If $\gamma(G)=2$, then $G$ must be the cocktail
party graph on $n>4$ vertices and 2. follows from Theorem 10.

Suppose $\gamma(G)\geq 3$ and let $A$ be a set of cardinality $\gamma(G)-1\geq
2$ that does not dominate $x$. If $A=V(G)\backslash\\{x\\}$ then $G$ is
disconnected, so $V(G)\backslash(A\cup\\{x\\})$ must be nonempty. Since
$A\cup\\{x\\}$ and $A\cup\\{v\\}$ for any $v\in B$, have cardinality
$\gamma(G)$, they dominate $G$. Consequently, $x$ must be adjacent to every
vertex in $B$. However, since $(A\cup\\{x\\})\backslash\\{a\\}$ has
cardinality $\gamma(G)-1$, it does not dominate $G$ for any $a\in A$. In
particular, $A\backslash\\{a\\}$ does not dominate $a$ (for any $a\in A$), and
we conclude the vertices of $A$ form an independent set.

For all $a\in A$, $v\in B$, set $(A\cup\\{v,x\\})\backslash\\{a\\}$ dominates
$G$ since it has cardinality $\gamma(G)$. This implies every vertex in $A$ is
adjacent to every vertex in $B$. Observe however, that
$A\cup\\{v\\}\backslash\\{a\\}$ dominates $G$ for any $a\in A,v\in B$, because
$A\backslash\\{a\\}$ is nonempty and dominates $(A\backslash\\{a\\})\cup B$;
while $v$ dominates $\\{x,a\\}$. This yields a contradiction as
$|A\cup\\{v\\}\backslash\\{a\\}|=\gamma(G)-1$.∎

The upper domination number of a graph $G$, denoted $\Gamma(G)$, is the
maximum cardinality of a minimal dominating set in $G$. In both complete
graphs and cocktail party graphs, the domination number equals the upper
domination number. These are examples of well-dominated graphs. Well-dominated
graphs were introduced in [5] where they define a graph $G$ to be well-
dominated if $\gamma(G)=\Gamma(G)$. The reader may also note that the paths
and cycles with Eulerian $k$-dominating graphs, described in Theorem 8 are
also well-dominated seed graphs. As pointed out in [3], it is easy to show
that the corona of any graph is well-dominated. The corona of graph $G$,
denoted by $G\circ K_{1}$ is the graph formed by adding a single new vertex of
degree one, adjacent to each vertex of $G$. A vertex of degree one is called a
pendant vertex and an edge incident with a pendant vertex is called a pendant
edge. We first note that if $G$ is a graph on $n>1$ vertices, then
$\gamma(G\circ K_{1})=\Gamma(G\circ K_{1})=n$: every minimal dominating set
must contain exactly one endpoint of each pendant edge.

######  Theorem 13.

Let $G$ be a graph on $n>1$ vertices and $k$ be an integer for which $n<k<2n$.
Then $\mathcal{D}_{k}(G\circ K_{1})$ is Eulerian if and only if $n$ is even
and $k=n+1$.

###### Proof.

Let $G$ be a graph on $n>1$ vertices. Let $S$ be a minimum dominating set on
$G\circ K_{1}$. For $k>n$, the degree of $s$ in $\mathcal{D}_{k}(G\circ
K_{1})$ is $|V(G\circ K_{1})|-|S|=n$. Thus, $s$ has even degree if and only if
$n$ is even.

Suppose $n$ is even and let $S^{\prime}=S\cup\\{v\\}$ for some $v\in V(G\circ
K_{1})\backslash S$. Since $S$ contains exactly one endpoint of each pendant
edge in $G\circ K_{1}$, $S^{\prime}$ contains both endpoints of exactly one
pendant edge $uv$ in $G\circ K_{1}$. Removing exactly one of $\\{u,v\\}$ from
$S^{\prime}$ yields a dominating set of $G\circ K_{1}$, but for $w\neq u$,
$w\neq v$, set $S^{\prime}\cup\\{v\\}\backslash\\{w\\}$ does not dominate
$G\circ K_{1}$. Thus, the degree of $s^{\prime}$ in $\mathcal{D}_{n+1}(G\circ
K_{1})$ is two; and for even $n$, $\mathcal{D}_{n+1}(G\circ K_{1})$ is
Eulerian. Note, however, that if $k>n+1$, vertex $s$ in
$\mathcal{D}_{k}(G\circ K_{1})$ will have degree $n+1$ since we can remove one
of $u,v$ from $S^{\prime}$ or add one of the other $n-1$ vertices to
$S^{\prime}$ and form a dominating set on $G\circ K_{1}$. Thus, if $k>n+1$,
$\mathcal{D}_{k}(G\circ K_{1})$ is not Eulerian.∎

It known from [5] that for a connected bipartite graph $G$; $G$ is well-
dominated if and only if $G\cong C_{4}$ or $G$ is the corona of a graph.
Combining this with Theorem 13 yields the following result.

######  Corollary 14.

Let $G$ be a bipartite, well-dominated graph on $n\geq 2$ vertices. Then
$\mathcal{D}_{k}(G)$ is Eulerian if and only if

  * •

$G\cong C_{4}$ and $k=3$; or

  * •

$G$ is the corona of a graph, $n\equiv 0$ (mod $4$), and $k=n/2+1$.

A complete characterization for well-dominated graphs with odd cycles has not
yet been found; see [3] for recent advances on well-dominated graphs
containing odd cycles. The cocktail party graphs (on at least $6$ vertices),
complete graphs, and $C_{7}$ are examples of well-dominated graphs that
contain odd cycles and have Eulerian $k$-dominating graphs (for particular
values of $k$).

######  Question 15.

Which well-dominated graphs contain an odd cycle and have an Eulerian
$k$-dominating graph?

To conclude, we restate Question 2 since it remains only partially answered.

Question 2. For which graphs $G$ and integers $k$, where $\gamma(G)<k<|V(G)|$,
is $\mathcal{D}_{k}(G)$ Eulerian?

##  4 Acknowledgements

M.E. Messinger acknowledges research support from NSERC (grant application
2018-04059). A. Porter acknowledges support from NSERC (USRA) and Mount
Allison University.

## References

  * [1] K. Adaricheva, C. Bozeman, N.E. Clarke, R. Haas, M.E. Messinger, K. Seyffarth and H. Smith, Reconfiguration graphs for dominating sets (2021). In: D. Ferrero, L. Hogben, S.R. Kingan and G.L. Matthews Eds., Research Trends in Graph Theory and Applications, Springer International Publishing, 119–135.
  * [2] K. Adaricheva, C. Bozeman, N.E. Clarke, R. Haas, M.E. Messinger, K. Seyffarth, H. Smith, Hamilton paths in dominating graphs of trees and cycles, Graphs and Combinatorics 38(6): 174 (2022).
  * [3] S.E. Anderson, K. Kuenzel, D.F. Rall, On well-dominated graphs, Graphs and Combinatorics 37 (2020) 151-165.
  * [4] A. Brouwer, P. Csorba, L. Schrijver, The number of dominating sets of a finite graph is odd, preprint (2009) https://www.win.tue.nl/~aeb/preprints/domin4a.pdf.
  * [5] A. Finbow, B. Hartnell, R. Nowakowski, Well-dominated graphs: a collection of well-covered ones, Ars Combinatoria 25-A (1988) 5-10.
  * [6] J.F. Fink, M.S. Jacobson, L.F. Kinch, J. Roberts, The bondage number of a graph, Discrete Mathematics 86 (1990) 47–57.
  * [7] R. Haas, K. Seyffarth, The $k$-dominating graph, Graphs and Combinatorics 30 (2014) 609-617.
  * [8] A.Haddadan, T.Ito, A.E.Mouawad, N.Nishimura, H.Ono, A.Suzuki, and Y. Tebbal. The complexity of dominating set reconfiguration, Theoretical Computer Science, 651 (2016) 37–49.
  * [9] C.M. Mynhardt, S. Nasserasr, Reconfiguration of colourings and dominating sets in graphs (2020). In: F. Chung, R. Graham, F. Hoffman, L. Hogben, R.C. Mullin and D.B. West, eds. 50 years of combinatorics, graph theory, and computing, Florida, CRC Press, 171–187.
  * [10] C.M. Mynhardt, A. Roux, L.E. Teshima, Connected $k$-dominating graphs, Discrete Mathematics 342 (2019) 145–151.
  * [11] N. Nishimura, Introduction to reconfiguration, Algorithms 11(4), 52, 2018.
  * [12] Weisstein, Eric W. “Cocktail Party Graph.” From MathWorld– A Wolfram Web Resource. https://mathworld.wolfram.com/CocktailPartyGraph.html.
  * [13] R.J. Wilson, Introduction to Graph Theory, 5th edition, Prentice Hall / Pearson, Hampshire, 2010.