# Temperature induced change in conformation of $\mathrm{Sc_{2}TbN@C_{80}}$ on
$h$-BN/Ni(111)

Roland Stania  Physik-Institut, Universität Zürich, CH-8057 Zürich,
Switzerland  Center for Artificial Low Dimensional Electronic Systems,
Institute for Basic Science, KR-37673 Pohang, South Korea  Ari Paavo Seitsonen
Département de Chimie, École Normale Supérieure, F-75005 Paris, France
Hyunjin Jung  Center for Artificial Low Dimensional Electronic Systems,
Institute for Basic Science, KR-37673 Pohang, South Korea  David Kunhardt
Leibniz Institute of Solid State and Materials Research, D-01069 Dresden,
Germany  Bernd Büchner  Leibniz Institute of Solid State and Materials
Research, D-01069 Dresden, Germany  Alexey A. Popov  Leibniz Institute of
Solid State and Materials Research, D-01069 Dresden, Germany  Matthias
Muntwiler  Paul Scherrer Institut, CH-5232 Villigen, Switzerland  Thomas
Greber  Physik-Institut, Universität Zürich, CH-8057 Zürich, Switzerland
<EMAIL_ADDRESS>
###### Abstract

The conformation of molecules on surfaces is decisive for their functionality.
In the case of the endofullerene paramagnet $\mathrm{Sc_{2}TbN@C_{80}}$ the
conformation is linked to an electric and a magnetic dipole moment. Therefore
a workfunction change of a substrate with such molecules on the surface
suggests the system to be magnetoelectric. Here one monolayer of
$\mathrm{Sc_{2}TbN@C_{80}}$ has been studied on $h$-BN/Ni(111). The molecules
assume a hexagonally close packed lattice aligned with the substrate high
symmetry directions. The structure is incommensurate and arranges at a
periodicity of $\approx$4.3$\times$4.3 substrate unit cells. At low
temperatures a C80 ($2\times 2$) superstructure is observed. Valence band
photoemission spectroscopy shows a temperature induced 0.3 eV shift on the C80
molecular orbitals to lower binding energies that is parallel to a
workfunction increase. From comparison of the molecular orbital angular
photoemission intensity distributions it is conjectured that the molecules
undergo a change in conformation between 30 and 300 K. This phase transition
is centred at 125 K as observed with high resolution x-ray photoelectron
spectroscopy that shows the core levels of the atomic species on the molecules
to shift parallel to the workfunction. The temperature dependence can be
described with a two level model that accounts for disordering with an
excitation energy of 74 meV into a high entropy ensemble. The experimental
findings are backed by density functional theory for the diamagnetic sibling
of $\mathrm{Sc_{2}TbN@C_{80}}$: Sc2YN@C80. The calculations rationalize the
incommensurate structure, indicate a permanent electric dipole moment of
Sc2YN@C80 and predict the room temperature N 1s x-ray photoelectron spectrum.

Endofullerenes, dielectric constant, density functional theory, x-ray
photoelectron spectroscopy

##  I Introduction

Fullerenes are archetypal molecular building blocks in nanoscience.
Correspondingly carbon shells like C60 have been studied in detail on surfaces
Rudolf  _et al._ (1999); Sánchez  _et al._ (2009); Moriarty (2010). Like found
in three dimensions Heiney  _et al._ (1991), the freezing of rotational
degrees of freedom also cause phase transitions in two-dimensional systems
Benning  _et al._ (1993); Goldoni  _et al._ (1996, 2002). A peculiar phase
transition of a monolayer of $\mathrm{C_{60}}$ on a single layer of $h$-BN on
Ni(111) showed a temperature dependent charge transfer onto $\mathrm{C_{60}}$
that is triggered by a change in conformation of the molecules with respect to
the substrate Muntwiler  _et al._ (2005). This pointed to non-adiabatic
effects that may be important for the engineering of electronic or spintronic
contacts at the nanometer scale.

Endohedral fullerenes are carbon cages that contain atoms Popov  _et al._
(2013). Species with a similar robustness as $\mathrm{C_{60}}$ Stevenson  _et
al._ (1999) open more opportunities for the exploitation of molecular
functionality such as single molecule magnetism Westerström  _et al._ (2012).
First surface science experiments focused on the electronic properties of
multilayer $\mathrm{C_{80}}$ endofullerenes Alvarez  _et al._ (2002); Shiozawa
_et al._ (2005), and soon monolayer systems were prepared and observed with
scanning probes Leigh  _et al._ (2007); Treier  _et al._ (2009); Huang  _et
al._ (2011); Krylov  _et al._ (2020). At low temperatures the orientation of
the endohedral unit is not random Treier  _et al._ (2009) and related to the
magnetisation Westerström  _et al._ (2015); Greber  _et al._ (2019); Krylov
_et al._ (2020). The orientation of the endohedral units may even be changed
by magnetic fields Kostanyan  _et al._ (2017). On the other hand, the
incomplete screening of the anisotropic electrostatic potential of the
endohedral cluster Stania  _et al._ (2018) bears a handle for accessing the
magnetisation of the endohedral clusters with electric fields.

Here we report on a phase transition of $\mathrm{Sc_{2}TbN@C_{80}}$ on
$h$-BN/Ni(111) around 125 K. It is related to the change in molecular
conformation which is reflected in a change of the angular dependence of the
photoemission from molecular orbitals and accompanied by a change of the
workfunction, as was the case for $\mathrm{C_{60}}$ on $h$-BN/Ni(111). In the
present transition, however, we find no charge transfer onto the molecule.
Instead, the orbital energies of $\mathrm{Sc_{2}TbN@C_{80}}$ shift parallel to
the workfunction i.e. they align with the vacuum level.

## Experimental and theoretical details

### Experimental

TbSc2N@C80 molecules with icosahedral $I_{h}$ symmetry of the carbon cage were
synthetized and purified as described in Ref. Zhang  _et al._ (2015) and
sublimated onto $h$-BN/Ni(111) Auwärter  _et al._ (1999), with the substrate
kept at 470 K. Like in the case of C60 Muntwiler  _et al._ (2005) this
substrate does bind the molecules weakly. The photoemission data were recorded
at a photon energy of 600 eV or He I$\alpha$ (21.2 eV) Muntwiler  _et al._
(2017). The coverage was determined with a layer by layer growth model, with
an electron mean free path of 1 nm and from the intensity ratio of the N 1s
core levels of the molecule and $h$-BN  Stania  _et al._ (2018). The low
energy electron diffraction (LEED) patterns were calibrated with the (0,1)
spots of the $h$-BN/Ni(111) substrate sup . Scanning tunneling microscopy
(STM) was performed at liquid nitrogen temperatures Muntwiler  _et al._
(2017).

### Theory

Density functional theory (DFT) calculations were performed on the Sc2YN@C80
endofullerene because it is chemically very similar to
$\mathrm{Sc_{2}TbN@C_{80}}$ but easier to describe accurately Stania  _et al._
(2018). The calculations on the isolated Sc2YN@C80 cluster were performed with
ORCA Neese  _et al._ (2020) and the calculations of Sc2YN@C80/$h$-BN/Ni(111)
using Quantum ESPRESSO Giannozzi  _et al._ (2009); details are given in the
supplemental material sup .

We denote the calculated structures
$h$-BN/Ni(111)-($\sqrt{19}\times\sqrt{19}$)R$23^{\circ}$,
$h$-BN/Ni(111)-($\sqrt{21}\times\sqrt{21}$)R$11^{\circ}$ and
$h$-BN/Ni(111)-($6\times{}6$) as $\sqrt{19}$, $\sqrt{21}$ and $6\times{}6$ or
“isolated”, respectively. We define the condensation energy $E_{c}$ as
$E_{c}=E_{\text{tot}}-E_{\text{mol}}-E_{\text{sub}}$, where $E_{\text{tot}}$
is the total energy of the fully relaxed system, $E_{\text{mol}}$ the energy
of an isolated Sc2YN@C80 molecule, and $E_{\text{sub}}$ the energy of the
relaxed substrate without molecule. The lock in energy is the energy
difference between the highest energy and the lowest energy upon translations
of the molecular layer relative to the substrate. We approximate the
ionisation potential and electron affinity by the energy eigenvalues of the
highest occupied and lowest unoccupied molecular orbital (HOMO and LUMO),
respectively.

## Results and Discussion

### Incommensurability and low temperature super structure

Figure 1 depicts the investigated system: A monolayer of
$\mathrm{Sc_{2}TbN@C_{80}}$ on $h$-BN/Ni(111). The STM image shows hexagonally
close packed molecules, and LEED indicates large scale ordering along the high
symmetry directions of the substrate. While $\mathrm{C_{60}}$ on
$h$-BN/Ni(111) forms a commensurate Ni (4$\times$4) superstructure Muntwiler
_et al._ (2005), the $\mathrm{C_{80}}$ molecules are about a factor of
$\sqrt{80/60}$=1.15 larger and thus may not accommodate in 4$\times$4 Ni(111)
unit cells. The analysis of the LEED spot positions suggests an aligned but
incommensurate $\approx$4.3$\times$4.3 super structure of
$\mathrm{Sc_{2}TbN@C_{80}}$ on $h$-BN/Ni(111).

Figure 1: $\mathrm{Sc_{2}TbN@C_{80}}$ on $h$-BN/Ni(111). (a) Sketch. (b)
Tunneling microscopy image of a monolayer preparation recorded at 77 K. (Area
= $25\times 25$ nm2, $I_{t}$= 1 nA, $V_{t}$= -5 mV). In the hexagonally close
packed layer single vacancies and one second layer molecule are detected. (c)
LEED pattern ($E=30$ eV) recorded at room temperature. An ordered C80
($1\times{}1$) structure with a lattice constant of $1.09\pm 0.05$ nm is
discerned. (d) Parallel component of the LEED scattering vector of TbSc2N@C80
from panel (c) (red) and $h$-BN/Ni(111) (grey) versus reciprocal lattice
vectors GNi and G${}_{\mathrm{C}_{80}}$. The C80 and the Ni lattices are
aligned and incommensurate, where one $\mathrm{C_{80}}$ fits on
$\approx$4.3$\times$4.3 substrate unit cells.

Figure 2 shows the formation of a C80 (2$\times$2) low temperature
superstructure in the incommensurate monolayer $\mathrm{Sc_{2}TbN@C_{80}}$ on
$h$-BN/Ni(111). The structure forms between 80 and 170 K. Such low temperature
ordering or freezing of fullerenes is known from $\mathrm{C_{60}}$ films,
where below 100 K a C60 (2$\times$2) structure was established Benning  _et
al._ (1993); Goldoni  _et al._ (1996). For $\mathrm{C_{60}}$ on $h$-BN/Ni(111)
a $(\sqrt{3}\times\sqrt{3})$ phase was found below 160 K Muntwiler  _et al._
(2005). This indicates that like in three dimensions Heiney  _et al._ (1991),
intermolecular forces lead to ordering of the fullerenes below room
temperature in two dimensional systems. The interaction between
$\mathrm{Sc_{2}TbN@C_{80}}$ molecules is, however, expected to be more
complicated than that between $\mathrm{C_{60}}$ because the high symmetry of
the $\mathrm{C_{80}}$ cage is broken by the endohedral unit, which is
reflected in their appearance as ellipsoids that are weakly distorted from
spherical shape and their permanent dipole moments.

Figure 2: LEED ($E=26.4$ eV) from $\mathrm{Sc_{2}TbN@C_{80}}$ on
$h$-BN/Ni(111) at two different temperatures. (a) C80 (2$\times$2) phase at 83
K. (b) At 170 K the C80 (1$\times$1) phase dominates as at room temperature
(see Figure 1(c)).

In order to better understand the $\mathrm{Sc_{2}TbN@C_{80}}$ on
$h$-BN/Ni(111) system and its differences to $\mathrm{C_{60}}$ on
$h$-BN/Ni(111) extensive DFT calculations were performed. Table 1 compares
different calculated molecular properties of C60 and Sc2YN@C80, which is,
except for the paramagnetism of Tb, electronically very similar to
$\mathrm{Sc_{2}TbN@C_{80}}$, that was used in the experiments.

|  |  C60 | Sc2YN@C80
---|---|---|---
semi minor axis $a$ | (nm) | 0.355 | 0.417
semi minor axis $b$ | (nm) | 0.355 | 0.411
semi minor axis $c$ | (nm) | 0.355 | 0.409
volume | (nm3) | 0.524 | 0.723
void volume | (nm3) | 0.038 | 0.080
dipole moment | (D) | 0 | 0.252
electron affinity | (eV) | 4.19 | 3.81
ionization energy | (eV) | 5.83 | 5.32
Table 1: Calculated geometric and electronic properties of $\mathrm{C_{60}}$
and Sc2YN@C80 in the gas phase. The volume and void volume have been
calculated in adding or subtracting the van der Waals radius of a carbon atom,
0.145 nm, to the semi minor axes $a$, $b$ and $c$ and then applying the
standard formula.

Figure 3 shows the DFT results of a freestanding Sc2YN@C80 monolayer,
Sc2YN@C80 on $h$-BN/Ni(111)-$\sqrt{19}$, and Sc2YN@C80 on
$h$-BN/Ni(111)-$6\times 6$. As a reference we refer to Sc2YN@C80 in the
vacuum. In Figure 3(a) the condensation energies $E_{c}$ are displayed. Figure
3(b) shows the energy of Sc2YN@C80 in a two dimensional hexagonally close
packed layer. The minimum corresponds to a lattice constant of
$a_{\text{min}}=1.103$ nm and a condensation energy of -1.09 eV. Because the
molecules do not fit in a $4\times 4$ Ni(111) unit cell the modelling of the
system with DFT is involved. A commensurate unit cell that is in line with the
LEED observation would not be rotated relative to the substrate lattice, and
would have to contain ten or more molecules, which can not be handled with
present-day capabilities. Instead, we found the lock in energy of the
molecules to be small and performed DFT calculations in rotated unit cells
that contain one molecule. The lattice constant of a $\sqrt{19}$ substrate
unit cell is close to the experimentally inferred lattice constant and we used
it as a commensurate approximation of the Sc2YN@C80 on $h$-BN/Ni(111) system.
Some calculations were performed in the larger $\sqrt{21}$ cell. Compared to
the free standing layer the $\sqrt{19}$ unit cell causes a compressive strain
of 2.6 % and a 124 meV higher energy, while in the $\sqrt{21}$ an expansive
strain of 2.4 % and a 88 meV higher energy was found. Calculations where the
lateral position of the molecule was shifted and fixed relative to the
substrate yielded lock in energies of 99 and 90 meV for the $\sqrt{19}$ and
the $6\times 6$ structures. If the molecules are incommensurate with the
substrate the average energy per molecule increases by 49 meV and 34 meV,
respectively sup . Therefore, the lock in energy is small compared to thermal
energies at the preparation temperature, the binding energy in the
freestanding layer, and the adsorption energy of a single Sc2YN@C80 on
$h$-BN/Ni(111). This supports the picture of non-covalent bonding of the
molecules to the surface and easy incommensurate layer formation. The
orientation of the incommensurate molecular lattice is likely guided by atomic
steps in the substrate that run along high symmetry $\langle
1{\bar{1}}0\rangle$ directions.

In Figures 3(c) and (d) the band structure of the valence- and conduction-
bands on the carbon cages of Sc2YN@C80 on $h$-BN/Ni(111) in $6\times{}6$ and
$\sqrt{19}$ cells are shown. While the bands in the former ”isolated”
structure are flat, the dispersion in the latter, condensed phase is
considerable and around the Fermi level of $p$-type, dispersing downward, with
maxima at the $\Gamma$ point. The large HOMO–LUMO gaps of the molecules become
apparent (1.49 and 1.28 eV), where the LUMO is pinned 118 and 81 meV above the
Fermi level in the two structures, respectively. For comparison the HOMO–LUMO
gap of the free molecule is 1.37 eV. We note that the applied exchange-
correlation functional does not match with the experimental gap inferred from
optical absorption spectroscopy, where 1.72 eV for Sc2YN@C80 in toluene
solution has been measured Chen  _et al._ (2007).

Endofullerenes are known to have conformers with local energy minima that are
difficult to find with DFT optimization methods. For the search of the lowest
energy structure we used an approach where the optimisations start from 120
different conformations Dubrovin  _et al._ (2019). As for C80 endofullerenes
in vacuum Yang  _et al._ (2008); Dubrovin  _et al._ (2019); Westerström  _et
al._ (2021) and on surfaces Dubrovin  _et al._ (2019) we found different
conformers depending on the conformation at the start of the optimization sup
. The calculated workfunction in the lowest energy $\sqrt{19}$ structure is
4.30 eV, while it is 3.55 eV for the substrate without molecules. The standard
deviation of the workfunctions of the 120 optimizations is 79 meV and that of
the corresponding condensation energies is 68 meV sup . Within the performed
simulations with one molecule per unit cell we found no correlation between
workfunction and condensation energy. At this point we speculate that the
($2\times 2$) molecular ordering, which we could not afford to calculate,
might reduce the workfunction by a non-parallel arrangement of the molecular
dipoles.

Figure 3: DFT results on the condensation of Sc2YN@C80. (a) Condensation
energy $E_{c}$ of Sc2YN@C80 in a monolayer (-1.09 eV), free
(reference$\equiv$0), isolated on $h$-BN/Ni(111) (-2.64 eV), and in a
$h$-BN/Ni(111)-$\sqrt{19}$ unit cell (-2.90 eV). The dashed lines indicate the
lock in energy of the molecules relative to the lowest energy structures. (b)
$E_{c}$ vs. lattice constant $a$ in a freestanding monolayer Sc2YN@C80 in
substrate units $a_{0}$. The lattice constants of the $\sqrt{19}$ and
$\sqrt{21}$ super cells are indicated. The dashed curve is the fit of a
Lennard-Jones potential at $a>4.36~{}a_{0}$ with a radial offset of 2.49
$a_{0}$. Band structure of the carbon atoms of Sc2YN@C80 with respect to the
Fermi energy $E_{F}$ in (c) (6$\times$6) and (d) $\sqrt{19}$.

In order to cross check the DFT model and the experimental structures we
calculated N 1s photoemission core level binding energies for hexagonal boron
nitride on Ni(111), with and without molecules, and the endohedral nitrogen in
Sc2YN@C80 on $h$-BN/Ni(111)-$\sqrt{19}$.

In Figure 4 x-ray photoelectron spectroscopy (XPS) data are compared with
final state energies that are convoluted with a Gaussian of 470 meV full width
at half maximum (FWHM). Inspection increases the confidence that experiment
and theory describe very similar physical situations. In contrast to initial
state core level calculations of the C80 cage Stania  _et al._ (2018), the
final state had to be considered sup . Self-consistent calculations with a
half hole on the N 1s orbital were performed and the resulting eigenvalues
were used. From these calculations we reached an excellent agreement of the
lowest energy $\sqrt{19}$ structure and the experiment (see Figure 4 and the
Table in the supplemental material sup ). The DFT results confirm the
assignment of the N 1s core level peaks to the boron nitride and to the
endohedral nitrogen species Stania  _et al._ (2018). The broadening of the BN
derived N 1s peak upon adsorption of endohedral C80 predicts that the nitrogen
atoms in the BN layer corrugate under the influence of the adsorbed molecules
to 0.09 nm sup . The shift of the BN derived N 1s peak upon adsorption of C80
is parallel to the work function and is in line with the physisorption picture
of $h$-BN on Ni that involves vacuum level alignment Nagashima  _et al._
(1995). The chemical shift of the endohedral N 1s peak agrees for experiments
at room temperature, but, as we will see below, not for the low temperature
case, where ($2\times 2$) molecular ordering was observed.

Figure 4: Comparison of XPS and DFT N 1s energies. Top panel, XPS on
$h$-BN/Ni(111) (grey dots) and $\mathrm{Sc_{2}TbN@C_{80}}$ on $h$-BN/Ni(111)
(red dots) at room temperature (photon energy $h\nu$=600 eV). Bottom panel,
DFT final state eigenvalues convoluted with a Gaussian with 470 meV FWHM for
$h$-BN/Ni(111) (dark grey line) Sc2YN@C80 on $h$-BN/Ni(111) $\sqrt{19}$ (red
line). The weight of the BN is the same for $h$-BN/Ni(111) and Sc2YN@C80 on
$h$-BN/Ni(111) and that of the endohedral nitrogen is increased by a factor of
5. The N 1s final state energy in Sc2YN@C80 from DFT is matched to the
experimental binding energy in $\mathrm{Sc_{2}TbN@C_{80}}$sup .

Figure 5 displays He I$\alpha$ excited valence band photoemission data and the
corresponding secondary electron cutoff of $\mathrm{Sc_{2}TbN@C_{80}}$ on
$h$-BN/Ni(111) at 30 and 300 K. The workfunction increases with temperature
from 3.95 to 4.20 eV. This shift is also reflected in the energy of the HOMO
and it indicates vacuum level alignment of the $\mathrm{Sc_{2}TbN@C_{80}}$
molecular orbitals, which is in line with a non-covalent bonding to the
substrate. The HOMO peak of $\mathrm{Sc_{2}TbN@C_{80}}$ on $h$-BN/Ni(111)
occurs at relatively high binding energies of 2.30 and 2.04 eV at 30 and 300
K. They are larger than the optical HOMO–LUMO gap of Sc2YN@C80 and indicative
for a strong on site Coulomb interaction U Lof  _et al._ (1992); Rudolf  _et
al._ (1999). In multilayer Sc3N@C80 Alvarez  _et al._ (2002) the HOMO was
found at $\approx$1.73 eV binding energy. In contrast to $\mathrm{C_{60}}$ on
$h$-BN/Ni(111) Muntwiler  _et al._ (2005) we find no hint on temperature
induced charge transfer, namely no partial filling of the LUMO that was seen
as extra intensity at the Fermi level. The valence band data show, however,
anisotropy of the molecular orbitals at low temperature, while no anisotropy
is visible at room temperature. Such intensity variations are known as ultra-
violet photoelectron diffraction (UPD) effects Osterwalder  _et al._ (1996);
Puschnig  _et al._ (2009); Greif  _et al._ (2013) and indicate orientational
order of the molecules at low temperatures.

Figure 5: Angular resolved He I$\alpha$ excited valence band photoemission
(ARUPS) from $\mathrm{Sc_{2}TbN@C_{80}}$ on $h$-BN/Ni(111). The temperature
induced shift $\Delta=0.3$ eV of the molecular orbital-peaks labeled as HOMO,
HOMO-1 and HOMO-2 is parallel to the shift of the secondary electron cut off
(left panel) that indicates a workfunction increase from 3.95 eV at 30 K to
4.20 eV at 300 K. At low temperature the molecular orbitals display anisotropy
with polar emission angle $\theta$, while at room temperature they do not.

### Behaviour of the molecular conformation with temperature

Figure 6 shows XPS of $\mathrm{Sc_{2}TbN@C_{80}}$ on $h$-BN/Ni(111) between 30
K and room temperature. The N 1s and the Sc 3p3/2 core levels are observed.
The N 1s level of the endohedral unit displays relative to the N 1s levels of
the BN substrate sharper and at lower binding energy. The BN N 1s orbitals of
the substrate have constant binding energy ($\pm$25 meV), while those of the
atoms in the molecules follow the workfunction, i.e. show the same energy
shift as the secondary cut off and the HOMO molecular orbitals in Figure 5.
This means that the BN N 1s energy does not follow the temperature dependence
of the vacuum level, while the one of the molecular layer on top of $h$-BN
does.

We assign the observed behaviour of the workfunction to the onset of
endohedral rotation and different dipole components $p_{z}$ along the surface
normal. The workfunction change $\Delta\Phi$ and $\Delta p_{z}$ are connected
via the Helmholtz equation $\Delta\Phi=-n\Delta p_{z}e/\epsilon_{0}$, where
$n$ is the areal density of the corresponding dipole component $\Delta p_{z}$
and $e$ the elementary charge. Taking the calculated gas phase dipole moment
of Sc2YN@C80 of 0.25 D we would get a workfunction increase of 92 meV in a
$\sqrt{19}$ unit cell in going from a configuration where the dipole points
antiparallel to the surface normal to an isotropic configuration with a zero
average dipole moment.

Figure 6: XPS from $\mathrm{Sc_{2}TbN@C_{80}}$ on $h$-BN/Ni(111) (photon
energy $h\nu$=600 eV). (a) Spectrum in the binding energy range of the N 1s
and the Sc 2p3/2 core levels. At low temperature the endohedral nitrogen
species has a 1.42 eV lower binding energy than the nitrogen of $h$-BN. (b)
Temperature dependent XPS between 30 and 300 K. (c) Two level model for the
temperature dependence of the molecular core level energy shifts. The energy
difference $\Delta E$ and the degeneracy $N_{1}$ are the only thermodynamic
parameters. (d) Endohedral Sc 2p3/2 (grey) and N 1s (light blue) binding
energies as a function of the sample temperature with a fit of the two level
model – solid lines.

The temperature dependence of the core level binding energies that are
parallel to the workfunction allows to extract thermodynamic properties of the
$\mathrm{Sc_{2}TbN@C_{80}}$ on $h$-BN/Ni(111) phase transition. Specifically,
we consider for the molecular conformations two energy levels that are
separated by $\Delta E=E_{1}-E_{0}$. While $E_{0}$ is set to be non-degenerate
($N_{0}=1$), the degeneracy of $E_{1}$ is $N_{1}$ (see Figure 6(c)). As it can
be seen from the calculations in the supplementary material sup , the
assumption of two conformational energies only is a simplification, though the
”smooth bend” of the order parameter does not allow for reliably fitting of
more than four independent parameters. At thermal equilibrium we obtain the
occupation $\langle n_{0}\rangle$ of the lowest energy state $E_{0}$,

$\langle n_{0}\rangle=\frac{1}{1+N_{1}\exp{(-\Delta E/k_{B}T})}$ (1)

and the occupation of state $E_{1}$, $\langle n_{1}\rangle=1-\langle
n_{0}\rangle$.

If the measured core level energies $E_{B}$ are taken to express the order
parameter i.e. the weighted sum $E_{B}=\langle n_{0}\rangle E_{B0}+\langle
n_{1}\rangle E_{B1}$, we may derive $E_{B0}$, $E_{B1}$, $\Delta E$ and $N_{1}$
from the measured data. $E_{B0}$ describes the system at T=0 or $\langle
n_{1}\rangle=0$ and $E_{B1}$ is the core level energy if all molecules were
excited, i.e. $\langle n_{1}\rangle=1$. From $\langle n_{0}\rangle(T)$ the
relevant thermodynamic quantities $\Delta E$ and $N_{1}$ are determined. The
solid lines in Figure 6(d) show the fits of the $N_{1}$ degenerate two level
model for the N 1s and the Sc 2p3/2 core levels of $\mathrm{Sc_{2}TbN@C_{80}}$
on $h$-BN/Ni(111). The fit-parameters are $\Delta E=74\pm 6$ meV,
$E_{B0}-E_{B1}=310\pm 40$ meV and the degeneracy $N_{1}=1300\pm 700$. As
expected $E_{B0}-E_{B1}$ is in line with the work function shift. The energy
$\Delta E$ has the order of magnitude of the scatter of $E_{c}$ for the
calculated conformations of Sc2YN@C80 on $h$-BN/Ni(111) sup . This means that
the transition has the energy scale of different molecular conformations of
Sc2YN@C80/$h$-BN/Ni(111). The large degeneracy $N_{1}$ reflects the large C80
($2\times 2$) unit cell at low temperature and indicates a strong contribution
of the entropy to the free energy of the system above the ordering
temperature.

## Conclusions

We observed a temperature induced workfunction shift of
$\mathrm{Sc_{2}TbN@C_{80}}$ on $h$-BN/Ni(111) centered at 125 K. This shift is
related to the disappearance of a $\mathrm{Sc_{2}TbN@C_{80}}$(2$\times 2$)
LEED structure. The transition is an order disorder transition with onset of
rotation of the endohedral clusters. This conclusion bases on angular
dependent valence band photoelectron spectroscopy. DFT calculations, predict
the lattice constant of Sc2YN@C80, a permanent dipole moment, describe the N
1s XPS spectrum in the Sc2YN@C80(1$\times 1$) phase and propose different
conformers with an energy distribution that is in line with a model for the
temperature dependence of the molecular core level binding energies.

### Acknowledgments

This work was supported by the Swiss National Science Foundation grant No.
200020_153312 and the Institute for Basic Science (IBS-R014-D1). Calculations
were performed at the CSCS Swiss National Supercomputing Centre under project
uzh11. The photoemission, LEED and STM measurements were performed at the
PEARL beamline of the Swiss Light Source, Paul Scherrer Institut, Villigen.
AAP acknowledges Deutsche Forschungsgemeinschaft (grant PO 1602/8-1).

## References

  * Rudolf  _et al._ (1999) P. Rudolf, M. S. Golden, and P. A Brühwiler, “Studies of fullerenes by the excitation, emission, and scattering of electrons,” J. Electron Spectros. Relat. Phenomena 100, 409–433 (1999).
  * Sánchez  _et al._ (2009) L. Sánchez, R. Otero, J. M. Gallego, R. Miranda, and N. Martin, “Ordering fullerenes at the nanometer scale on solid surfaces,” Chem. Rev. 109, 2081–2091 (2009).
  * Moriarty (2010) P. J. Moriarty, “Fullerene adsorption on semiconductor surfaces,” Surf. Sci. Rep. 65, 175–227 (2010).
  * Heiney  _et al._ (1991) P. A. Heiney, J. E. Fischer, A. R. McGhie, W. J. Romanow, A. M. Denenstein, J. P. McCauley Jr., A. B. Smith, and D. E. Cox, “Orientational ordering transition in solid C60,” Phys. Rev. Lett. 66, 2911–2914 (1991).
  * Benning  _et al._ (1993) P. J. Benning, F. Stepniak, and J. H. Weaver, “Electron-diffraction and photoelectron-spectroscopy studies of fullerene and alkali-metal fulleride films,” Phys. Rev. B 48, 9086–9096 (1993).
  * Goldoni  _et al._ (1996) A. Goldoni, C. Cepek, and S. Modesti, “First-order orientational-disordering transition on the (111) surface of C60,” Phys. Rev. B 54, 2890–2895 (1996).
  * Goldoni  _et al._ (2002) A. Goldoni, C. Cepek, R. Larciprete, L. Sangaletti, S. Pagliara, G. Paolucci, and M. Sancrotti, “Core level photoemission evidence of frustrated surface molecules: A germ of disorder at the (111) surface of C60 before the order-disorder surface phase transition,” Phys. Rev. Lett. 88, 196102 (2002).
  * Muntwiler  _et al._ (2005) M. Muntwiler, W. Auwärter, A. Seitsonen, J. Osterwalder, and T. Greber, “Rocking-motion-induced charging of C60 on $h$-BN/Ni(111),” Phys. Rev. B 71, 121402 (2005).
  * Popov  _et al._ (2013) A. A. Popov, S. Yang, and L. Dunsch, “Endohedral Fullerenes,” Chem. Rev. 113, 5989–6113 (2013).
  * Stevenson  _et al._ (1999) S. Stevenson, G. Rice, T. Glass, K. Harich, F. Cromer, M. R. Jordan, J. Craft, E. Hadju, R. Bible, M. M. Olmstead, K. Maitra, A. J. Fisher, A. L. Balch, and H. C. Dorn, “Small-bandgap endohedral metallofullerenes in high yield and purity,” Nature 401, 55–57 (1999).
  * Westerström  _et al._ (2012) R. Westerström, J. Dreiser, C. Piamonteze, M. Muntwiler, S. Weyeneth, H. Brune, S. Rusponi, F. Nolting, A. Popov, SF. Yang, L. Dunsch, and T. Greber, “An endohedral single-molecule magnet with long relaxation times: DySc2N@C80,” J. Am. Chem. Soc. 134, 9840–9843 (2012).
  * Alvarez  _et al._ (2002) L. Alvarez, T. Pichler, P. Georgi, T. Schwieger, H. Peisert, L. Dunsch, Z. Hu, M. Knupfer, J. Fink, P. Bressler, M. Mast, and M. S. Golden, “Electronic structure of pristine and intercalated Sc3N@C80 metallofullerene,” Phys. Rev. B 66, 035107 (2002).
  * Shiozawa  _et al._ (2005) H. Shiozawa, H. Rauf, T. Pichler, D. Grimm, X. Liu, M. Knupfer, M. Kalbac, S. Yang, L. Dunsch, B. Büchner, and D. Batchelor, “Electronic structure of the trimetal nitride fullerene Dy3N@C80,” Phys. Rev. B 72, 195409 (2005).
  * Leigh  _et al._ (2007) D. F. Leigh, C. Norenberg, D. Cattaneo, J. H. G. Owen, K. Porfyrakis, A. Li Bassi, A. Ardavan, and G. A. D. Briggs, “Self-assembly of trimetallic nitride template fullerenes on surfaces studied by STM,” Surf. Sci. 601, 2750–2755 (2007).
  * Treier  _et al._ (2009) M. Treier, P. Ruffieux, R. Fasel, F. Nolting, SF. Yang, L. Dunsch, and T. Greber, “Looking inside an endohedral fullerene: Inter- and intramolecular ordering of ${\text{Dy}}_{3}\text{N}@{\text{C}}_{80}$ $({I}_{h})$ on Cu(111),” Phys. Rev. B 80, 081403 (2009).
  * Huang  _et al._ (2011) T. Huang, J. Zhao, M. Peng, A. A. Popov, SF. Yang, L. Dunsch, and H. Petek, “A molecular switch based on current-driven rotation of an encapsulated cluster within a fullerene cage,” Nano Lett. 11, 5327–5332 (2011).
  * Krylov  _et al._ (2020) D. S. Krylov, S. Schimmel, V. Dubrovin, F. Liu, T. T. Nhung Nguyen, L. Spree, C.H. Chen, G. Velkos, C. Bulbucan, R. Westerström, M. Studniarek, J. Dreiser, C. Hess, B. Büchner, S. M. Avdoshenko, and A. A. Popov, “Substrate-independent magnetic bistability in monolayers of the single-molecule magnet Dy2ScN@C80 on metals and insulators,” Angew. Chem. Int. Ed. 59, 5756–5764 (2020).
  * Westerström  _et al._ (2015) R. Westerström, A.-C. Uldry, R. Stania, J. Dreiser, C. Piamonteze, M. Muntwiler, F. Matsui, S. Rusponi, H. Brune, SF. Yang, A. Popov, B. Büchner, B. Delley, and T. Greber, “Surface aligned magnetic moments and hysteresis of an endohedral single-molecule magnet on a metal,” Phys. Rev. Lett. 114, 087201–5 (2015).
  * Greber  _et al._ (2019) T. Greber, A. P. Seitsonen, A. Hemmi, J. Dreiser, R. Stania, F. Matsui, M. Muntwiler, A. A. Popov, and R. Westerström, “Circular dichroism and angular deviation in x-ray absorption spectra of Dy2ScN@C80 single-molecule magnets on h-BN/Rh(111),” Phys. Rev. Materials 3, 014409 (2019).
  * Kostanyan  _et al._ (2017) A. Kostanyan, R. Westerström, Y. Zhang, D. Kunhardt, R. Stania, B. Büchner, A. A. Popov, and T. Greber, “Switching molecular conformation with the torque on a single magnetic moment,” Phys. Rev. Lett. 119, 237202 (2017).
  * Stania  _et al._ (2018) R. Stania, A. P. Seitsonen, D. Kunhardt, B. Büchner, A. A. Popov, M. Muntwiler, and T. Greber, “Electrostatic interaction across a single-layer carbon shell,” J. Phys. Chem. Lett. 9, 3586–3590 (2018).
  * Zhang  _et al._ (2015) Y. Zhang, D. Krylov, M. Rosenkranz, S. Schiemenz, and A. A. Popov, “Magnetic anisotropy of endohedral lanthanide ions: paramagnetic NMR study of MSc2N@C80-Ih with M running through the whole $4f$ row,” Chem. Sci. 6, 2328–2341 (2015).
  * Auwärter  _et al._ (1999) W. Auwärter, T. J. Kreutz, T. Greber, and J. Osterwalder, “XPD and STM investigation of hexagonal boron nitride on Ni(111),” Surf. Sci. 429, 229–236 (1999).
  * Muntwiler  _et al._ (2017) M. Muntwiler, J. Zhang, R. Stania, F. Matsui, P. Oberta, U. Flechsig, L. Patthey, C. Quitmann, T. Glatzel, R. Widmer, E. Meyer, T. A. Jung, P. Aebi, R. Fasel, and T. Greber, “Surface science at the PEARL beamline of the Swiss Light Source,” J. Synchrotron Rad. 24, 354–366 (2017).
  * (25) “Supplementaries,” .
  * Neese  _et al._ (2020) F. Neese, F. Wennmohs, U. Becker, and C. Riplinger, “The ORCA quantum chemistry program package,” J. Chem. Phys. 152, 224108 (2020).
  * Giannozzi  _et al._ (2009) P. Giannozzi, S. Baroni, N. Bonini, M. Calandra, R. Car, C. Cavazzoni, D. Ceresoli, G. L. Chiarotti, M. Cococcioni, I. Dabo, A. Dal Corso, S. de Gironcoli, S. Fabris, G. Fratesi, R. Gebauer, U. Gerstmann, C. Gougoussis, A. Kokalj, M. Lazzeri, L. Martin-Samos, N. Marzari, F. Mauri, R. Mazzarello, S. Paolini, A. Pasquarello, L. Paulatto, C. Sbraccia, S. Scandolo, G. Sclauzero, A. P. Seitsonen, A. Smogunov, P. Umari, and R. M. Wentzcovitch, “Quantum ESPRESSO: a modular and open-source software project for quantum simulations of materials,” J. Phys. Condens. Matt. 21, 395502 (2009).
  * Chen  _et al._ (2007) N. Chen, L. Z. Fan, K. Tan, Y. Q. Wuand, C. Y. Shu, X. Lu, and C. R. Wang, “Comparative spectroscopic and reactivity studies of Sc3-xYxN@C80 ($x={0-3}$),” J. Phys. Chem. C 111, 11823–11828 (2007).
  * Dubrovin  _et al._ (2019) V. Dubrovin, L-H. Gan, B. Büchner, A. A. Popov, and S. M. Avdoshenko, “Endohedral metal-nitride cluster ordering in metallofullerene-Ni${}^{\text{II}}$(OEP) complexes and crystals: a theoretical study,” Phys. Chem. Chem. Phys. 21, 8197–8200 (2019).
  * Yang  _et al._ (2008) S. F. Yang, A. A. Popov, and L. Dunsch, “Carbon pyramidalization in fullerene cages induced by the endohedral cluster: Non-scandium mixed metal nitride clusterfullerenes,” Angew. Chem. Int. Ed. 47, 8196–8200 (2008).
  * Westerström  _et al._ (2021) R. Westerström, V. Dubrovin, K. Junghans, C. Schlesier, B. Büchner, S. M. Avdoshenko, A. Popov, A. Kostanyan, J. Dreiser, and T. Greber, “Precise measurement of angles between two magnetic moments and their configurational stability in single-molecule magnets,” Phys. Rev. B 104, 224401 (2021).
  * Nagashima  _et al._ (1995) A. Nagashima, N. Tejima, Y. Gamou, T. Kawai, and C. Oshima, “Electronic structure of monolayer hexagonal boron nitride physisorbed on metal surfaces,” Phys. Rev. Lett. 75, 3918–3921 (1995).
  * Lof  _et al._ (1992) R. W. Lof, M. A. van Veenendaal, B. Koopmans, H. T. Jonkman, and G. A. Sawatzky, “Band gap, excitons, and coulomb interaction in solid ${\mathrm{C}}_{60}$,” Phys. Rev. Lett. 68, 3924–3927 (1992).
  * Osterwalder  _et al._ (1996) J. Osterwalder, T. Greber, P. Aebi, R. Fasel, and L. Schlapbach, “Final-state scattering in angle-resolved ultraviolet photoemission from copper,” Phys. Rev. B 53, 10209–10216 (1996).
  * Puschnig  _et al._ (2009) P. Puschnig, S. Berkebile, A. J. Fleming, G. Koller, K. Emtsev, T. Seyller, J. D. Riley, C. Ambrosch-Draxl, F. P. Netzer, and M. G. Ramsey, “Reconstruction of molecular orbital densities from photoemission data,” Science 326, 702–706 (2009).
  * Greif  _et al._ (2013) M. Greif, L. Castiglioni, A. P. Seitsonen, S. Roth, J. Osterwalder, and M. Hengsberger, “Photoelectron diffraction in the x-ray and ultraviolet regime: Sn-phthalocyanine on Ag(111),” Phys. Rev. B 87, 085429 (2013).


# Independence equivalence classes of cycles

Boon Leong Ng

(National Institute of Education, Nanyang Technological University, Singapore
)

###### Abstract

The independence equivalence class of a graph $G$ is the set of graphs that
have the same independence polynomial as $G$. Beaton, Brown and Cameron (2019)
found the independence equivalence classes of even cycles, and raised the
problem of finding the independence equivalence class of odd cycles. The
problem is completely solved in this paper.

##  1 Definitions and Introduction

Let $G$ be a simple graph with vertex set $V(G)$ and edge set $E(G)$. A set of
vertices $U\subseteq V(G)$ is said to be _independent_ if no two vertices in
$U$ are adjacent. The _independence number_ $\alpha(G)$ of $G$ is the
cardinality of the largest independent set of $G$. The _independence
polynomial_ $I(G,x)$ of $G$ is given by
$I(G,x)=\sum_{k=0}^{\alpha(G)}i_{k}(G)x^{k}$ where $i_{k}(G)$ is the number of
independent subsets of $V(G)$ of cardinality $k$. A survey of results on
independence polynomials can be found in [16].

Two graphs $G$ and $H$ are said to be _independence equivalent_ if
$I(G,x)=I(H,x)$. The _independence equivalence class_ $\mathcal{I}(G)$ of a
graph $G$ is the set of graphs which are independence equivalent to $G$. A
graph $G$ is said to be _independence unique_ if $\mathcal{I}(G)=\\{G\\}$,
that is, if $I(G,x)=I(H,x)$ implies that $G\cong H$ ($G$ is isomorphic to
$H$).

In the study of graph polynomials, the problem of finding nonisomorphic graphs
that have equivalent polynomials is one that naturally arises. An equivalence
class analogous to the independence equivalence class can be defined for any
graph polynomial. In the case of chromatic polynomials, this has a long
history (see [4, 7, 8, 14] and Chapter 3 of [10]). More recently, the study of
domination polynomials has also led to results on domination equivalence [1,
2, 5, 13].

Returning to independence polynomials, the existence of graphs with the same
independence polynomial was already noticed very early on by Wingard [19]. The
following two results, on finding the independence polynomial of a graph in
terms of that of its subgraphs, are very useful in showing that graphs are
independence equivalent.

######  Proposition 1.

[11] For any vertex $u\in V(G)$,

$I(G,x)=I(G-u,x)+xI(G-N[u],x).$

######  Proposition 2.

[11] For any edge $e=uv$ in $E(G)$,

$I(G,x)=I(G-e,x)-x^{2}I(G-(N(u)\cup N(v)),x).$

$a$$b$$\cdots$$f$ Figure 1: The graph $D_{n}$ with $n$ vertices

For example, the following family of independence equivalent graphs was
observed by Chism [9].

######  Proposition 3.

[9] For $n\geq 4$, if $G$ is the cyclic graph $C_{n}$ and $H$ is the graph
$D_{n}$ shown in Figure 1, then $C_{n}$ and $D_{n}$ are independence
equivalent.

Oboudi [17] and Beaton, Brown and Cameron [6] considered the question of
whether other graphs existed in $\mathcal{I}(C_{n})$, and showed the
following:

######  Proposition 4.

[17] If $G$ is a connected graph in $\mathcal{I}(C_{n})$, then
$G\in\\{C_{n},D_{n}\\}$.

######  Proposition 5.

[6]

  1. (i)

$\mathcal{I}(C_{6})=\\{C_{6},D_{6},K_{4}-e\cup K_{2}\\}$ for $n=6$,

  2. (ii)

$\mathcal{I}(C_{n})=\\{C_{n},D_{n}\\}$ for even $n\geq 4$, $n\neq 6$,

  3. (iii)

$\mathcal{I}(C_{n})=\\{C_{n},D_{n}\\}$ for $n=p^{k}$ where $p\geq 5$ is prime
and $k$ is a positive integer.

Beaton, Brown and Cameron [6] also made the following conjecture:

######  Conjecture 1.

If $3\not|n$ and $n\geq 4$ is odd, then $G$ is independence equivalent to
$C_{n}$ iff $G\in\\{C_{n},D_{n}\\}$.

In the case where $n$ is an odd multiple of $3$, Oboudi [17] observed for
$n=9$, and Beaton, Brown and Cameron [6] observed for $n=15$, that there exist
graphs other than $D_{n}$ which are independence equivalent to $C_{n}$. A
computer search carried out by Beaton, Brown and Cameron [6] showed that these
were the only examples up to $n=31$, and they raised the problem of
determining $\mathcal{I}(C_{n})$ for larger values of $n$ which are odd
multiples of $3$.

In this paper, we will prove Beaton, Brown and Cameron’s conjecture, and solve
their problem, in the following theorem.

######  Theorem 6.

For odd $n\geq 3$,

  1. (i)

$\mathcal{I}(C_{3})=\\{C_{3}\\}$,

  2. (ii)

$\mathcal{I}(C_{0})=\\{C_{9},D_{9},C_{3}\cup G_{a},C_{3}\cup G_{b},C_{3}\cup
G_{c},C_{3}\cup G_{d}\\}$ (see Figure 2; the case $C_{3}\cup G_{d}$ seems to
have been omitted by previous writers [17, 6]),

  3. (iii)

$\mathcal{I}(C_{15})=\\{C_{15},D_{15},C_{3}\cup C_{5}\cup
G^{\prime}_{a},C_{3}\cup D_{5}\cup G^{\prime}_{a},C_{3}\cup C_{5}\cup
G^{\prime}_{b},C_{3}\cup D_{5}\cup G^{\prime}_{b},C_{3}\cup C_{5}\cup
G^{\prime}_{c},C_{3}\cup D_{5}\cup G^{\prime}_{c}\\}$ (see Figure 3),

  4. (iv)

$\mathcal{I}(C_{n})=\\{C_{n},D_{n}\\}$ for odd $n\geq 5$, except for $n=9$ and
$n=15$,

$G_{a}$$G_{b}$$G_{c}$$G_{d}$ Figure 2: Graphs $G_{a}$, $G_{b}$, $G_{c}$ and
$G_{d}$ in Theorem 6 $G^{\prime}_{a}$$G^{\prime}_{b}$$G^{\prime}_{c}$ Figure
3: Graphs $G^{\prime}_{a}$, $G^{\prime}_{b}$ and $G^{\prime}_{c}$ in Theorem 6

Proposition 5 and Thereom 6 together give us a complete characterisation of
$\mathcal{I}(C_{n})$ for all $n\geq 3$.

The proof of Theorem 6 will proceed as follows. Since Proposition 4 completely
characterises the connected graphs which are independence equivalent to
$C_{n}$, we need only consider disconnected graphs. From the definition of the
independence polynomial, it is clear that if $G$ is a disconnected graph with
connected components $G_{1},\ldots,G_{r}$, then

$I(G,x)=\prod_{i=1}^{r}I(G_{i},x).$

In other words, the independence polynomial of a graph $G$ is the product of
the independence polynomials of the connected components of $G$.

In Section 2, we show how to factorise $I(C_{n},x)$ over $\mathbb{Z}[x]$ for
odd $n$, and investigate properties of the factors of $I(C_{n},x)$. This in
turn enables us, in Section 3, to determine which graphs can be connected
components of a graph $G\in\mathcal{I}(C_{n})$. The case where $n$ is not a
multiple of $3$ is addressed in Section 4, where it is shown that
$\mathcal{I}(C_{n})=\\{C_{n},D_{n}\\}$.

The more difficult case where $n$ is a multiple of $3$ is addressed in Section
5, where we seek graphs in $\mathcal{I}(C_{n})$ that are not isomorphic to
$C_{n}$ or $D_{n}$. Such graphs must be disconnected, and we show that one of
the connected components must be $C_{3}$, and the other components must either
be cycle graphs, or belong one of the families of graphs in Figure 4. Further
consideration of the degree and coefficients of $I(C_{n},x)$ narrows down the
possible graphs to those listed in the statement of Theorem 6.

##  2 Factorisation of the Independence Polynomial of $C_{n}$

In this section, we factorise $I(C_{n},x)$ over $\mathbb{Z}[x]$ to investigate
properties of the factors.

The roots of the independence polynomials of cyclic graphs have been
completely determined by Alikhani and Peng [3].

######  Proposition 7.

[3] The roots of $I(C_{n},x)$ are

$c_{i}=-\frac{1}{2+2\cos\left(\frac{(2i-1)\pi}{n}\right)}$

for $i=1,2,\ldots,\left\lfloor\frac{n}{2}\right\rfloor$.

Now, the minimal polynomials of $\cos(2\pi k/n)$ have been previously
determined by Lehmer [15] and Watkins and Zeitlin [18].

######  Proposition 8.

[15] If $\gcd(k,n)=1$ and $n\geq 3$ then the minimal polynomial of $2\cos(2\pi
k/n)$ has degree $\phi(n)/2$ and leading coefficient $1$, where $\phi(n)$ is
Euler’s totient function.

Watkins and Zeitlin [18] give an explicit construction for this minimal
polynomial in terms of Chebychev polynomials.

######  Proposition 9.

[18] The roots of the minimal polynomial of $2\cos(2\pi k/n)$ are precisely
those values of $2\cos(2\pi k/n)$ for which $\gcd(k,n)=1$ and $1\leq k<n/2$.

We are now in a position to find the minimal polynomials of $c_{i}$.

######  Proposition 10.

Let $n\geq 3$ be an odd integer. For positive integers $i$ where
$\gcd(2i-1,n)=1$ and $1\leq i\leq\left\lfloor\frac{n}{2}\right\rfloor$, let
$f(x)$ be the minimal polynomial of $c_{i}$ over $\mathbb{Z}[x]$. For positive
integers $k$ where $\gcd(k,n)=1$ and $1\leq k<n/2$, let $g(x)$ be the minimal
polynomial of $2\cos((2\pi k)/(2n))$ over $\mathbb{Z}[x]$. Then $f(x)$ and
$g(x)$ are of the same degree $d=\phi(n)/2$. Furthermore, $f(x)|I(C_{n},x)$.

###### Proof.

Let

$x_{i}=2\cos\left(\frac{2\pi(2i-1)}{2n}\right)=-\frac{2c_{i}+1}{c_{i}}.$

Since $n$ is odd, $\gcd(2i-1,n)=1$ iff $\gcd(2i-1,2n)=1$. Therefore, the set
of values taken by $x_{i}$ as $i$ varies is precisely those of $2\cos((2\pi
k)/(2n))$ as $k$ varies.

$\displaystyle\left\\{x_{i}:\gcd(2i-1,n)=1\textrm{ and }1\leq
i\leq\left\lfloor\frac{n}{2}\right\rfloor\right\\}$ $\displaystyle=$
$\displaystyle\left\\{2\cos\left(\frac{2\pi k}{2n}\right):\gcd(k,n)=1\textrm{
and }1\leq k<\frac{n}{2}\right\\}$

From Proposition 8, $g(x)$ has degree $\phi(2n)/2=\phi(n)/2$ and leading
coefficient 1. From Proposition 9, we now have

$g(x)=\prod_{\begin{subarray}{c}\gcd(2i-1,n)=1,\\\ 1\leq
i\leq\left\lfloor\frac{n}{2}\right\rfloor\end{subarray}}(x-x_{i})$

Since we know that $g(x)$ is an irreducible polynomial with integer
coefficients and degree $d$, let

$g(x)=\sum_{t=0}^{d}a_{t}x^{t}.$

Now, we can translate $g(x)$ along the $x$-axis to obtain another irreducible
polynomial $h(x)$ with integer coefficients and degree $d$, whose roots are
$x_{i}+2$.

$g(x-2)=\sum_{t=0}^{d}a_{t}(x-2)^{t}=\sum_{t=0}^{d}b_{t}x^{t}=h(x).$

Since $x_{i}+2=-1/c_{i}$,

$0=\sum_{t=0}^{d}a_{t}x_{i}^{t}=\sum_{t=0}^{d}b_{t}(x_{i}+2)^{t}=\sum_{t=0}^{d}b_{t}\left(-\frac{1}{c_{i}}\right)^{t}=\left(-\frac{1}{c_{i}}\right)^{d}\sum_{t=0}^{d}b_{t}(-c_{i})^{d-t}.$

and therefore the $c_{i}$ are roots of a polynomial

$f(x)=\sum_{t=0}^{d}b_{t}(-x)^{d-t}.$

Since $h(x)$ is irreducible, $f(x)$ is irreducible as well, and has degree $d$
and integer coefficients.

The roots of $f(x)$ are precisely the values of $c_{i}$ where $\gcd(2i-1,n)=1$
and $1\leq i\leq\left\lfloor\frac{n}{2}\right\rfloor$. As all these values of
$c_{i}$ are also roots of $I(C_{n},x)$, we see that $f(x)|I(C_{n},x)$. ∎

We can therefore define a sequence of polynomials $f_{n}(x)$ for odd positive
integers $n$.

######  Definition 11.

For an odd positive integer $n$, the polynomial $f_{n}(x)$ is defined to be

$f(x)=\begin{cases}1&n=1,\\\
k_{n}\displaystyle\prod_{\begin{subarray}{c}{\gcd(2i-1,n)=1,}\\\ 1{\leq
i\leq\left\lfloor\frac{n}{2}\right\rfloor}\end{subarray}}(x-c_{i})&\textrm{odd
}n\geq 1,\end{cases}$

where $k_{n}$ is an appropriate constant to make the coefficients of $f_{n}$
integers whose greatest common divisor is 1.

Then $f_{n}(x)$ is the minimal polynomial over $\mathbb{Z}[x]$ of $c_{i}$
where $\gcd(2i-1,n)=1$ and $1\leq i\leq\left\lfloor\frac{n}{2}\right\rfloor$
for odd $n>1$. The following proposition then follows immediately.

######  Proposition 12.

For odd $n>1$,

$I(C_{n},x)=\prod_{m|n}f_{m}(x).$

######  Corollary 13.

For an odd prime $p$, $f_{p}(x)=I(C_{p},x)$.

######  Corollary 14.

[6] For an odd positive integer $n$ and $k\neq 1$, $k|n$ if and only if
$I(C_{k},x)|I(C_{n},x)$.

######  Example 15.

We will illustrate Proposition 12 for $n=3,5,9,15$. (We omit explicitly
writing the factor $f_{1}(x)=1$.)

  1. (i)

In the case $n=3$, we have

$f_{3}(x)=I(C_{3},x)=1+3x,$

an irreducible polynomial.

Similarly, in the case $n=5$, we have

$f_{5}(x)=I(C_{5},x)=I(D_{5},x)=1+5x+5x^{2}.$

  2. (ii)

In the case $n=9$, we have

$\displaystyle I(C_{9},x)$ $\displaystyle=$ $\displaystyle
1+9x+27x^{2}+30x^{3}+9x^{4}$ $\displaystyle=$
$\displaystyle\underbrace{(1+3x)}_{f_{3}(x)}\underbrace{(1+6x+9x^{2}+3x^{3})}_{f_{9}(x)}.$

Note that for the four graphs in Figure 2,

$I(G_{a},x)=I(G_{b},x)=I(G_{c},x)=I(G_{d},x)=f_{9}(x).$

  3. (iii)

In the case $n=15$, we have

$\displaystyle I(C_{15},x)$ $\displaystyle=$ $\displaystyle
1+15x+90x^{2}+275x^{3}+450x^{4}+378x^{5}+140x^{6}+15x^{7}$ $\displaystyle=$
$\displaystyle\underbrace{(1+3x)}_{f_{3}(x)}\underbrace{(1+5x+5x^{2})}_{f_{5}(x)}\underbrace{(1+7x+14x^{2}+8x^{3}+x^{4})}_{f_{15}(x)}.$

Note that for the three graphs in Figure 3,

$I(G^{\prime}_{a},x)=I(G^{\prime}_{b},x)=I(G^{\prime}_{c},x)=f_{15}(x).$

We now show how this factorisation of $I(C_{n},x)$ gives us information about
graphs which are independence equivalent to it.

##  3 Structure of a graph which is independence equivalent to $C_{n}$

######  Definition 16.

[6] A polynomial $p(x)=\sum_{i=0}^{n}p_{i}x^{i}$, where the $p_{i}$ are all
non-negative integers, is unicyclic if $p_{0}=1$ and
$p_{2}=\binom{p_{1}}{2}-p_{1}$.

######  Corollary 17.

[6] Let $G$ be a connected graph. Then $G$ has an independence polynomial that
is unicyclic iff $G$ is unicyclic.

######  Proposition 18.

[6] Suppose that $p(x)=q(x)r(x)$.

  1. (i)

If $q(x)$ and $r(x)$ are unicyclic then $p(x)$ is unicyclic.

  2. (ii)

If $p(x)$ and $q(x)$ are unicyclic then $r(x)$ is unicyclic.

######  Proposition 19.

The polynomials $f_{n}(x)$ for odd $n\geq 3$ are all unicyclic.

###### Proof.

Suppose that $n$ has prime factorisation $p_{1}^{r_{1}}p_{2}^{r_{2}}\ldots
p_{j}^{r_{j}}$. We use induction on $s_{n}=r_{1}+\ldots+r_{j}$. If $s_{n}=1$
then $n$ is prime, and therefore, by Corollary 13, $f_{n}(x)=I(C_{n},x)$ which
is unicyclic. Suppose it holds for all odd $n\geq 3$ where $1\leq s_{n}<s$.

Let $n\geq 3$ be odd where $s_{n}=s\geq 2$. Now

$f_{n}(x)=\frac{I(C_{n},x)}{\displaystyle\prod_{m|n,m<n}f_{m}(x)}.$

$I(C_{n},x)$ is unicyclic and, for all $m$ such that $m|n$, $m<n$, we have
$s_{m}<s$ so $f_{m}(x)$ is unicyclic by our induction hypothesis. Therefore,
by Proposition 18(ii), $f_{n}(x)$ is also unicyclic. ∎

######  Proposition 20.

If $G\in\mathcal{I}(C_{n})$, where $n$ is odd, and $G$ is the disjoint union
of connected graphs $G_{1},G_{2},\ldots,G_{r}$, then
$G_{1},G_{2},\ldots,G_{r}$ are all unicyclic.

###### Proof.

For each $i\in\\{1,\ldots,r\\}$, $I(G_{i},x)$ is a factor of $I(C_{n},x)$.
Therefore, it must be a product of some polynomials $f_{m}(x)$ where $m|n$.
Since each of the $f_{m}(x)$ are unicyclic, their product $I(G_{i},x)$ is
unicyclic by Proposition 18(i), and hence $G_{i}$ is unicyclic by Corollary
17. ∎

Therefore, if $G\in\mathcal{I}(C_{n})$, where $n$ is odd, then $G=D_{n}$ or
$G$ is the disjoint union of a set of unicyclic graphs.

We will make use of the following notation and propositions from Beaton, Brown
and Cameron [6].

######  Definition 21.

Let $n\geq 4$ be a positive integer and $G$ be a graph. Let $n_{G}(C_{3})$ be
the number of triangles in $G$, and $g_{i}$ denote the number of vertices in
$G$ of degree $i$.

######  Proposition 22.

[6] If $G\in\mathcal{I}(C_{n})$, where $n\geq 4$, then

  1. (i)

$\displaystyle\sum_{i=0}^{n-1}g_{i}=n$,

  2. (ii)

$\displaystyle\sum_{i=1}^{n-1}i\cdot g_{i}=2n$,

  3. (iii)

$\displaystyle\sum_{i=2}^{n-1}\binom{i}{2}g_{i}=n+n_{G}(C_{3})$,

  4. (iv)

$n_{G}(C_{3})\geq g_{0}+\displaystyle\sum_{i=3}^{n-1}g_{i}$, so that the
number of vertices in $G$ not of degree 1 or 2 is $n(C_{3})$.

Actually, Beaton, Brown and Cameron proved a stronger statement than
Proposition 22(iv).

######  Proposition 23.

If $G\in\mathcal{I}(C_{n})$, where $n\geq 4$, then

$n_{G}(C_{3})=\sum_{i=3}^{n-1}\binom{i-1}{2}g_{i}$

###### Proof.

From Proposition 22, if we add (i) and (iii) and subtract (ii), we get

$\displaystyle n_{G}(C_{3})$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{n-1}g_{i}+\sum_{i=2}^{n-1}\binom{i}{2}g_{i}-\sum_{i=1}^{n-1}i\cdot
g_{i}$ $\displaystyle=$ $\displaystyle
g_{0}+\sum_{i=3}^{n-1}\left(\binom{i}{2}-i+1\right)g_{i}$ $\displaystyle=$
$\displaystyle g_{0}+\sum_{i=3}^{n-1}\binom{i-1}{2}g_{i}.$

Now $g_{0}$ is the number of isolated vertices. However, if $G$ has an
isolated vertex, then $I(K_{1},x)=1+x$ would be a factor of $I(G,x)$, so $-1$
would be a root of $I(G,x)=I(C_{n},x)$. However, we can see from Proposition 7
that this is not possible. Hence $g_{0}=0$ and the result follows. ∎

We now try to elucidate the structure of a graph $G\in\mathcal{I}(C_{n})$ for
odd $n\geq 5$. If $G$ is not $C_{n}$ or $D_{n}$ then, by Proposition 4, $G$ is
not connected, and by Proposition 20, $G=\bigcup_{i=1}^{r}G_{i}$ where the
$G_{i}$ are connected unicyclic graphs.

Since $I(C_{n},x)$ does not have repeated roots, at most one of the connected
components can be $C_{3}$. If any of the other connected components contain a
triangle, then at least one of the vertices of the triangle must have degree 3
or larger.

######  Proposition 24.

If $G\in\mathcal{I}(C_{n})$, where $n\geq 4$, then the maximum degree
$\Delta(G)$ of $G$ is at most $3$ and

$n_{G}(C_{3})=g_{3}.$

###### Proof.

From Proposition 23,

$n_{G}(C_{3})=g_{3}+3g_{4}+6g_{5}+\ldots+\binom{n-2}{2}g_{n-1}.$

Let $h=g_{4}+\ldots+g_{n-1}>0$. Then $n_{G}(C_{3})\geq g_{3}+3h$. Since every
triangle, except at most one, has a vertex of degree 3 or larger, we see that
$g_{3}+h$ must be at least as large as the number of triangles less one, that
is, $g_{3}+h\geq n_{G}(C_{3})-1$. Since we have $g_{3}+h\geq g_{3}+3h-1$ and
$h$ is a nonnegative integer, the only possibility is that $h=0$, so
$g_{4}=\ldots=g_{n-1}=0$ and the maximum degree of $G$ is $3$. This also
implies that $n_{G}(C_{3})=g_{3}$. ∎

######  Proposition 25.

If $G\in\mathcal{I}(C_{n})$, where $n\geq 4$, and $G$ does not contain $C_{3}$
as a connected component, then each connected component of $G$ is either a
cycle or a graph of the form $D_{m}$ for some values of $m$.

###### Proof.

Let $G_{i}$ be one of the connected components of $G$. From Proposition 24,
the maximum degree of $G$ is at most $3$. Since $G_{i}$ is unicyclic, if the
maximum degree of $G_{i}$ is $2$, then $G_{i}$ must be a cycle.

If the maximum degree of $G_{i}$ is $3$, then $G_{i}$ must contain a triangle.
Otherwise, $G$ would need to have $C_{3}$ as a connected component so that
$n_{G}(C_{3})=g_{3}$. But this also implies that there must be exactly one
vertex of degree 3 per triangle, so there is only one such vertex in $G_{i}$.
Therefore, $G_{i}$ must be isomorphic to $D_{m}$ for some value of $m$.

Therefore, each connected component of $G$ is either a cycle or a graph of the
form $D_{m}$ for some values of $m$. ∎

##  4 The case where $n$ is not a multiple of $3$

######  Proposition 26.

If $G\in\mathcal{I}(C_{n})$ where $n$ is an odd positive number that is not a
multiple of 3, then $G=C_{n}$ or $G=D_{n}$.

###### Proof.

If $G$ is not $C_{n}$ or $D_{n}$ then $G$ is not connected, and by Proposition
20, $G=\bigcup_{i=1}^{r}G_{i}$ where the $G_{i}$ are connected unicyclic
graphs. Since $n$ is not a multiple of $3$, none of the $G_{i}$ can be
$C_{3}$, by Corollary 14.

By Proposition 25, $G$ is a disjoint union of cyclic graphs and $D_{m}$’s. But
each $D_{m}$ is independence equivalent to $C_{m}$, hence $G$ is independence
equivalent to a disjoint union of cyclic graphs. In other words, $I(G,x)$ is a
product of independence polynomials of cyclic graphs:

$I(G,x)=\prod_{i=1}^{r}I(C_{n_{i}},x).$

Now I claim that $\gcd(n_{i},n_{j})=1$ for all $i,j\in\\{1,\ldots\,r\\}$.
Suppose this was not the case, and that for some $i,j\in\\{1,\ldots\,r\\}$,
$\gcd(n_{i},n_{j})=d>1$. Then, from Proposition 7,

$-\frac{1}{2+2\cos\left(\frac{\pi}{d}\right)}=-\frac{1}{2+2\cos\left(\frac{(n_{i}/d)\pi}{n_{i}}\right)}=-\frac{1}{2+2\cos\left(\frac{(n_{j}/d)\pi}{n_{j}}\right)}$

is a root of both $I(C_{n_{i}},x)$ and $I(C_{n_{j}},x)$, and hence a repeated
root of $I(G,x)$. However, also from Proposition 7, none of the roots of
$I(G,x)=I(C_{n},x)$ are repeated, which is a contradiction. Hence,
$\gcd(n_{i},n_{j})=1$ for all $i,j\in\\{1,\ldots\,r\\}$.

Now, from Proposition 12,

$I(G,x)=\prod_{i=1}^{r}\prod_{m|n_{i}}f_{m}(x).$

For some $i,j\in\\{1,\ldots\,r\\}$, note that $f_{n_{i}}(x)$ and
$f_{n_{j}}(x)$ are included among the factors, but since
$\gcd(n_{i},n_{j})=1$, $f_{n_{i}n_{j}}(x)$ is not.

We also have

$I(G,x)=I(C_{n},x)=\prod_{m|n}f_{m}(x).$

Therefore, since $f_{n_{i}}(x)$ and $f_{n_{j}}(x)$ are factors of
$I(C_{n},x)$, it follows that $n_{i}|n$ and $n_{j}|n$, and since
$\gcd(n_{i},n_{j})=1$, $n_{i}n_{j}|n$, so $f_{n_{i}n_{j}}(x)$ is also a factor
of $I(G,x)$. This is a contradiction.

Hence, $G$ must be a connected graph and so can only be $C_{n}$ or $D_{n}$. ∎

##  5 The case where $n$ is a multiple of $3$

If $n$ is a multiple of $3$, and if $G$ is a disconnected graph which is
independence equivalent to $C_{n}$, then it turns out that $C_{3}$ must be
exactly one of the connected components of $G$. If this is not the case, then
the proof of Proposition 26 would show that $G$ must be a connected graph. On
the other hand, since the independence polynomial of $C_{n}$ does not have
repeated roots, at most one of the connected components can be $C_{3}$. If any
of the other connected components contain a triangle, then at least one of the
vertices of the triangle must have degree 3 or larger.

Let $G=\bigcup_{i=1}^{r}G_{i}$ where the $G_{i}$ are connected unicyclic
graphs. Let $g_{3,i}$ be the number of vertices of degree 3 in $G_{i}$, and
let $G_{1}=C_{3}$. Now $n_{G_{i}}(C_{3})$ is either $0$ or $1$, and if
$n_{G_{i}}(C_{3})=1$ then $g_{3,i}\geq 1$ for $i\in\\{2,\ldots,r\\}$.
Therefore, $g_{3,i}\geq n_{G_{i}}(C_{3})$ for all $i\in\\{2,\ldots,r\\}$. But
we have

$1+\sum_{i=2}^{r}n_{G_{i}}(C_{3})=n_{G}(C_{3})=g_{3}=\sum_{i=2}^{r}g_{3,i}$

and so $g_{3,i}=n_{G_{i}}(C_{3})$ for all values of $i\in\\{2,\ldots,r\\}$
except one (without loss of generality, let it be $r$), and in that case,
$g_{3,r}=n_{G_{r}}(C_{3})+1$.

For those values of $i$ where $g_{3,i}=n_{G_{i}}(C_{3})$, we have either
$g_{3,i}=n_{G_{i}}(C_{3})=0$, which means $G_{i}=C_{m}$ for some $m\geq 4$, or
$g_{3,i}=n_{G_{i}}(C_{3})=1$, which, by an argument in the proof of
Proposition 25, means that $G_{i}=D_{m}$ for some $m\geq 4$. Since $C_{m}$ and
$D_{m}$ are independence equivalent, we will not consider the case where
$G_{i}=D_{m}$, and instead replace all $D_{m}$ with $C_{m}$. Since
$I(C_{m},x)|I(C_{n},x)$, by Proposition 14, $m|n$. In particular, $m$ is odd.

As for $G_{r}$, where $g_{3,r}=n_{G_{r}}(C_{3})+1$, we have the following
cases (see Figure 4), where $m_{1},m_{2},m_{3}$ are positive integers unless
otherwise stated.

  1. 1.

$g_{3,r}=1$ and $n_{G_{r}}(C_{3})=0$. In this case, the only possibility is
$E_{m_{1},m_{2}}$, a graph where a pendant path $P_{m_{2}}$ is attached to a
cyclic graph $C_{m_{1}+3}$.

  2. 2.

$g_{3,r}=2$ and $n_{G_{r}}(C_{3})=1$. This leads us to two subcases:

    1. (a)

If both vertices of degree 3 are on the triangle, then we have
$A_{m_{1},m_{2}}$, a graph where pendant paths $P_{m_{1}}$ and $P_{m_{2}}$ are
attached to two distinct vertices of a $C_{3}$.

    2. (b)

If only one vertex of degree 3 is on the triangle, then we have
$B_{m_{1},m_{2},m_{3}}$. It is possible that $m_{1}=0$, in which case the two
vertices of degree 3 are adjacent.

$E_{m_{1},m_{2}}$:$\cdots$$C_{m_{1}+3}$$v_{1}$$v_{2}$$\cdots$$v_{m_{2}}$$A_{m_{1},m_{2}}$:$v$$v_{0}$$v_{1}$$v_{2}$$\cdots$$v_{m_{1}}$$u_{0}$$u_{1}$$u_{2}$$\cdots$$u_{m_{2}}$$B_{m_{1},m_{2},m_{3}}$:$v_{1}$$\cdots$$v_{m_{1}}$$v$$u_{1}$$u_{2}$$\cdots$$u_{m_{2}}$$w_{1}$$w_{2}$$\cdots$$w_{m_{3}}$
Figure 4: Candidate graphs for $G_{r}$

It turns out that the graph $A_{m_{1},m_{2}}$ is independence equivalent to
both $E_{m_{1},m_{2}}$ and $E_{m_{2},m_{1}}$. This can be observed using
Proposition 1. Deleting vertices $v_{1}$ from $E_{m_{1},m_{2}}$ and $u_{1}$
from $A_{m_{1},m_{2}}$ give isomorphic graphs, and deleting neighbourhoods
$N[v_{1}]$ from $E_{m_{1},m_{2}}$ and $N[u_{1}]$ from $A_{m_{1},m_{2}}$ also
give isomorphic graphs. Therefore $A_{m_{1},m_{2}}$ is independence equivalent
to $E_{m_{1},m_{2}}$. Similarly, deleting vertices $v_{1}$ from
$E_{m_{2},m_{1}}$ and $v_{1}$ from $A_{m_{1},m_{2}}$ gives isomorphic graphs,
and deleting neighbourhoods $N[v_{1}]$ from $E_{m_{2},m_{1}}$ and $N[v_{1}]$
from $A_{m_{1},m_{2}}$ also give isomorphic graphs, so $A_{m_{1},m_{2}}$ is
independence equivalent to $E_{m_{2},m_{1}}$. Therefore, we do not need to
consider graphs $E_{m_{1},m_{2}}$ for the rest of this section, as they can be
replaced with graphs $A_{m_{1},m_{2}}$.

As $G$ is independence equivalent to $C_{n}$, their independence numbers are
equal so $\alpha(G)=\alpha(C_{n})=\frac{1}{2}(n-1)$ since $n$ is odd. As
$G=\bigcup_{i=1}^{r}G_{i}$ and all the $G_{i}$ are odd cycles except for
$G_{r}$, we have

$\alpha(G)=\sum_{i=1}^{r}\alpha(G_{i})=\alpha(G_{r})+\sum_{i=1}^{r-1}\frac{|V(G_{i})|-1}{2}=\alpha(G_{r})-\frac{r-1}{2}+\sum_{i=1}^{r-1}\frac{|V(G_{i})|}{2}.$

Equating this to $\frac{1}{2}(n-1)$ gives us

$2\alpha(G_{r})=n+r-2-\sum_{i=1}^{r-1}V(G_{i})|=|V(G_{r})|+r-2.$ (1)

Since $G_{r}$ is of the form $A_{m_{1},m_{2}}$ or $B_{m_{1},m_{2},m_{3}}$, we
can calculate the independence numbers of both graphs to determine
$\alpha(G_{r})$ and obtain a bound on $r$.

######  Lemma 27.

The independence number $\alpha(A_{m_{1},m_{2}})$ is

  * •

$\frac{1}{2}(m_{1}+m_{2}+4)=\frac{1}{2}(|V(A_{m_{1},m_{2}})|+1)$ if $m_{1}$
and $m_{2}$ are both odd,

  * •

$\frac{1}{2}(m_{1}+m_{2}+3)=\frac{1}{2}|V(A_{m_{1},m_{2}})|$ if $m_{1}$ and
$m_{2}$ have different parity,

  * •

$\frac{1}{2}(m_{1}+m_{2}+2)=\frac{1}{2}(|V(A_{m_{1},m_{2}})|-1)$ if $m_{1}$
and $m_{2}$ are both even.

Also, the independence number $\alpha(B_{m_{1},m_{2},m_{3}})$ is

  * •

$\frac{1}{2}(m_{1}+m_{2}+m_{3}+5)=\frac{1}{2}(|V(B_{m_{1},m_{2},m_{3}})|+1$ if
$m_{1},m_{2},m_{3}$ are all odd,

  * •

$\frac{1}{2}(m_{1}+m_{2}+m_{3}+4)=\frac{1}{2}|V(B_{m_{1},m_{2},m_{3}})|$ if

    * –

$m_{1}$ is odd and $m_{2}$ and $m_{3}$ have different parity,

    * –

$m_{1}$ is even and $m_{2}$ and $m_{3}$ are both odd,

    * –

$m_{1},m_{2},m_{3}$ are all even,

that is, either none or exactly two of $m_{1},m_{2},m_{3}$ are odd,

  * •

$\frac{1}{2}(m_{1}+m_{2}+m_{3}+3)=\frac{1}{2}(|V(B_{m_{1},m_{2},m_{3}})|-1)$
if

    * –

$m_{1}$ is odd and $m_{2}$ and $m_{3}$ are both even,

    * –

$m_{1}$ is even and $m_{2}$ and $m_{3}$ have different parity,

that is, exactly one of $m_{1},m_{2},m_{3}$ is odd.

###### Proof.

Using Proposition 1 and the vertices labelled $v$ in Figure 4, we find that

$I(A_{m_{1},m_{2}},x)=I(P_{m_{1}+m_{2}+2},x)+xI(P_{m_{1}},x)I(P_{m_{2}},x)$

and

$I(B_{m_{1},m_{2},m_{3}},x)=\begin{cases}\begin{array}[]{l}I(C_{m_{1}+3},x)I(P_{m_{2}},x)I(P_{m_{3}},x)\\\
\qquad+xI(C_{m_{1}+2},x)I(P_{m_{2}-1},x)I(P_{m_{3}-1},x)\end{array}&m_{1}\geq
1,\\\ \begin{array}[]{l}I(C_{m_{1}+3},x)I(P_{m_{2}},x)I(P_{m_{3}},x)\\\
\qquad+xI(P_{2},x)I(P_{m_{2}-1},x)I(P_{m_{3}-1},x)\end{array}&m_{1}=0.\\\
\end{cases}$

Since we know that the degree of $I(P_{m},x)$ is $\frac{1}{2}(m+1)$ when $m$
is odd and $\frac{1}{2}m$ when $m$ is even, and the degree of $I(C_{m},x)$ is
$\frac{1}{2}(m-1)$ when $m$ is odd and $\frac{1}{2}m$ when $m$ is even, we can
calculate the degree of $I(A_{m_{1},m_{2}},x)$ and
$I(B_{m_{1},m_{2},m_{3}},x)$ for each of the cases. ∎

Substituting each of these possibilities into Equation 1, we find that
$r\in\\{1,2,3\\}$. However, as $G$ is not a connected graph, $r\neq 1$. This
leaves us with the following cases:

  * •

$r=2$: Then

    * –

$G=C_{3}\cup A_{m_{1},m_{2}}$, where $m_{1}$ and $m_{2}$ are of different
parity

    * –

$G=C_{3}\cup B_{m_{1},m_{2},m_{3}}$ where either none or exactly two of
$m_{1},m_{2},m_{3}$ are odd.

  * •

$r=3$: Then

    * –

$G=C_{3}\cup C_{m}\cup A_{m_{1},m_{2}}$, where $m_{1}$ and $m_{2}$ are both
odd, or

    * –

$G=C_{3}\cup C_{m}\cup B_{m_{1},m_{2},m_{3}}$ where $m_{1},m_{2},m_{3}$ are
all odd.

Note that $m|n$ (from Corollary 14), and $3\nmid m$, since from Proposition 7,
$I(C_{n},x)$ does not have repeated roots. Note that we can always replace
$C_{m}$ by $D_{m}$.

Thus far, we have used the fact that the independence coefficients $i_{k}(G)$
for $k\in\\{0,1,2,3\\}$ are equal to $i_{k}(C_{n})$ to obtain information
about the structure of $G$. We next try to make use of the next coefficient
$i_{4}(G)$. Now, the coefficients of the independence polynomial of the cyclic
graph $C_{n}$ and the path $P_{n}$ have been found by Hopkins and Staton [12].

######  Lemma 28.

[12] Let $i_{k}(G)$ be the number of independent sets of cardinality $k$ in
$G$. Then

$i_{k}(C_{n})=\frac{n}{k}\binom{n-k-1}{k-1}$

and

$i_{k}(P_{n})=\binom{n-k+1}{k}.$

We also need the following:

######  Lemma 29.

If $G$ is a graph such that $I(G,x)=I(C_{n},x)$ where $n\geq 5$ is odd. Then

$\displaystyle\frac{n(3n-11)}{2}$ $\displaystyle=$ $\displaystyle
e_{2}(G)+n_{G}(P_{3}\cup K_{1})-n_{G}(C_{3}\cup K_{1})$ $\displaystyle-
n_{G}(P_{4})-n_{G}(K_{1,3})+n_{G}(D_{4})+n_{G}(C_{4}).$

where $e_{2}(G)$ is the number of matchings of size $2$ in $G$ and $n_{G}(H)$
is the number of subgraphs in $G$ (not necessarily induced) which are
isomorphic to $H$.

###### Proof.

We try to find an expression for $i_{4}(G)$ using the Principle of Inclusion
and Exclusion. Any subset of 4 vertices would induce one of the subgraphs in
the table below. As each connected component of $G$ is unicyclic, we do not
need to consider subgraphs with more than $4$ edges as they would contain more
than one cycle.

Number of edges $|E(H)|$ | Subgraphs $H$
---|---
$0$ | $\overline{K}_{4}$
$1$ | $P_{2}\cup\overline{K}_{2}$
$2$ |  $2P_{2}$ and $P_{3}\cup K_{1}$
$3$ |  $C_{3}\cup K_{1}$, $P_{4}$ and $K_{1,3}$
$4$ |  $D_{4}$ and $C_{4}$

Let $\mathcal{G}_{4}$ be the collection of graphs listed in the table above.

For each edge $e\in E(G)$, let $X_{e}$ (respectively, $\overline{X_{e}}$) be
the set of induced subgraphs of $G$ with $4$ vertices and which contain (do
not contain) $e$ as an edge. Then

$\displaystyle i_{4}(G)$ $\displaystyle=$
$\displaystyle\left|\bigcap\limits_{e\in E(G)}\overline{X_{e}}\right|$
$\displaystyle=$ $\displaystyle\sum_{Y\subseteq
E(G)}(-1)^{|Y|}\left|\bigcap\limits_{e\in Y}X_{e}\right|,$

by the Principle of Inclusion and Exclusion. For each $k$, $1\leq
k\leq|E(G)|$, consider a set $Y\subseteq E(G)$ such that $|Y|=k$. Then
$\bigcap\limits_{e\in Y}X_{e}$ is the collection of graphs $H$ which have $4$
vertices and edge set $E(H)=Y$. Therefore,

$\sum_{\begin{subarray}{c}H\in\mathcal{G}_{4},\\\
|E(H)|=k\end{subarray}}n_{G}(H)=\sum_{\begin{subarray}{c}Y\subseteq E(H),\\\
|Y|=k\end{subarray}}\left|\bigcap\limits_{e\in Y}X_{e}\right|.$

Substituting this into the above expression for $i_{4}(G)$ gives us

$i_{4}(G)=\sum_{H\in\mathcal{G}_{4}}(-1)^{|E(H)|}n_{G}(H).$

Expanding this summation using the values of $n_{G}(H)$ from the table above
gives us

$\displaystyle i_{4}(G)$ $\displaystyle=$
$\displaystyle\binom{n}{4}-n\binom{n-2}{2}$
$\displaystyle+e_{2}(G)+n_{G}(P_{3}\cup K_{1})$ $\displaystyle-n_{G}(C_{3}\cup
K_{1})-n_{G}(P_{4})-n_{G}(K_{1,3})$ $\displaystyle+n_{G}(D_{4})+n_{G}(C_{4})$

because

$n_{G}(\overline{K}_{4})=\binom{n}{4},\qquad
n_{G}(P_{2}\cup\overline{K}_{2})=n\binom{n-2}{2},\qquad
n_{G}(2P_{2})=e_{2}(G).$

On the other hand, from Lemma 28,

$i_{4}(G)=i_{4}(C_{n})=\frac{n(n-5)(n-6)(n-7)}{24}.$

Comparing the two expressions for $i_{4}(G)$ gives us the required result. ∎

###  5.1 The subcase $G=C_{3}\cup A_{m_{1},m_{2}}$

We tabulate the number of each subgraph with 2 to 4 vertices for $G=C_{3}\cup
A_{m_{1},m_{2}}$. (Here, $n=|V(G)|=|V(A_{m_{1},m_{2}})|+3$.)

We will do it in detail for this subcase, and leave the remaining subcases for
the reader to fill in. The vertex labels below refer to those in Figure 4.

  * •

$2P_{2}$: This is the number of matchings of size $2$ in $C_{3}\cup
A_{m_{1},m_{2}}$. In such a matching, either the two edges are both in
$A_{m_{1},m_{2}}$ or one edge is in $C_{3}$ and one edge is in
$A_{m_{1},m_{2}}$. There are $e_{2}(A_{m_{1},m_{2}})$ matchings in the first
case. We find $e_{2}(A_{m_{1},m_{2}})$ by subtracting the number of pairs of
adjacent edges from $\binom{n-3}{2}$. Now there are $n-7$ vertices of degree
$2$ (namely, $v$, $v_{1}$ to $v_{m_{1}-1}$ and $u_{1}$ to $u_{m_{2}-1}$) in
$A_{m_{1},m_{2}}$ that correspond to a pair of adjacent edges, and two
vertices of degree $3$ ($v_{0}$ and $u_{0}$) that correspond to three pairs of
adjacent edges each. Hence there are $n-1$ pairs of adjacent edges, so
$e_{2}(A_{m_{1},m_{2}})=\binom{n-3}{2}-(n-1)$. In the second case, the number
of matchings is $|E(C_{3})||E(A_{m_{1},m_{2}})=3(n-3)$. Therefore,
$n_{G}(2P_{2})=\binom{n-3}{2}-(n-1)+3(n-3)$.

  * •

$P_{3}\cup K_{1}$: We count the number of $P_{3}$ subgraphs according to the
central vertex (the vertex of degree $2$) in $P_{3}$. Each vertex of degree
$2$ in $G$ can be the central vertex in exactly one $P_{3}$ subgraph. There
are altogether $n-4$ such vertices. There are also two vertices of degree $3$
($v_{0}$ and $u_{0}$) that can be the central vertex of three $P_{3}$
subgraphs each. Hence there are altogether $n+2$ $P_{3}$ subgraphs. For each
$P_{3}$ subgraph, there are $n-3$ vertices that are not in the $P_{3}$, and
hence can be the $K_{1}$. Therefore, $n_{G}(P_{3}\cup K_{1})=(n+2)(n-3)$.

  * •

$C_{3}\cup K_{1}$: There are two $C_{3}$ subgraphs in $G$, and for each of
them, there are $n-3$ vertices that are not in the $C_{3}$, and hence can be
the $K_{1}$. Therefore, $n_{G}(C_{3}\cup K_{1})=2(n-3)$.

  * •

$P_{4}$: This can only be a subgraph of $A_{m_{1},m_{2}}$. We count the number
of $P_{4}$ subgraphs according to the central edge (the edge incident to two
vertices of degree $2$) in $P_{4}$. The edges $vv_{0}$ and $vu_{0}$ can each
be the central edge in exactly one $P_{4}$ subgraph. The edge $v_{0}u_{0}$ can
be the central edge in three $P_{4}$ subgraphs.

If $m_{1}\geq 2$ then $v_{0}v_{1}$ can be the central edge in two $P_{4}$
subgraphs, and $v_{i-1}v_{i}$ can be the central edge in one $P_{4}$ subgraph
for $2\leq i\leq m_{1}-1$. However, if $m_{1}=1$ then we do not have any of
these subgraphs. Then number of $P_{4}$ subgraphs here is thus
$m_{1}-1+\alpha_{1}$ where

$\alpha_{1}=\begin{cases}1&\quad\text{if }m_{1}\geq 2\\\ 0&\quad\text{if
}m_{1}=1.\\\ \end{cases}$

A similar argument holds for the edges $u_{i-1}u_{i}$ for $1\leq i\leq
m_{2}-1$. Therefore,
$n_{G}(P_{4})=5+(m_{1}-1+\alpha_{1})+(m_{2}-1+\alpha_{2})=n-3+\alpha_{1}+\alpha_{2}$
since $m_{1}+m_{2}=n-6$.

  * •

$K_{1,3}$: There are only two vertices ($v_{0}$ and $u_{0}$) that can be the
vertex of degree $3$ in $K_{1,3}$, and each of them correspond to exactly one
$K_{1,3}$ subgraph.

  * •

$D_{4}$ There are only two vertices ($v_{0}$ and $u_{0}$) that can be the
vertex of degree $3$ in $D_{4}$, and each of them correspond to exactly one
$D_{4}$ subgraph.

  * •

$C_{4}$: There are none.

The results are summarised in the following table.

Subgraph $H$ | $n_{G}(H)$
---|---
$2P_{2}$ | $\begin{aligned} &e_{2}(A_{m_{1},m_{2}})+3|E(A_{m_{1},m_{2}})|\\\ =&\displaystyle\binom{n-3}{2}-(n-1)+3(n-3)\end{aligned}$
$P_{3}\cup K_{1}$ | $(n+2)(n-3)$
$C_{3}\cup K_{1}$ | $2(n-3)$
$P_{4}$ | $n-3+\alpha_{1}+\alpha_{2}$
$K_{1,3}$ | $2$
$D_{4}$ | $2$
$C_{4}$ | $0$

where

$\alpha_{i}=\begin{cases}1&\quad\text{if }m_{i}\geq 2\\\ 0&\quad\text{if
}m_{i}=1\\\ \end{cases}$

for $i\in\\{1,2\\}$.

Lemma 29 gives us $\alpha_{1}+\alpha_{2}=1$ so, without loss of generality,
$m_{1}\geq 2$ is even and $m_{2}=1$.

Applying Proposition 1 to vertex $u_{1}$, we have

$I(A_{m_{1},1},x)=I(D_{m_{1}+3},x)+xI(P_{m_{1}+2},x)=I(C_{m_{1}+3},x)+xI(P_{m_{1}+2},x),$

so the leading coefficient of $I(A_{m_{1},1},x)$ is $\frac{1}{2}m_{1}+2$.
Therefore, the leading coefficient of

$I(G,x)=I(C_{3},x)I(A_{m_{1},1},x)=(1+3x)I(A_{m_{1},1},x)$

is $\frac{3}{2}m_{1}+6$. Equating this to the leading coefficient of
$I(C_{n},x)$, which is $n$, and recalling that $n=m_{1}+7$ gives us $m_{1}=2$
or $n=9$ as the only solution. Explicit computation shows that $C_{9}$ is
independence equivalent to $C_{3}\cup A_{2,1}$. As we have seen, $A_{2,1}$ is
itself independence equivalent to $E_{1,2}$ and $E_{2,1}$. These are the
graphs $G_{a}$, $G_{b}$ and $G_{c}$ listed in Theorem 6, and are the cases
found by Oboudi [17].

###  5.2 The subcase $G=C_{3}\cup B_{m_{1},m_{2},m_{3}}$

We tabulate the number of each subgraph with 2 to 4 vertices for $G=C_{3}\cup
B_{m_{1},m_{2},m_{3}}$. (Here, $n=|V(G)|=|V(B_{m_{1},m_{2},m_{3}})|+3$.)

Subgraph $H$ | $n_{G}(H)$
---|---
$2P_{2}$ | $\begin{aligned} &e_{2}(B_{m_{1},m_{2},m_{3}})+3|E(B_{m_{1},m_{2},m_{3}})|\\\ =&\displaystyle\binom{n-3}{2}-(n-1)+3(n-3)\end{aligned}$
$P_{3}\cup K_{1}$ | $(n+2)(n-3)$
$C_{3}\cup K_{1}$ | $2(n-3)$
$P_{4}$ | $n-4+\alpha_{1}+\alpha_{2}+\alpha_{3}$
$K_{1,3}$ | $2$
$D_{4}$ | $1$
$C_{4}$ | $0$

where

$\alpha_{1}=\begin{cases}1&\quad\text{if }m_{1}=0\\\ 0&\quad\text{if
}m_{1}\geq 1\\\ \end{cases}$

and

$\alpha_{i}=\begin{cases}1&\quad\text{if }m_{i}\geq 2\\\ 0&\quad\text{if
}m_{i}=1\\\ \end{cases}$

for $i\in\\{2,3\\}$.

Lemma 29 gives us $\alpha_{1}+\alpha_{2}+\alpha_{3}=1$ so either $m_{1}=0$ and
$m_{2}=m_{3}=1$ or, without loss of generality, $m_{1}\geq 1$, $m_{2}\geq 2$
and $m_{3}=1$. The former case gives us $G=C_{3}\cup B_{0,1,1}$, and explicit
computation of the independence polynomial shows that it is indeed
independence equivalent to $C_{9}$. This is the graph $G_{d}$ mentioned in
Theorem 6.

In the latter case, since $m_{3}=1$ is odd, $m_{1}$ and $m_{2}$ must have
different parity. Now

$\displaystyle I(B_{m_{1},m_{2},1},x)$ $\displaystyle=$ $\displaystyle
I(D_{m_{1}+m_{2}+4},x)+xI(D_{m_{1}+3},x)I(P_{m_{2}},x)$ $\displaystyle=$
$\displaystyle I(C_{m_{1}+m_{2}+4},x)+xI(C_{m_{1}+3},x)I(P_{m_{2}},x)$

Suppose $m_{1}$ is odd and $m_{2}$ is even. Then the leading coefficient of
$I(B_{m_{1},m_{2},1},x)$ is $2(\frac{1}{2}m_{2}+1)=m_{2}+2$, which is even.
Therefore, the leading coefficient of

$I(G,x)=I(C_{3},x)I(B_{m_{1},m_{2},1},x)$

is also even (in fact, it is $3m_{2}+6$). However, the leading coefficient of
$I(C_{n},x)$ is $n$, an odd number. Therefore, this cannot be the case.

Suppose $m_{1}$ is even and $m_{2}$ is odd. Then the leading coefficient of
$I(B_{m_{1},m_{2},1},x)$ is $m_{1}+3$ so the leading coefficient of $I(G,x)$
is $3(m_{1}+3)$. But this has to be equal to the leading coefficient of
$I(C_{n},x)$, which is $n=m_{1}+m_{2}+8$. Therefore, $m_{2}=2m_{1}+1$ and
$n=3m_{1}+9$.

We have

$\displaystyle I(B_{m_{1},m_{2},1},x)$ $\displaystyle=$ $\displaystyle
I(C_{m_{1}+m_{2}+4},x)+xI(C_{m_{1}+3},x)I(P_{m_{2}},x)$ $\displaystyle=$
$\displaystyle\left(1+\ldots+(m_{1}+m_{2}+4)x^{\frac{m_{1}+m_{2}+3}{2}}\right)$
$\displaystyle+x\left(1+\ldots+\frac{(m_{1}+3)^{3}-(m_{1}+3)}{24}x^{\frac{m_{1}}{2}}+(m_{1}+3)x^{\frac{m_{1}+2}{2}}\right)$
$\displaystyle\left(1+\ldots+\frac{(m_{2}+3)(m_{2}+1)}{8}x^{\frac{m_{2}-1}{2}}+x^{\frac{m_{2}+1}{2}}\right)$

and therefore the coefficient of $x^{\frac{1}{2}(m_{1}+m_{2}+3)}$ in
$I(B_{m_{1},m_{2},1},x)$ is

$\displaystyle
m_{1}+m_{2}+4+\frac{(m_{1}+3)^{3}-(m_{1}+3)}{24}+\frac{(m_{1}+3)(m_{2}+3)(m_{2}+1)}{8}$
$\displaystyle=$
$\displaystyle\frac{13m_{1}^{3}+93m_{1}^{2}+287m_{1}+279}{24}.$

The coefficient of $x^{\frac{1}{2}(m_{1}+m_{2}+5)}=x^{\frac{1}{2}}(n-3)$ in
$I(G,x)=I(C_{3},x)I(B_{m_{1},m_{2},1},x)$ is thus

$3\cdot\frac{13m_{1}^{3}+81m_{1}^{2}+230m_{1}+216}{24}+1\cdot(m_{1}+3).$

This has to be equal to the coefficient of $x^{\frac{1}{2}}(n-3)$ in
$I(C_{n},x)$ which is

$\frac{n^{3}-n}{24}=\frac{(3m_{1}+9)^{3}-(3m_{1}+9)}{24}$

. This ultimately simplifies to

$m_{1}^{3}-m_{1}=0.$

Since $m_{1}$ is an even integer, the only possibility is $m_{1}=0$,
contradicting the supposition that $m_{1}\geq 1$.

###  5.3 The subcase $G=C_{3}\cup C_{m}\cup A_{m_{1},m_{2}}$

We tabulate the number of each subgraph with 2 to 4 vertices for $G=C_{3}\cup
C_{m}\cup A_{m_{1},m_{2}}$. Since $m$ is an odd number not divisible by $3$,
$m\geq 5$. Also, $m_{1}$ and $m_{2}$ are both odd. (Here,
$n=|V(G)|=|V(A_{m_{1},m_{2}})|+m+3$.)

Subgraph $H$ | $n_{G}(H)$
---|---
$2P_{2}$ | $\begin{aligned} &e_{2}(C_{m})+e_{2}(A_{m_{1},m_{2}})\\\ &+3m+(3+m)|E(A_{m_{1},m_{2}})|\\\ =&\displaystyle\frac{m(m-3)}{2}+\displaystyle\binom{n-3-m}{2}-(n-1-m)\\\ &+3m+(3+m)(n-3-m)\end{aligned}$
$P_{3}\cup K_{1}$ | $(n+2)(n-3)$
$C_{3}\cup K_{1}$ | $2(n-3)$
$P_{4}$ | $n-3+\alpha_{1}+\alpha_{2}$
$K_{1,3}$ | $2$
$D_{4}$ | $2$
$C_{4}$ | $0$

where

$\alpha_{i}=\begin{cases}1&\quad\text{if }m_{i}\geq 3\\\ 0&\quad\text{if
}m_{i}=1\\\ \end{cases}$

for $i\in\\{1,2\\}$.

Lemma 29 gives us $\alpha_{1}+\alpha_{2}=1$ so, without loss of generality,
$m_{1}\geq 3$ is odd and $m_{2}=1$.

Applying Proposition 1 to vertex $u_{1}$, we have

$\displaystyle I(A_{m_{1},1},x)$ $\displaystyle=$ $\displaystyle
I(D_{m_{1}+3},x)+xI(P_{m_{1}+2},x)$ $\displaystyle=$ $\displaystyle
I(C_{m_{1}+3},x)+xI(P_{m_{1}+2},x)$ $\displaystyle=$
$\displaystyle\left(1+\ldots+2x^{\frac{m_{1}+3}{2}}\right)+x\left(1+\ldots+\binom{\frac{m_{1}+5}{2}}{2}x^{\frac{m_{1}+1}{2}}+x^{\frac{m_{1}+3}{2}}\right)$
$\displaystyle=$ $\displaystyle
1+\ldots+\left(2+\frac{(m_{1}+5)(m_{1}+3)}{8}\right)x^{\frac{m_{1}+3}{2}}+x^{\frac{m_{1}+5}{2}}$

Comparing the leading coefficients of $I(C_{n},x)$ and

$I(G,x)=I(C_{3},x)I(C_{m},x)I(A_{m_{1},1},x),$

gives us $n=3m$.

Comparing the coefficients of $x^{\frac{n-3}{2}}$ in $I(C_{n},x)$ and $I(G,x)$
gives us

$m+\frac{m^{3}-m}{8}+3m\left(2+\frac{(m_{1}+5)(m_{1}+3)}{8}\right)=\frac{n^{3}-n}{24}.$

Substituting $n=3m$ and $m_{1}=n-m-7$, this equation reduces to

$(m-5)(m-4)=0.$

Since $m$ is odd, $m=5$ is the only solution. This gives us $G=C_{3}\cup
C_{5}\cup A_{3,1}$. Explicit computation shows that $G$ is indeed independence
equivalent to $C_{15}$. As we have seen, $A_{3,1}$ is itself independence
equivalent to $E_{1,3}$ and $E_{3,1}$. These are the graphs $G^{\prime}_{a}$,
$G^{\prime}_{b}$ and $G^{\prime}_{c}$ listed in Theorem 6, and were first
discovered by Beaton, Brown and Cameron [6].

###  5.4 The subcase $G=C_{3}\cup C_{m}\cup B_{m_{1},m_{2},m_{3}}$

We tabulate the number of each subgraph with 2 to 4 vertices and at most 4
edges for $G=C_{3}\cup C_{m}\cup B_{m_{1},m_{2},m_{3}}$. (Here,
$n=|V(G)|=|V(B_{m_{1},m_{2},m_{3}})|+m+3$.)

Subgraph $H$ | $n_{G}(H)$
---|---
$2P_{2}$ | $\begin{aligned} &e_{2}(C_{m})+e_{2}(B_{m_{1},m_{2},m_{3}})\\\ &+3m+(3+m)|E(B_{m_{1},m_{2},m_{3}})|\\\ =&\displaystyle\frac{m(m-3)}{2}+\displaystyle\binom{n-3-m}{2}-(n-1-m)\\\ &+3m+(3+m)(n-3-m)\end{aligned}$
$P_{3}\cup K_{1}$ | $(n+2)(n-3)$
$C_{3}\cup K_{1}$ | $2(n-3)$
$P_{4}$ | $n-4+\alpha_{1}+\alpha_{2}+\alpha_{3}$
$K_{1,3}$ | $2$
$D_{4}$ | $1$
$C_{4}$ | $0$

where

$\alpha_{1}=\begin{cases}1&\quad\text{if }m_{1}=0\\\ 0&\quad\text{if
}m_{1}\geq 1\\\ \end{cases}$

and

$\alpha_{i}=\begin{cases}1&\quad\text{if }m_{i}\geq 2\\\ 0&\quad\text{if
}m_{i}=1\\\ \end{cases}$

for $i\in\\{2,3\\}$.

Equating $i_{4}(C_{n})$ and $i_{4}(G)$ gives us
$\alpha_{1}+\alpha_{2}+\alpha_{3}=1$ so either $m_{1}=0$ and $m_{2}=m_{3}=1$
or, without loss of generality, $m_{1}\geq 1$, $m_{2}\geq 2$ and $m_{3}=1$.
The former case is impossible as the total number of vertices of $G$ is even
whereas the total number of vertices of $C_{n}$ is odd. In the latter case,
$m_{1}$ and $m_{2}$ are both odd.

Applying Proposition 1 to vertex $w_{1}$, we have

$\displaystyle I(B_{m_{1},m_{2},1},x)$ $\displaystyle=$ $\displaystyle
I(D_{m_{1}+m_{2}+4},x)+xI(D_{m_{1}+3},x)I(P_{m_{2}},x)$ $\displaystyle=$
$\displaystyle I(C_{m_{1}+m_{2}+4},x)+xI(C_{m_{1}+3},x)I(P_{m_{2}},x)$
$\displaystyle=$
$\displaystyle\left(1+\ldots+2x^{\frac{m_{1}+m_{2}+4}{2}}\right)$
$\displaystyle+x\left(1+\ldots+2x^{\frac{m_{1}+3}{2}}\right)\left(1+\ldots+x^{\frac{m_{2}+1}{2}}\right)$
$\displaystyle=$ $\displaystyle 1+\ldots+2x^{\frac{m_{1}+m_{2}+6}{2}}$

The leading coefficient of $I(B_{m_{1},m_{2},1},x)$ is $2$, an even number.
Therefore, the leading coefficient of

$I(G,x)=I(C_{3},x)I(C_{m},x)I(B_{m_{1},m_{2},1},x)$

is also even (in fact, it is $6m$). However, the leading coefficient of
$I(C_{n},x)$ is $n$, an odd number. This contradiction means that this case is
impossible.

This concludes the proof of Theorem 6. In Section 4, it was shown, for odd $n$
that were not multiples of $3$, that $\mathcal{I}(C_{n})=\\{C_{n},D_{n}\\}$.
In Section 5, we searched for graphs in $\mathcal{I}(C_{n})$ that are not
isomorphic to $C_{n}$ or $D_{n}$, leading to the four subcases. Subcases 5.1
and 5.2 turned up graphs in $\mathcal{I}(C_{9})$, while Subcase 5.3 turned up
graphs in $\mathcal{I}(C_{15})$. Subcase 5.4 turned out to be impossible.

## References

  * [1] S. Akbari, S. Alikhani and Y.-H. Peng  “Characterization of graphs using domination polynomials”  In _Eur. J. Comb._ 31.7, 2010, pp. 1714–1724  DOI: https://doi.org/10.1016/j.ejc.2010.03.007
  * [2] S. Alikhani  “On the $\mathcal{D}$-equivalence class of a graph”  In _Bull. Georg. Natl. Acad. Sci._ 6.1, 2016, pp. 43–46
  * [3] S. Alikhani and Y.-H. Peng  “Independence roots and independence fractals of certain graphs”  In _J. Appl. Math. Comput._ 36.1–2, 2011, pp. 89–100  DOI: https://doi.org/10.1007/s12190-010-0389-4
  * [4] R.A. Bari  “Chromatically equivalent graphs”  In _Graphs and Combinatorics_ 406 Springer, 1974, pp. 186–200  DOI: https://doi.org/10.1007/BFb0066441
  * [5] I. Beaton and J.I. Brown  “The domination equivalence classes of paths”  In _Australas. J. Combin._ 73.2, 2019, pp. 291–312
  * [6] I. Beaton, J.I. Brown and B. Cameron  “Independence equivalence classes of paths and cycles”  In _Australas. J. Combin._ 75.1, 2019, pp. 127–145
  * [7] C.Y. Chao and E.G. Whitehead  “On chromatic equivalence of graphs”  In _Theory and Applications of Graphs_ 642 Springer, 1978, pp. 121–131  DOI: https://doi.org/10.1007/BFb0070369
  * [8] G.L. Chia and C.-K. Ho  “Chromatic equivalence classes of some families of complete tripartite graphs”  In _Bull. of the Malaysian Math. Sciences Soc._ 37.3, 2014, pp. 614–646
  * [9] L.M. Chism  “On independence polynomials and independence equivalence in graphs”, 2009
  * [10] F.M. Dong, K.M. Koh and K.L. Teo  “Chromatic Polynomials And Chromaticity Of Graphs”  World Scientific, 2005  DOI: https://doi.org/10.1142/5814
  * [11] C. Hoede and X. Li  “Clique polynomials and independent set polynomials of graphs”  In _Discrete Math._ 125.1–3, 1994, pp. 219–228  DOI: https://doi.org/10.1016/0012-365X(94)90163-5
  * [12] G. Hopkins and W. Staton  “Some identities arising from the Fibonacci numbers of certain graphs”  In _Fibonacci Quart._ 22.3, 1984, pp. 255–258
  * [13] S. Jahari and S. Alikhani  “On $\mathcal{D}$-equivalence classes of some graphs”  In _Bull. Georg. Natl. Acad. Sci._ 10.1, 2016, pp. 12–19
  * [14] G.-C. Lau and H. Zhang  “Some chromatic equivalence classes of complete multipartite graphs”  In _Utilitas Mathematica_ 105, 2017, pp. 75–85
  * [15] D.H. Lehmer  “A note on trigonometric algebraic numbers”  In _Amer. Math. Monthly_ 40.3, 1933, pp. 165–166  DOI: https://doi.org/10.2307/2301023
  * [16] V.E. Levit and E. Mandrescu  “The independence polynomial of a graph – a survey”  In _Proceedings of the 1st International Conference on Algebraic Informatics. Held in Thessaloniki, October 20-23, 2005_ Thessaloniki: Aristotle Univ., 2005, pp. 233–254
  * [17] M.R. Oboudi  “Some results on the independence polynomial of unicyclic graphs”  In _Discuss. Math. Graph Theory_ 38.2, 2018, pp. 515–524  DOI: https://doi.org/10.7151/dmgt.2022
  * [18] W. Watkins and J. Zeitlin  “The minimal polynomial of $\cos(2\pi/n)$”  In _Amer. Math. Monthly_ 100.5, 1993, pp. 471–474  DOI: https://doi.org/10.2307/2324301
  * [19] G.C. Wingard  “Properties and applications of the Fibonacci polynomial of a graph”, 1995