# Irredundance Trees of Diameter $\mathbf{3}$

C.M. Mynhardt
Department of Mathematics and Statistics
University of Victoria, Victoria, BC, Canada
<EMAIL_ADDRESS>Supported by the Natural Sciences and Engineering Research
Council of Canada. A. Roux
Department of Mathematical Sciences
Stellenbosch University, Stellenbosch, South Africa
<EMAIL_ADDRESS>This work is based on research supported by the National
Research Foundation of South Africa (Grant number: 121931)

###### Abstract

A set $D$ of vertices of a graph $G=(V,E)$ is irredundant if each non-isolated
vertex of $G[D]$ has a neighbour in $V-D$ that is not adjacent to any other
vertex in $D$. The upper irredundance number $\operatorname{IR}(G)$ is the
largest cardinality of an irredundant set of $G$; an
$\operatorname{IR}(G)$-set is an irredundant set of cardinality
$\operatorname{IR}(G)$.

The $\operatorname{IR}$-graph of $G$ has the $\operatorname{IR}(G)$-sets as
vertex set, and sets $D$ and $D^{\prime}$ are adjacent if and only if
$D^{\prime}$ can be obtained from $D$ by exchanging a single vertex of $D$ for
an adjacent vertex in $D^{\prime}$. An $\operatorname{IR}$-tree is an
$\operatorname{IR}$-graph that is a tree. We characterize
$\operatorname{IR}$-trees of diameter $3$ by showing that these graphs are
precisely the double stars $S(2n,2n)$, i.e., trees obtained by joining the
central vertices of two disjoint stars $K_{1,2n}$.

Keywords: Irredundance; Reconfiguration problem; $\operatorname{IR}$-graph;
$\operatorname{IR}$-tree

AMS Subject Classification Number 2010: 05C69

##  1 Introduction

Reconfiguration problems are concerned with determining conditions under which
a feasible solution to a given problem can be transformed into another one via
a sequence of feasible solutions in such a way that any two consecutive
solutions are adjacent according to a specified adjacency relation. The
solutions form the vertex set of the associated reconfiguration graph, two
vertices being adjacent if one solution can be obtained from the other in a
single step. Typical questions about the reconfiguration graph concern its
structure (connectedness, Hamiltonicity, diameter), realizability (which
graphs can be realized as a specific type of reconfiguration graph), and
algorithmic properties (finding a shortest path between two solutions).

Domination reconfiguration problems involving dominating sets of different
cardinalities were introduced by Haas and Seyffarth [9] and also studied in,
for example, [1, 10, 11, 16]. Two variations of domination reconfiguration
problems involving only minimum-cardinality dominating sets were introduced by
Lakshmanan and Vijayakumar [13] in 2010, and Fricke, Hedetniemi, Hedetniemi,
and Hutson [8] in 2011, respectively, and also studied in [2, 5, 6, 7, 13, 17,
18, 19, 20]. A survey of results concerning the reconfiguration of colourings
and dominating sets in graphs can be found in [14].

The study of upper irredundance graphs, or $\operatorname{IR}$-graphs, was
mentioned as an open problem in [17] and initiated by the current authors in
[15]. There we showed that all disconnected graphs, but not all connected
graphs, are realizable as $\operatorname{IR}$-graphs, and that the smallest
non-complete $\operatorname{IR}$-tree is the double star $S(2,2)$ (see Figure
1). Here we characterize $\operatorname{IR}$-trees of diameter $3$ by showing
that these graphs are precisely the _double stars_ $S(2n,2n)$, i.e., trees
obtained by joining the central vertices of two disjoint stars $K_{1,2n}$. We
need a number of results from [15], which we state in Section 3 after
providing some definitions in Section 2. In Section 4 we construct a class of
graphs $G_{n},\ n\geq 1$, and show that $\operatorname{IR}(G_{n})\cong
S(2n,2n)$. We show in Section 5 that these double stars are the only
$\operatorname{IR}$-trees of diameter $3$. We close by mentioning open
problems and conjectures in Section 6.

##  2 Definitions

We follow the notation of [3] for general concepts, and that of [12] for
domination related concepts not defined here. For a graph $G=(V,E)$ and
vertices $u,v\in V$, we use the notation $u\sim v$ ($u\nsim v$, respectively)
to denote that $u$ is adjacent (nonadjacent, respectively) to $v$. For a set
$D\subseteq V$ and a vertex $v\in D$, a $D$-_private neighbour_ of $v$ is a
vertex $v^{\prime}$ that is dominated by $v$ (i.e., $v^{\prime}=v$ or
$v^{\prime}\sim v$) but by no vertex in $D-\\{v\\}$. The set of $D$-private
neighbours of $v$ is called the _private neighbourhood of_ $v$ _with respect
to_ $D$ and denoted by $\operatorname{PN}(v,D)$.

The concept of irredundance was introduced by Cockayne, Hedetniemi and Miller
[4] in 1978. A set $D\subseteq V$ is _irredundant_ if
$\operatorname{PN}(v,D)\neq\varnothing$ for each $v\in D$. The _upper
irredundance number_ $\operatorname{IR}(G)$ is the largest cardinality of an
irredundant set of $G$. An $\operatorname{IR}$-_set_ of $G$, or an
$\operatorname{IR}(G)$-_set_ , is an irredundant set of
cardinality$~{}\operatorname{IR}(G)$. Let $D$ be an irredundant set of $G$.
For $v\in D$, it is possible that $v\in\operatorname{PN}(v,D)$; this happens
if and only if $v$ is isolated in the subgraph $G[D]$ induced by $D$. If
$u\in\operatorname{PN}(v,D)$ and $u\neq v$, then $u\in V-D$; in this case $u$
is an _external_ $D$-_private neighbour of_ $v$. The set of external
$D$-private neighbours of $v$ is denoted by $\operatorname{EPN}(v,D)$. An
isolated vertex of $G[D]$ may or may not have external $D$-private neighbours,
but if $v$ has positive degree in $G[D]$, then
$\operatorname{EPN}(v,D)\neq\varnothing$.

As defined in [15], the _$\operatorname{IR}$ -graph _$G(\operatorname{IR})$__
of _$G$_ is the graph whose vertex set consists of the
$\operatorname{IR}(G)$-sets, where sets $D$ and $D^{\prime}$ are adjacent if
and only if there exist vertices $u\in D$ and $v\in D^{\prime}-\\{u\\}$ such
that $uv\in E(G)$ and $D^{\prime}=(D-\\{u\\})\cup\\{v\\}$. We shorten the
expression $D^{\prime}=(D-\\{u\\})\cup\\{v\\}$ to
$D\overset{uv}{\sim}D^{\prime}$, and also write $D\sim_{H}D^{\prime}$ or
$D\overset{uv}{\sim}_{G(\operatorname{IR})}D^{\prime}$ to show that $D$ and
$D^{\prime}$ are adjacent in $G(\operatorname{IR})$. When
$D\overset{uv}{\sim}D^{\prime}$, we say that $v$ is _swapped into_ and $u$ is
_swapped out of_ the $\operatorname{IR}(G)$-set, or simply that $u$ and $v$
are _swapped_. To prove that a given graph $H$ is an
$\operatorname{IR}$-graph, one needs to construct a graph $G$ such that
$G(\operatorname{IR})\cong H$. Figure 1 shows a graph $G^{\prime}$ and and its
$\operatorname{IR}$-graph $G^{\prime}(\operatorname{IR})\cong S(2,2)$; the six
$\operatorname{IR}(G)$-sets are given in Lemma 5 below.

Figure 1: The graph
$G^{\prime}=G[\\{x_{1},x_{2},x_{3},x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime}\\}]$
and the double star $S(2,2)$ induced by the
$\operatorname{IR}(G^{\prime})$-sets, as described in Lemma 5

##  3 Previous Results

We need the following results from Mynhardt and Roux [15]. We weakly partition
an $\operatorname{IR}$-set $X$ into subsets $X^{\operatorname{EPN}}$ and
$X^{\mathrm{iso}}$ (one of which may be empty), where each vertex in
$X^{\mathrm{iso}}$ is isolated in $G[X]$ and each vertex in
$X^{\operatorname{EPN}}$ has at least one external private neighbour. (This
partition is not necessarily unique. Isolated vertices of $G[X]$ with external
private neighbours can be allocated arbitrarily to $X^{\operatorname{EPN}}$ or
$X^{\mathrm{iso}}$.) For each $y\in X^{\operatorname{EPN}}$, let
$y^{\prime}\in\operatorname{EPN}(y,X)$ and define
$Y^{\prime}=\\{y^{\prime}:y\in X^{\operatorname{EPN}}\\}$. Let
$X^{\prime}=(X-X^{\operatorname{EPN}})\cup\\{Y^{\prime}\\}$; note that
$|X|=|X^{\prime}|$. We call $X^{\prime}$ a _flip-set_ of $X$, or to be more
precise, the _flip-set_ of $X$ _using_ $Y^{\prime}$.

The first result from [15] allows us to find more $\operatorname{IR}$-sets by
using external private neighbours in a given $\operatorname{IR}$-set.

###### Theorem 1

_[15]_ If $X$ is an $\operatorname{IR}(G)$-set, then so is any flip-set of
$X$. In particular, if $X^{\prime}$ is the flip-set __ of $X$ using
$Y^{\prime}$, and $y^{\prime}\in Y^{\prime}$ belongs to
$\operatorname{EPN}(y,X)$, then
$y\in\operatorname{EPN}(y^{\prime},X^{\prime})$.

The following lemmas from [15] are important tools in the study of
$\operatorname{IR}$-trees.

###### Lemma 2

_[15]_ If the $\operatorname{IR}$-graph $H$ of $G$ is connected and $X$ is an
$\operatorname{IR}(G)$-set such that

  1. $(i)$

$G[X]$ has exactly one edge, or

  2. $(ii)$

$X$ is independent but at least two vertices have $X$-external private
neighbours,

then $H$ contains an induced $C_{4}$.

###### Lemma 3

_[15]_ Let $G$ be a graph, all of whose $\operatorname{IR}$-sets are
independent. If the $\operatorname{IR}$-graph $H$ of $G$ is connected and has
order at least three, then $H$ contains a triangle or an induced $C_{4}$.

###### Lemma 4

_[15]_ If the $\operatorname{IR}$-graph $H$ of $G$ is connected and $X$ is an
$\operatorname{IR}(G)$-set that contains $k\geq 3$ vertices of positive degree
in $G[X]$, or with $X$-external private neighbours, then
$\operatorname{diam}(H)\geq k$.

The last lemma in this section is adapted from Lemma 5.1 of [15].

###### Lemma 5

Let $H$ be an $\operatorname{IR}$-tree of a graph $G$ such that
$\operatorname{diam}(H)=3$. Suppose $X=\\{x_{1},...,x_{r}\\}$ is an
$\operatorname{IR}(G)$-set such that exactly three vertices, say
$x_{1},x_{2},x_{3}$, have positive degree in $G[X]$. For $i=1,2,3$, let
$x_{i}^{\prime}\in\operatorname{EPN}(x_{i},X)$ and let $X^{\prime}$ be the
flip-set of $X$ using $\\{x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime}\\}$.
Note that $d_{H}(X,X^{\prime})=3$ and assume without loss of generality that
$P:(X=X_{0},X_{1},X_{2},X_{3}=X^{\prime})$, where

$X_{1}=\\{x_{1}^{\prime},x_{2},...,x_{r}\\}\ \ \text{and\ \
}X_{2}=\\{x_{1}^{\prime},x_{2}^{\prime},x_{3},...,x_{r}\\},$

is an $X$-$X^{\prime}$ geodesic in $H$. Then

  1. $(i)$

$G[\\{x_{1},x_{2},x_{3},x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime}\\}]$ is
the graph $G^{\prime}$ shown in Figure 1; in particular, the sets $X_{1}$ and
$X_{2}$ are independent,

  2. $(ii)$

the set $U=\\{x_{1},x_{1}^{\prime},x_{2},x_{4},...,x_{r}\\}$ is an
$\operatorname{IR}(G)$-set such that $x_{3}\in\operatorname{EPN}(x_{1},U),\
x_{3}^{\prime}\in\operatorname{EPN}(x_{1}^{\prime},U)$ and
$x_{2}^{\prime}\in\operatorname{EPN}(x_{2},U)$,

  3. $(iii)$

denoting the flip-set
$\\{x_{2}^{\prime},x_{3}^{\prime},x_{3},x_{4},...,x_{r}\\}$ of $U$ using
$\\{x_{3},x_{3}^{\prime},x_{2}^{\prime}\\}$ by $U^{\prime}$, the graph induced
by $\\{X,X_{1},X_{2},X^{\prime},U,U^{\prime}\\}$ is $S(2,2)$, with edges as
shown in Figure 1.

We need a few more definitions based on Lemma 5. Observe that
$C=(x_{1},x_{3},x_{3}^{\prime},x_{1}^{\prime},x_{1})$ is an induced $4$-cycle
in $G$, with $x_{1},x_{3}\in X$ and $x_{1}^{\prime},x_{3}^{\prime}\in
X^{\prime}$. Significantly, $x_{1}^{\prime}$ and $x_{3}$ have degree $2$ in
$G[\\{x_{1},x_{2},x_{3},x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime}\\}]$,
while $x_{1}$ and $x_{3}^{\prime}$ have degree $3$. The set $U$ is obtained
from $X$ by replacing (not swapping) $x_{3}$ with the vertex $x_{1}^{\prime}$
that is nonadjacent to it in $C$; imagine a token on $x_{3}$ skipping to
$x_{1}^{\prime}$. We say that $U$ is _the skip-set of_ $X$ _replacing_ $x_{3}$
_with_ $x_{1}^{\prime}$, or simply $U$ is _a skip-set of_ $X$ when the
vertices involved are obvious. (Thus $X$ is the skip-set of $U$ replacing
$x_{1}^{\prime}$ with $x_{3}$.) The set $U^{\prime}$ is not only a flip-set of
$U$, but also the skip-set of $X^{\prime}$ replacing $x_{1}^{\prime}$ with
$x_{3}$. We call the set $\mathcal{X}=\\{X,X^{\prime},U,U^{\prime}\\}$ of
these four related $\operatorname{IR}(G)$-sets, which are leaves of $H$, a
$4$-_cluster_.

##  4 Construction of a graph $G_{n}$ such that $G_{n}(\operatorname{IR})\cong
S(2n,2n)$

In this section we construct a class of graphs $G_{n}$, where $n\geq 1$, such
that $\operatorname{IR}(G_{n})=2n+1$ and $G_{n}(\operatorname{IR})$ is the
double star $S(2n,2n)$.

###  4.1 Construction of $G_{n}$

See Figure 2 for the case $n=3$. The vertex set of $G_{n}$ consists of five
disjoint subsets $\\{u,v\\},\ A,B,C,D$, where $A=\\{a_{1},...,a_{n}\\},\
B=\\{b_{1},...,b_{n}\\},\ C=\\{c_{1},...,c_{n}\\}$ and
$D=\\{d_{1},...,d_{n}\\}$. Join $u$ to each vertex in $A\cup\\{v\\}$, and join
$v$ to each vertex in $B$. Hence, ignoring (for the moment) the edges between
$A$ and $B$, the subgraph induced by $A\cup B\cup\\{u,v\\}$ is isomorphic to
the double star $S(n,n)$. Let $M=\\{a_{i}b_{i}:i=1,...,n\\}$ and join the
vertices in $A$ to the vertices in $B$ so that the subgraph induced by $A\cup
B$ is isomorphic to the bipartite graph $K_{n,n}-M$ with partite sets $A$ and
$B$. Finally, for each $i=1,...,n$, let $S_{i}=\\{a_{i},b_{i},c_{i},d_{i}\\}$
and add edges such that the subgraph induced by each $S_{i}$ is the $4$-cycle
$(a_{i},c_{i},b_{i},d_{i},a_{i})$.

Figure 2: A graph $G_{3}$ such that $G_{3}(\operatorname{IR})\cong S(6,6)$

###  4.2 The upper irredundance number of $G_{n}$

Since $C\cup D\cup\\{u\\}$ and $C\cup D\cup\\{v\\}$ are independent sets of
cardinality $2n+1$, $\operatorname{IR}(G_{n})\geq 2n+1$. We show that
$\operatorname{IR}(G_{n})=2n+1$. Let $X$ be any irredundant set of $G_{n}$. We
prove that $|X|\leq 2n+1$ by proving the following two statements:

  1. (a)

$|S_{i}\cap X|\leq 2$ for each $i$;

  2. (b)

if $\\{u,v\\}\subseteq X$, then $|X|\leq 2n$ for all $n\geq 1$.

Proof of (a). Note that if, without loss of generality,
$\\{a_{i},b_{i},c_{i}\\}\subseteq X$ or $\\{a_{i},c_{i},d_{i}\\}\subseteq X$,
then $\operatorname{PN}(c_{i},X)=\varnothing$, a contradiction.
$\blacklozenge$

Proof of (b). Assume that $\\{u,v\\}\subseteq X$. Note that
$\operatorname{PN}(u,\\{u,v\\})=A$ and $\operatorname{PN}(v,\\{u,v\\})=B$.
Hence, if $n=1$, then $X\cap S_{1}=\varnothing$ and $X=\\{u,v\\}$. Assume that
$n\geq 2$. Suppose $a_{i}\in X$. Then
$\operatorname{PN}(a_{i},X)\subseteq\\{c_{i},d_{i}\\}$. Moreover,
$\operatorname{PN}(v,X)=\\{b_{i}\\}$. This implies that
$\\{b_{i},c_{i},d_{i}\\}\cap X=\varnothing$. Since $G_{n}[A\cup B]\cong
K_{n,n}-M$, any vertex $a_{j}$, where $j\neq i$, is adjacent to $b_{i}$.
Therefore, the private neighbourhood property of $v$ implies that $A\cap
X=\\{a_{i}\\}$. Similarly, if $b_{j}\in X$, then
$\operatorname{PN}(u,X)=\\{a_{j}\\},$ $\\{a_{j},c_{j},d_{j}\\}\cap
X=\varnothing$ and $B\cap X=\\{b_{j}\\}$.

If $\\{a_{i},b_{j}\\}\subseteq X$ for some $i$ and $j$ (where, as shown above,
$i\neq j$), then possibly $\\{c_{k},d_{k}\\}\cap X\neq\varnothing$ for some
(or all) $k\notin\\{i,j\\}$. Necessarily, $|X|\leq 4+2(n-2)=2n$. On the other
hand, if $|X\cap(A\cup B)|=1$, say $X\cap(A\cup B)=\\{a_{i}\\}$, then
$X\cap\\{c_{j},d_{j}\\}=\varnothing$ for at least one $j\neq i$ to ensure that
$\operatorname{PN}(u,X)\neq\varnothing$. Therefore $|X|\leq 3+2(n-2)=2n-1$.

Suppose $X\cap(A\cup B)=\varnothing$. Then $\\{c_{i},d_{i}\\}\cap
X=\varnothing$ for at least one $i$ to ensure that $\operatorname{PN}(u,X)$
and $\operatorname{PN}(v,X)$ are nonempty. Again we have that $|X|\leq
2+2(n-1)=2n$. This establishes (b). $\blacklozenge$

Therefore, the cardinality of $X$ is maximized when $|X\cap\\{u,v\\}|=1$. It
follows that $\operatorname{IR}(G_{n})=2n+1$, as asserted.

###  4.3 The $\operatorname{IR}(G_{n})$-sets

By (a) and (b) and the fact that $\operatorname{IR}(G_{n})=2n+1$, any
$\operatorname{IR}(G_{n})$-set contains exactly one of $u$ and $v$, and
exactly two vertices from each $S_{i}$. We show that the
$\operatorname{IR}(G_{n})$-sets are precisely the sets

  1. 1.

$X=C\cup D\cup\\{u\\}$

  2. 2.

$X_{i}=(X-\\{c_{i}\\})\cup\\{a_{i}\\}$ for $i=1,...,n$

  3. 3.

$X_{i}^{\prime}=(X-\\{d_{i}\\})\cup\\{a_{i}\\}$ for $i=1,...,n$

  4. 4.

$Y=C\cup D\cup\\{v\\}$

  5. 5.

$Y_{i}=(Y-\\{c_{i}\\})\cup\\{b_{i}\\}$ for $i=1,...,n$

  6. 6.

$Y_{i}^{\prime}=(Y-\\{d_{i}\\})\cup\\{b_{i}\\}$ for $i=1,...,n.$

Let $Z$ be any $\operatorname{IR}(G_{n})$-set and assume first that $u\in Z$.
We show that $Z\cap B=\varnothing$. Suppose $b_{i}\in Z$. Since $|Z\cap
S_{i}|=2$, $a_{i}\in Z$ or, without loss of generality, $c_{i}\in Z$.

  * •

Suppose $\\{a_{i},b_{i}\\}\subseteq Z$. Note that $N_{G_{n}}(u)=A\cup\\{v\\}$.
Since $u\sim a_{i}$, $u$ is not isolated in $G_{n}[Z]$, hence
$u\notin\operatorname{PN}(u,Z)$. Since $a_{i}\in Z$ and $b_{i}$ is adjacent to
$v$ and to each $a_{j},\ j\neq i$,
$(A\cup\\{v\\})\cap\operatorname{PN}(u,Z)=\varnothing$. But then
$\operatorname{PN}(u,Z)=\varnothing$, which is impossible.

  * •

Suppose $\\{b_{i},c_{i}\\}\subseteq Z$. Then $c_{i}$ is not isolated in
$G_{n}[Z]$, hence $c_{i}\notin\operatorname{PN}(c_{i},Z)$. But $b_{i}\in Z$
and $u\sim a_{i}$, hence
$\\{a_{i},b_{i}\\}\cap\operatorname{PN}(c_{i},Z)=\varnothing$. Therefore
$\operatorname{PN}(c_{i},Z)=\varnothing$, which is impossible.

We conclude that $b_{i}\notin Z$ and therefore $Z\cap B=\varnothing$. We show
next that $|Z\cap A|\leq 1$. Suppose to the contrary that $a_{i},a_{j}\in Z$
for $i\neq j$. Since $|Z\cap S_{i}|=2$, we further assume without loss of
generality that $c_{i}\in Z$. Since $a_{i}\sim c_{i}$,
$\\{a_{i},c_{i}\\}\cap\operatorname{PN}(c_{i},Z)=\varnothing$, and since
$a_{j}\sim b_{i}$, $b_{i}\notin\operatorname{PN}(c_{i},Z)$. Again we see that
$\operatorname{PN}(c_{i},Z)=\varnothing$, a contradiction.

We have therefore established that $S_{i}\cap Z=\\{c_{i},d_{i}\\}$ for all
except possibly one value of $i$. Consider the set $X_{i}=(C-\\{c_{i}\\})\cup
D\cup\\{a_{i},u\\}$. For each $j\neq i$,
$c_{j}\in\operatorname{PN}(c_{j},X_{i})$ and
$d_{j}\in\operatorname{PN}(d_{j},X_{i})$. Since $X_{i}\cap A=\\{a_{i}\\}$, no
vertex in $X_{i}-\\{d_{i}\\}$ is adjacent to $b_{i}$, hence
$b_{i}\in\operatorname{PN}(d_{i},X_{i})$. Finally,
$v\in\operatorname{PN}(u,X_{i})$. Therefore $X_{i}$ is irredundant. Since
$|X_{i}|=2n+1$, we have shown that $X_{i}$ is an
$\operatorname{IR}(G_{n})$-set for each $i$. Similarly, $X_{i}^{\prime}$ is an
$\operatorname{IR}(G_{n})$-set for each $i$. Therefore, the sets $X,\ X_{i}$
and $X_{i}^{\prime}$ are precisely the $\operatorname{IR}(G_{n})$-sets
containing $u$. By symmetry, $Y,\ Y_{i}$ and $Y_{i}^{\prime}$ are precisely
the $\operatorname{IR}(G_{n})$-sets containing $v$. Note that
$\\{X_{i},X_{i}^{\prime},Y_{i},Y_{i}^{\prime}\\}$ is a $4$-cluster for each
$i$.

Figure 3: The graph $G_{3}(\operatorname{IR})$, where $G_{3}$ is the graph in
Figure 2, $X=\\{u,c_{1},c_{2},c_{3},d_{1},d_{2},d_{3}\\},\
Y=\\{v,c_{1},c_{2},c_{3},d_{1},d_{2},d_{3}\\},\
X_{i}=(X-\\{c_{i}\\})\cup\\{a_{i}\\},\
X_{i}^{\prime}=(X-\\{d_{i}\\})\cup\\{a_{i}\\},\
Y_{i}=(Y-\\{c_{i}\\})\cup\\{b_{i}\\}$, and
$Y_{i}^{\prime}=(Y-\\{d_{i}\\})\cup\\{b_{i}\\}$

###  4.4 The graph $G_{n}(\operatorname{IR})$

Denote the $\operatorname{IR}$-graph $G_{n}(\operatorname{IR})$ by $H$. Figure
3 shows $H$ for the case $n=3$. Since $u\sim_{G_{n}}v$, we see that
$X\overset{uv}{\sim}_{H}Y$. Since $c_{i}\sim_{G_{n}}a_{i}$ and
$d_{i}\sim_{G_{n}}a_{i}$, it follows that
$X_{i}\overset{c_{i}a_{i}}{\sim}_{H}X$ and
$X_{i}^{\prime}\overset{d_{i}a_{i}}{\sim}_{H}X$ for each $i$. Similarly,
$Y_{i}\overset{c_{i}b_{i}}{\sim}_{H}Y$ and
$Y_{i}^{\prime}\overset{d_{i}b_{i}}{\sim}_{H}Y$ for each $i$. This shows that
the double star $S(2n,2n)$ is a spanning subgraph of $H$. It remains to show
that the vertices $X_{i},\ X_{i}^{\prime},\ Y_{i}$ and $Y_{i}^{\prime}$ are
leaves of $H$.

  * •

When $i\neq j$, note that $\\{a_{i},c_{j}\\}\subseteq X_{i}-X_{j}$. Therefore
$|X_{i}-X_{j}|\geq 2$, hence $X_{i}\nsim_{H}X_{j}$. Similarly,
$X_{i}^{\prime}\nsim_{H}X_{j}^{\prime},\ Y_{i}\nsim_{H}Y_{j}$ and
$Y_{i}^{\prime}\nsim_{H}Y_{j}^{\prime}$.

  * •

For each $i$, since $c_{i}\nsim d_{i}$, it follows that
$X_{i}\nsim_{H}X_{i}^{\prime}$. Similarly, $Y_{i}\nsim_{H}Y_{i}^{\prime}$.

  * •

Consider $X_{i}$ and $X_{j}^{\prime}$ for $i\neq j$. Since
$\\{a_{i},d_{j}\\}\subseteq X_{i}-X_{j}^{\prime}$, we know that
$|X_{i}-X_{j}^{\prime}|\geq 2$ and thus $X_{i}\nsim_{H}X_{j}^{\prime}$.
Similarly, $Y_{i}\nsim_{H}Y_{j}^{\prime}$.

It follows that the sets

$\mathcal{X}=\\{X_{i}:i=1,...,n\\}\cup\\{X_{i}^{\prime}:i=1,...,n\\}$

and

$\mathcal{Y}=\\{Y_{i}:i=1,...,n\\}\cup\\{Y_{i}^{\prime}:i=1,...,n\\}$

are independent in $G_{n}$.

  * •

For any $U\in\mathcal{X}$ and any $W\in\mathcal{Y}$, $\\{a_{i},u\\}\subseteq
U-W$ and $\\{a_{i},u\\}\subseteq U-Y$. Hence no vertex in $\mathcal{X}$ is
adjacent, in $G_{n}(\operatorname{IR})$, to $Y$ or to any $W\in\mathcal{Y}$.

  * •

Finally, no vertex $W\in\mathcal{Y}$ is adjacent to $X$, because
$\\{b_{i},v\\}\subseteq W-X$.

This completes the proof that $H=G_{n}(\operatorname{IR})\cong S(2n,2n)$.

##  5 Stars $S(2k,2k)$ are the only $\operatorname{IR}$-trees of diameter $3$

Having shown in Section 4 that $S(2n,2n)$ is an $\operatorname{IR}$-tree for
each $n\geq 1$, we now show that they are the only $\operatorname{IR}$-trees
of diameter $3$. We begin by stating a simple observation about trees of
diameter $3$ for referencing.

###### Observation 6

Let $T$ be a tree with diameter $3$ and diametrical path
$(v_{0},v_{1},v_{2},v_{3})$. For any vertex $u$ of $T$, $d(u,v_{1})\leq 2$ and
$d(u,v_{2})\leq 2$. Moreover, if $d(u,v_{1})=2$, then $v_{2}$ lies on the
$v_{1}$-$u$ geodesic and $u\sim v_{2}$.

We are now ready to prove our main result. We use the graphs in Figure 1
throughout the proof to affirm adjacencies and nonadjacencies between their
vertices. To prove the theorem we show that if a tree $T$ with
$\operatorname{diam}(T)=3$ is an $\operatorname{IR}$-tree, then the leaves of
$T$ occur in disjoint $4$-clusters. We state and prove several claims within
the main proof; the end of the proof of a claim is signalled by a diamond
$\blacklozenge$. We consider three cases in the proof of Claim 4; the end of
the proof of each case is indicated by an open diamond $\lozenge$.

###### Theorem 7

The stars $S(2k,2k)$, $k\geq 1$, are the only $\operatorname{IR}$-trees of
diameter $3$.

Proof. Suppose $T$ with $\operatorname{diam}(T)=3$ is an
$\operatorname{IR}$-tree of a graph $G$. By Lemma 2, all the
$\operatorname{IR}$-sets of $G$ are either independent or induce a graph that
has exactly three vertices of positive degree. If $G$ has only independent
$\operatorname{IR}$-sets, then by Lemma 3 the $\operatorname{IR}$-graph of $G$
contains a cycle. Therefore $G$ has an $\operatorname{IR}$-set
$X=\\{x_{1},...,x_{r}\\}$ with exactly three vertices, say
$x_{1},x_{2},x_{3}$, of positive degree in $G[X]$. Let
$x_{i}^{\prime}\in\operatorname{EPN}(x_{i},X)$ for $i=1,2,3$ and let
$X^{\prime}$ be the flip-set of $X$ using
$\\{x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime}\\}$. Since
$|X-X^{\prime}|=3$, we know that $d_{T}(X,X^{\prime})\geq 3$, and since
$\operatorname{diam}(T)=3$ by assumption, $d_{T}(X,X^{\prime})=3$. Let
$P:(X=X_{0},X_{1},X_{2},X_{3}=X^{\prime})$ be an $X$-$X^{\prime}$ geodesic in
$T$. Assume, as in the statement of Lemma 5, that

$X_{1}=\\{x_{1}^{\prime},x_{2},x_{3},\dots,x_{r}\\},X_{2}=\\{x_{1}^{\prime},x_{2}^{\prime},x_{3},\dots,x_{r}\\}\
\text{and\
}X_{3}=X^{\prime}=\\{x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime},\dots,x_{r}\\}.$

Let

$\displaystyle Z$
$\displaystyle=\\{x_{1},x_{2},x_{3},x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime}\\},$
$\displaystyle U$
$\displaystyle=\\{x_{1},x_{1}^{\prime},x_{2},x_{4},...,x_{r}\\},\text{\
}U^{\prime}=\\{x_{2}^{\prime},x_{3}^{\prime},x_{3},x_{4},...,x_{r}\\},\text{\
and}$ $\displaystyle\mathcal{X}$
$\displaystyle=\\{X,X^{\prime},U,U^{\prime}\\}.$

By Lemma 5, $G[Z]$ is the graph $G^{\prime}$ shown in Figure 1, the sets
$X_{1}$ and $X_{2}$ are independent,

$x_{3}\in\operatorname{EPN}(x_{1},U),\
x_{3}^{\prime}\in\operatorname{EPN}(x_{1}^{\prime},U)\text{\ and\
}x_{2}^{\prime}\in\operatorname{EPN}(x_{2},U),$ (1)

$U^{\prime}$ is the flip-set of $U$ using
$\\{x_{3},x_{3}^{\prime},x_{2}^{\prime}\\}$, and $\mathcal{X}$ is a
$4$-cluster. Also by Lemma 5,

$T[\\{X,X_{1},X_{2},X^{\prime},U,U^{\prime}\\}]\cong S(2,2),$

with edges shown in Figure 1. For referencing we state and prove the following
claim.

###### Claim 1

The vertex $x_{2}\in\operatorname{EPN}(x_{2}^{\prime},X_{2})$ and
$x_{2}^{\prime}$ is the only vertex with an $X_{2}$-external private
neighbour.

Proof of Claim 1. Since $X_{1}$ is independent, $x_{1}^{\prime}\nsim
x_{2}\nsim x_{3}$. Since $x_{i}$ is isolated in $G[X]$ for $i=4,...,r$,
$x_{2}\nsim x_{i}$ for $i=4,...,r$. Finally, since $x_{2}^{\prime}\sim x_{2}$,
it follows that $x_{2}\in\operatorname{EPN}(x_{2}^{\prime},X_{2})$. Since
$X_{2}$ is independent, Lemma 2 implies that that no other vertex in $X_{2}$
has an $X_{2}$-external private neighbour. $\blacklozenge$

By assumption, $T$ is a tree, $\operatorname{diam}(T)=3$ and $P$ is a
diametrical path of $T$. Hence any vertex of $T$ not on $P$ is a leaf adjacent
to $X_{1}$ or $X_{2}$. Let $A^{\prime}\notin\\{X_{1},X^{\prime},U^{\prime}\\}$
be any $\operatorname{IR}(G)$-set such that $X_{2}\sim_{T}A^{\prime}$; say
$X_{2}\overset{yy^{\prime}}{\sim}_{T}A^{\prime}$ for vertices $y\in X_{2}$ and
$y^{\prime}\in V(G)-X_{2}$ adjacent to $y$. We aim to show that $A^{\prime}$
belongs to a $4$-cluster disjoint from $\mathcal{X}$. Since $X_{2}$ is
independent and $y\sim y^{\prime}$, we know that

$y\in\operatorname{EPN}(y^{\prime},A^{\prime}).$ (2)

We further investigate the neighbourhoods of $y$ and $y^{\prime}$ in Claims 2
– 5.

###### Claim 2

The vertex $y^{\prime}$ is adjacent to exactly two vertices of $A^{\prime}$.

Proof of Claim 2. First suppose that $y^{\prime}$ is an $X_{2}$-private
neighbour of $y$. Then, by Claim 1, $y=x_{2}^{\prime}$ (but $y^{\prime}\neq
x_{2}$, otherwise $A^{\prime}=X_{1}$) and
$A^{\prime}=\\{x_{1}^{\prime},y^{\prime},x_{3},\dots,x_{r}\\}$. Furthermore,
if $y^{\prime}\nsim x_{2}$, then
$Q_{1}=\\{x_{1}^{\prime},y^{\prime},x_{2},x_{3},\dots,x_{r}\\}$ is an
independent set, hence an irredundant set, with $X_{1}\subsetneqq Q_{1}$. But
then $|Q_{1}|>\operatorname{IR}G)$, which is impossible. Hence $y^{\prime}\sim
x_{2}$. However, now $(X_{1},X_{2},A^{\prime},X_{1})$ is a cycle in the tree
$T$. This contradiction implies that $y^{\prime}$ is not an $X_{2}$-external
private neighbour of $y$ and therefore $y^{\prime}$ is not isolated in
$G[A^{\prime}]$. In fact, since $X_{2}$ is independent, it follows from Lemma
2 that $y^{\prime}$ is adjacent to at least two vertices in
$A^{\prime}=(X_{2}-\\{y\\})\cup\\{y^{\prime}\\}$. If $y^{\prime}$ is adjacent
to more than two vertices in $A^{\prime}$, then the flip-set of $A^{\prime}$
through $N[y^{\prime}]\cap A^{\prime}$ is at distance at least $3$ from
$X_{2}$, contradicting Observation 6. We conclude that $y^{\prime}$ is
adjacent to exactly two vertices of $A^{\prime}$. $\blacklozenge$

Since $A^{\prime}\notin\\{X_{1},X^{\prime},U^{\prime}\\}$ is an arbitrary
$\operatorname{IR}(G)$-set adjacent to $X_{2}$ (and since $X^{\prime}$ and
$U^{\prime}$ are not independent), it follows that no
$\operatorname{IR}(G)$-set adjacent to $X_{2}$, other than $X_{1}$, is
independent. By symmetry, the same statement is true for
$\operatorname{IR}(G)$-sets, other than $X_{2}$, adjacent to $X_{1}$. Since
$\operatorname{diam}(T)=3$ and $P$ is an $X$-$X^{\prime}$ geodesic, all
$\operatorname{IR}(G)$-sets are adjacent to either $X_{1}$ or $X_{2}$. We
therefore deduce that

$X_{1}\text{\ and\ }X_{2}\text{\ are\ the\ only\ independent\
}\operatorname{IR}(G)\text{-sets.}$ (3)

Let $u,v\in N(y^{\prime})\cap A^{\prime}$ with $A^{\prime}$-external private
neighbours $u^{\prime}$ and $v^{\prime}$, respectively. By (2),
$y\in\operatorname{EPN}(y^{\prime},A^{\prime})$. Denote the flip-set of
$A^{\prime}$ using $\\{y,u^{\prime},v^{\prime}\\}$ by $A$.

###### Claim 3

The vertex $y^{\prime}$ belongs to $V(G)-(X\cup Z)$_._

Proof of Claim 3. Suppose the vertex $y\in X_{2}$ is swapped out for one of
the vertices $x_{1},x_{2},x_{3}^{\prime}$. Recall that, by (1),
$x_{i}^{\prime}\in\operatorname{EPN}(x_{i},X)$ for $i\in\\{1,2,3\\}$. Since
the only neighbours of $x_{1}$ in $X$ are $x_{2}$ and $x_{3}$, the only
neighbours of $x_{1}$ in $X_{2}$ are $x_{1}^{\prime}$ and $x_{3}$. Since the
only neighbour of $x_{2}$ in $X$ is $x_{1}$, the only neighbour of $x_{2}$ in
$X_{2}$ is $x_{2}^{\prime}$. The only neighbours of $x_{3}^{\prime}$ in
$X_{2}$ are $x_{3}$ and, by Lemma 5, $x_{1}^{\prime}$ and $x_{2}^{\prime}$
(see Figure 1). Hence $y\in\\{x_{1}^{\prime},x_{2}^{\prime},x_{3}\\}$. But by
Lemma 5, the sets $X_{1},X_{2}$ and the $4$-cluster
$\\{X,X^{\prime},U,U^{\prime}\\}$ are the only $\operatorname{IR}(G)$-sets
that can be obtained in this way. We conclude that $y\in X_{2}$ is swapped for
$y^{\prime}\in V(G)-X-Z$. $\blacklozenge$

###### Claim 4

The vertex $y=x_{j}$ for some $j\geq 4$.

Proof of Claim 4. We showed in the proof of Claim 3 that no vertex in $X_{2}$
is swapped out for one of the vertices $x_{1},x_{2},x_{3}^{\prime}$. Now
suppose that $y\in\\{x_{1}^{\prime},x_{2}^{\prime},x_{3}\\}$ and $y$ is
swapped for $y^{\prime}\notin Z$. We consider three cases, depending on $y$.
In each case we examine the possibilities for the external
$A^{\prime}$-private neighbours $u^{\prime}$ and $v^{\prime}$ of the
neighbours $u$ and $v$, respectively, of $y^{\prime}$ in $A^{\prime}$. We show
that each choice where $\\{u^{\prime},v^{\prime}\\}\cap Z\neq\varnothing$
leads to a contradiction. We are then left with a flip-set $A$ of $A^{\prime}$
containing the vertices $u^{\prime},v^{\prime}\neq x_{i},x_{i}^{\prime}$ for
$i=1,2,3$, which implies that $d_{T}(X_{i},A)\geq 2$ for $i=1,2$, contrary to
Observation 6.

Case 1: $y=x_{2}^{\prime}$, that is,
$A^{\prime}=\\{x_{1}^{\prime},y^{\prime},x_{3},\dots,x_{r}\\}$. We show that
$u^{\prime},v^{\prime}\neq x_{i},x_{i}^{\prime}$ for $i=1,2,3$. Since
$u^{\prime},v^{\prime}$ are external $A^{\prime}$-private neighbours and
$x_{1}^{\prime},x_{3}\in A^{\prime}$, we know that $u^{\prime},v^{\prime}\neq
x_{1}^{\prime},x_{3}$. Since $y^{\prime}\sim x_{2}^{\prime}=y$, no neighbour
of $y^{\prime}$ has $x_{2}^{\prime}$ as $A^{\prime}$-private neighbour, hence
$u^{\prime},v^{\prime}\neq x_{2}^{\prime}$. Also, since
$x_{2}\in\operatorname{EPN}(x_{2}^{\prime},X_{2})$, we either have
$N[x_{2}]\cap A^{\prime}=\varnothing$ or $N[x_{2}]\cap
A^{\prime}=\\{y^{\prime}\\}$; in either case, $u^{\prime},v^{\prime}\neq
x_{2}$. Because $x_{1}^{\prime}\sim x_{3}^{\prime}\sim x_{3}$, we know that
$u^{\prime},v^{\prime}\neq x_{3}^{\prime}$. Finally, since $x_{1}^{\prime}\sim
x_{1}\sim x_{3}$, we have $u^{\prime},v^{\prime}\neq x_{1}$. Therefore the
flip-set $A$ of $A^{\prime}$ contains the vertices
$u^{\prime},v^{\prime}\notin Z$, which implies that
$\min\\{d_{T}(A,X_{1}),d_{T}(A,X_{2})\\}\geq 2$ and leads to a contradiction
to Observation 6.$~{}\lozenge$

Case 2: $y=x_{1}^{\prime}$, that is,
$A^{\prime}=\\{y^{\prime},x_{2}^{\prime},x_{3},...,x_{r}\\}$. We consider the
possibilities for the neighbours $u,v$ of $y^{\prime}$ in $A^{\prime}$ and
their respective external $A^{\prime}$-private neighbours
$u^{\prime},v^{\prime}$. If $y^{\prime}\sim x_{3}^{\prime}$ (see the black and
blue edges in Figure 4), then
$A^{\prime}\overset{y^{\prime}x_{3}^{\prime}}{\sim}_{T}U^{\prime}$, so that
the graph $H$ in Figure 4 is a subgraph of the tree $T$, which is impossible.

$\text{Hence\ we\ may\ assume\ that\ }y^{\prime}\nsim x_{3}^{\prime}.$ (4)

Clearly, $u^{\prime},v^{\prime}\neq x_{2}^{\prime},x_{3}\in A^{\prime}$
because $u^{\prime}$ and $v^{\prime}$ are external $A^{\prime}$-private
neighbours.

We next show that $y^{\prime}\sim x_{2}^{\prime}$. Suppose, to the contrary,
that $y^{\prime}\nsim x_{2}^{\prime}$, that is, $u,v\in\\{x_{3},...,x_{r}\\}$.
We may then assume that $v\neq x_{3}$. By the private neighbour properties of
$X$, this implies that $v^{\prime}\neq x_{i},x_{i}^{\prime}$ for $i=1,2,3$,
since none of these vertices is adjacent to a vertex in
$\\{x_{4},...,x_{r}\\}$. If we also have that $u\neq x_{3}$, the same holds
for $u^{\prime}$, i.e., $u^{\prime},v^{\prime}\notin Z$, and we are done,
hence assume $u=x_{3}$. Since $x_{2}^{\prime}\sim x_{3}^{\prime}$, we have
that
$x_{3}^{\prime}\notin\operatorname{EPN}(x_{3},A^{\prime})\cup\operatorname{EPN}(y^{\prime},A^{\prime})$.
Therefore $u^{\prime}\neq x_{3}^{\prime}$. Since $x_{2}\sim x_{2}^{\prime}$,
we know that $u^{\prime}\neq x_{2}$. Suppose $u^{\prime}=x_{1}$. Then
$A=\\{x_{1},x_{1}^{\prime},x_{2}^{\prime},v^{\prime},x_{4},...,x_{r}\\}-\\{v\\}$.
However, now $x_{1},v^{\prime}\in A-(X_{1}\cup X_{2})$, so that
$\min\\{d_{T}(A,X_{1}),d_{T}(A,X_{2})\\}\geq 2$, contrary to Observation 6. We
obtain a similar contradiction if $u^{\prime}\notin Z$.

$\text{Therefore\ we\ may\ assume\ that}\ y^{\prime}\sim
x_{2}^{\prime}\text{;\ say\ }x_{2}^{\prime}=v.$ (5)

Because $x_{2}^{\prime}\sim x_{3}^{\prime}\sim x_{3}$, we know that
$x_{3}^{\prime}\notin\\{u^{\prime},v^{\prime}\\}$. We still need to consider
$x_{1}$ and $x_{2}$. Observe that

$\text{if\ }x_{2}\in\\{u^{\prime},v^{\prime}\\}\text{,\ then\
}x_{2}=v^{\prime}$ (6)

because $x_{2}\sim x_{2}^{\prime}=v$ by (5). Since
$x_{2}^{\prime}\in\operatorname{EPN}(x_{2},X)$, $x_{1}\nsim x_{2}^{\prime}=v$
and so $x_{1}\neq v^{\prime}$. The investigation of whether $x_{1}=u^{\prime}$
depends on whether $u=x_{3}$ or $u=x_{j}$ for $j\geq 4$.

Figure 4: The graph $G^{\prime\prime}=G[Z\cup\\{y^{\prime}\\}]$ and the graph
$H$ formed by its $\operatorname{IR}$-sets, as described in Case 2 of the
proof of Claim 4

Case 2.1: $u=x_{3}$. Consider
$A=\\{y,u^{\prime},v^{\prime},x_{4},..,x_{r}\\}$.

Suppose that $u^{\prime}=x_{1}$ and $v^{\prime}=x_{2}$. Then

$x_{1}^{\prime}\in\operatorname{EPN}(y^{\prime},A^{\prime}),\ \
x_{2}\in\operatorname{EPN}(x_{2}^{\prime},A^{\prime})\ \ \text{and}\ \
x_{1}\in\operatorname{EPN}(x_{3},A^{\prime}).$

At this point the graph $G[Z\cup\\{y^{\prime}\\}]$ is the graph formed by the
black and red edges of the graph $G^{\prime\prime}$ in Figure 4, where the
vertices in $A^{\prime}-\\{x_{4},...,x_{r}\\}$ and their private neighbours
are shown by solid squares and open circles, respectively. By Claim 2, (5) and
the assumption of Case 2.1, $y^{\prime}$ is adjacent to exactly two vertices
in $A^{\prime}$, namely $x_{2}^{\prime}$ and $x_{3}$; we deduce that
$y^{\prime}\in\operatorname{EPN}(x_{3},X)$. Since, by (4), $y^{\prime}\nsim
x_{3}^{\prime}$, it now follows that the set
$Q_{2}=(X-\\{x_{1},x_{3}\\})\cup\\{y^{\prime},x_{3}^{\prime}\\}=\\{y^{\prime},x_{2},x_{3}^{\prime},x_{4},...,x_{r}\\}$
is independent and therefore an $\operatorname{IR}(G)$-set, contradicting (3).

Suppose $v^{\prime}=x_{2}$ but
$x_{1}\notin\operatorname{EPN}(x_{3},A^{\prime})$, i.e., $x_{1}\neq
u^{\prime}$. Then $u^{\prime}\in V(G)-(X\cup Z)$. (See the black edges of
$G^{\ast}$ in Figure 5.) Consider the set
$Q_{3}=\\{x_{1},x_{2}^{\prime},x_{3},...,x_{r}\\}$ and note that $x_{1}x_{3}$
is the only edge of $G[Q_{3}]$. Moreover,
$x_{1}^{\prime}\in\operatorname{EPN}(x_{1},Q_{3})$ and (with only the edges in
black) $u^{\prime}\in\operatorname{EPN}(x_{3},Q_{3})$. But by Lemma 2, $Q_{3}$
is not an $\operatorname{IR}(G)$-set. The only possibility is that
$u^{\prime}$ is adjacent to some other vertex of $Q_{3}$. Since
$x_{2}^{\prime}\in A^{\prime}$ and
$u^{\prime}\in\operatorname{EPN}(x_{3},A^{\prime})$, it follows that
$u^{\prime}\nsim x_{2}^{\prime}$, and we conclude that $u^{\prime}\sim x_{1}$.
(See the black and blue edges of $G^{\ast}$ in Figure 5.) But now
$A=\\{x_{1}^{\prime},x_{2},u^{\prime},x_{4},...,x_{r}\\}$ belongs to the
triangle
$A\overset{u^{\prime}x_{3}}{\sim}_{T}X_{1}\overset{x_{3}x_{1}}{\sim}_{T}U\overset{x_{1}u^{\prime}}{\sim}_{T}A$
in $T$, which is impossible.

Finally, suppose $v^{\prime}\neq x_{2}$. If $u^{\prime}=x_{1}$, then
$A=\\{x_{1},x_{1}^{\prime},v^{\prime},x_{4},...,x_{r}\\}$, where
$v^{\prime}\neq x_{i},x_{i}^{\prime}$ for $i=1,2,3$. Hence
$\\{x_{1},v^{\prime}\\}\subseteq A-(X_{1}\cup X_{2})$ and we get a
contradiction to Observation 6. We obtain a similar contradiction if
$u^{\prime}\neq x_{1}$, because then $u^{\prime},v^{\prime}\neq
x_{i},x_{i}^{\prime}$ for $i=1,2,3$ and $\\{u^{\prime},v^{\prime}\\}\subseteq
A-(X_{1}\cup X_{2})$. This concludes the proof of Case 2.1 ($u=x_{3}$).

Figure 5: The graph $G^{\ast}=G[Z\cup\\{u^{\prime},y^{\prime}\\}]$ and the
graph $H$ formed by its $\operatorname{IR}$-sets, as described in Case 2.1 of
the proof of Theorem 7.

To recapitulate, we may assume, by (4) and (5), that $y^{\prime}\nsim
x_{3}^{\prime}$ and $y^{\prime}\sim x_{2}^{\prime}=v$. We have shown that
$\\{u^{\prime},v^{\prime}\\}\cap\\{x_{2}^{\prime},x_{3},x_{3}^{\prime}\\}=\varnothing$,
and if $x_{2}\in\\{u^{\prime},v^{\prime}\\}$, then $x_{2}=v^{\prime}$ – see
(6).

Case 2.2: $u\in\\{x_{4},...,x_{r}\\}$; say $u=x_{4}$. By the properties of
$X$, $u^{\prime}\notin X\cup Z$; say $u^{\prime}=x_{4}^{\prime}$. Moreover,
since $x_{1}\nsim x_{2}^{\prime}$, we have that $x_{1}\neq v^{\prime}$. Assume
therefore that $x_{2}=v^{\prime}$, otherwise $\\{u^{\prime},v^{\prime}\\}\cap
Z=\varnothing$ and we are done. Now
$A=\\{x_{1}^{\prime},x_{2},x_{3},x_{4}^{\prime},x_{5},...,x_{r}\\}$ and
$y^{\prime}\nsim x_{2}=v^{\prime}$. If
$x_{1}\in\operatorname{EPN}(x_{3},A^{\prime})$, then, by Theorem 1 applied to
the flip-set of $A^{\prime}$ using
$\\{x_{1},x_{1}^{\prime},x_{2},x_{4}^{\prime}\\}$, this set is an
$\operatorname{IR}(G)$-set that differs from $A^{\prime}$ in four elements.
But this is impossible because $\operatorname{diam}(T)=3$. Hence
$x_{1}\notin\operatorname{EPN}(x_{3},A^{\prime})$ and the only possibility is
that $x_{1}\sim y^{\prime}$. Moreover, by Lemma 5$(i)$ applied to $A^{\prime}$
and $A$, and because $x_{1}^{\prime}\nsim x_{2}$, we see that
$x_{1}^{\prime}\sim x_{4}^{\prime}\sim x_{2}$. Consider the set
$Q_{5}=\\{x_{1},y^{\prime},x_{3},...,x_{r}\\}$ and note that $G[Q_{5}]$
contains the path $(x_{3},x_{1},y^{\prime},x_{4})$. Hence, by Lemma 4, $Q_{5}$
is not an $\operatorname{IR}(G)$-set. But
$x_{2}\in\operatorname{EPN}(x_{1},Q_{5})$,
$x_{2}^{\prime}\in\operatorname{EPN}(y^{\prime},Q_{5})$,
$x_{3}^{\prime}\in\operatorname{EPN}(x_{3},Q_{5})$ and, unless $x_{1}\sim
x_{4}^{\prime}$, we also have that
$x_{4}^{\prime}\in\operatorname{EPN}(x_{4},Q_{5})$; all vertices $x_{i}$ with
$i\geq 5$ are isolated in $G[Q_{5}]$. Therefore $x_{1}\sim x_{4}^{\prime}$.
Finally, consider the set $Q_{6}=\\{x_{4}^{\prime},x_{2},...,x_{r}\\}$, and
note that $x_{1}^{\prime}\in\operatorname{EPN}(x_{4}^{\prime},Q_{6})$,
$x_{2}^{\prime}\in\operatorname{EPN}(x_{2},Q_{6})$ and
$y^{\prime}\in\operatorname{EPN}(x_{4},Q_{6})$, while $x_{i}$, for $i=3$ or
$i\geq 5$, is isolated in $G[Q_{6}]$. Hence $Q_{6}$ is an
$\operatorname{IR}(G)$-set. However,
$Q_{6}\overset{x_{4}^{\prime}x_{1}}{\sim}_{T}X$, from which it follows that
$T$ either has diameter at least $4$ (if $Q_{6}$ is nonadjacent to all other
$\operatorname{IR}(G)$-sets), or a cycle (otherwise). This concludes the proof
of Case 2.2 ($u=x_{j}$, $j\geq 4$) and also of Case 2\. $\lozenge$

Case 3: $y=x_{3}$, i.e.,
$A^{\prime}=\\{x_{1}^{\prime},x_{2}^{\prime},y^{\prime},x_{4},\dots,x_{r}\\}$
and $x_{3}\in\operatorname{EPN}(y^{\prime},A^{\prime})$. Similar to Case 2, if
$y^{\prime}\sim x_{3}^{\prime}$, then
$X_{2}\overset{x_{3}y^{\prime}}{\sim}A^{\prime}\overset{y^{\prime}x_{3}^{\prime}}{\sim}X^{\prime}\overset{x_{3}^{\prime}x_{3}}{\sim}X_{2}$,
thus forming a cycle. Hence $y^{\prime}\nsim x_{3}^{\prime}$. Recall that if
the external $A^{\prime}$-private neighbours $u^{\prime}$ and $v^{\prime}$ of
$u$ and $v$, respectively, satisfy $\\{u^{\prime},v^{\prime}\\}\cap
Z=\varnothing$, then $d_{T}(X_{i},A)\geq 2$ for $i=1,2$, contrary to
Observation 6. The possibilities for $u^{\prime}$ and $v^{\prime}$ among
$x_{i},x_{i}^{\prime}$, $i=1,2,3$, are $x_{1},x_{2}$ and $x_{3}^{\prime}$.
However, $x_{3}^{\prime}$ is adjacent to both $x_{1}^{\prime}$ and
$x_{2}^{\prime}$, so we only need to consider $x_{1}$ and $x_{2}$. Note that

$\text{if\ (say)\ }u^{\prime}=x_{1}\text{,\ then\ }u=x_{1}^{\prime}\text{\
since\ }x_{1}\sim x_{1}^{\prime}\text{;\ similarly,\ if\
}v^{\prime}=x_{2}\text{,\ then\ }v=x_{2}^{\prime}.$ (7)

Suppose $u^{\prime}=x_{1}$ and $v^{\prime}=x_{2}$. Then $u=x_{1}^{\prime}$ and
$v=x_{2}^{\prime}$, hence, by Claim 2 and the elements in $X$ and
$A^{\prime}$, $x_{3}$ is the only neighbour of $y^{\prime}$ in $X$, i.e.,
$\\{y^{\prime},x_{3}^{\prime}\\}\subseteq\operatorname{EPN}(x_{3},X)$. But
then, since $y^{\prime}\nsim x_{3}^{\prime}$,
$(X-\\{x_{2},x_{3}\\})\cup\\{y^{\prime},x_{3}^{\prime}\\}$ is an independent
set of $G$ of cardinality $\operatorname{IR}(G)$, hence an independent
$\operatorname{IR}(G)$-set different from both $X_{1}$ and $X_{2}$, contrary
to (3).

Suppose $u=x_{1}^{\prime}$ and $v^{\prime}\neq x_{2}$, that is, $u^{\prime}$
is either $x_{1}$ or $u^{\prime}\notin Z$, and $v^{\prime}\notin Z$. Then
$A=\\{u^{\prime},v^{\prime},x_{3},...,x_{r}\\}$, so that, by the conditions on
$u^{\prime}$, the set $\\{u^{\prime},v^{\prime}\\}\subseteq A-(X_{1}\cup
X_{2})$. Consequently, $d_{T}(X_{i},A)\geq 2$ for $i=1,2$, contrary to
Observation 6. Similarly, if $u\neq x_{1}^{\prime}$ (so $u^{\prime}\notin Z$)
and $v^{\prime}\notin Z$, then $d_{T}(X_{i},A)\geq 2$ for $i=1,2$, giving the
same contradiction. We examine the remaining case.

Suppose $u\neq x_{1}^{\prime}$ and $v^{\prime}=x_{2}$. Then $v=x_{2}^{\prime}$
and $u,u^{\prime}\notin Z$. Assume without loss of generality that $u=x_{4}$.
Then $A=\\{x_{1}^{\prime},x_{2},x_{3},u^{\prime},x_{5},\dots,x_{r}\\}$. We
consider the edges of $G[A\cup Z]$ and $G[A^{\prime}\cup Z]$. Applying Lemma
5$(i)$ to $A^{\prime}$ and $A$ (and noting that $x_{2}\nsim x_{3}$ and
$x_{2}\nsim x_{1}^{\prime}\nsim x_{3}$) we find that $x_{2}\sim u^{\prime}\sim
x_{3}$.__ Since $u^{\prime}\in\operatorname{EPN}(x_{4},A^{\prime})$,
$u^{\prime}$ is nonadjacent to all vertices in
$A^{\prime}-\\{x_{4}\\}=\\{x_{1}^{\prime},x_{2}^{\prime},y^{\prime},x_{5},...,x_{r}\\}$.
Since each of $x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime}$ has an
$X^{\prime}$-external private neighbour, Lemma 4 implies that
$\operatorname{EPN}(x_{4},X^{\prime})=\varnothing$. The only remaining
possibility is that $u^{\prime}\sim x_{3}^{\prime}$. To avoid $A^{\prime}$
having four vertices with external private neighbours,
$x_{1}\notin\operatorname{EPN}(x_{1}^{\prime},A^{\prime})$, and since
$x_{2}^{\prime}\nsim x_{1}\nsim x_{4}$, necessarily $y^{\prime}\sim x_{1}$.

Consider the set
$Q_{7}=\\{x_{1},x_{2},x_{2}^{\prime},y^{\prime},x_{5},...,x_{r}\\}$. Since
$x_{1}\sim x_{2}\sim x_{2}^{\prime}=v\sim y^{\prime}$,
$x_{1},x_{2},x_{2}^{\prime},y^{\prime}$ all have positive degree in
$G[Q_{7}]$. Hence $Q_{7}$ is not an $\operatorname{IR}(G)$-set (by Lemma 4).
However, if $x_{1}\nsim u^{\prime}$, then
$x_{1}^{\prime}\in\operatorname{EPN}(x_{1},Q_{7}),\
u^{\prime}\in\operatorname{EPN}(x_{2},Q_{7}),\
x_{3}^{\prime}\in\operatorname{EPN}(x_{2}^{\prime},Q_{7})$ and
$x_{4}\in\operatorname{EPN}(y^{\prime},Q_{7})$. Thus $x_{1}\sim u^{\prime}$.
The subgraph $F=G[Z\cup\\{x_{4},u^{\prime},y^{\prime}\\}]$ is shown by the
black edges in Figure 6, where the edges incident with $u^{\prime}$ and
$y^{\prime}$ in the complement $\overline{F}$ are shown in colour (light grey
in monotone). Recall that $U=\\{x_{1},x_{1}^{\prime},x_{2},x_{4},...,x_{r}\\}$
and consider the set
$M=\\{x_{1}^{\prime},x_{2},x_{4},u^{\prime},x_{4},...,x_{r}\\}$. The vertices
$x_{2},x_{4}$ and $u^{\prime}$ have positive degree in $G[M]$ and have
$M$-external private neighbours $x_{2}^{\prime},y^{\prime}$ and $x_{3}$,
respectively, hence $M$ is an $\operatorname{IR}(G)$-set. However,
$M\overset{u^{\prime}x_{1}}{\sim}_{T}U\overset{x_{1}x_{3}}{\sim}_{T}X_{1}\overset{x_{3}u^{\prime}}{\sim}_{T}M$,
hence $T$ contains a cycle, which is impossible.

Figure 6: The graph $F=G[Z\cup\\{x_{4},u^{\prime},y^{\prime}\\}]$ and the
graph $H$ formed by some of its $\operatorname{IR}$-sets, as described in Case
3 of the proof of Theorem 7.

We conclude that $\\{u^{\prime},v^{\prime}\\}\cap Z=\varnothing$, which leads
to a contradiction with Observation 6 as explained above. $\lozenge$

Therefore, no $y\in\\{x_{1}^{\prime},x_{2}^{\prime},x_{3}\\}$ is swapped when
obtaining $A^{\prime}$ from
$X_{2}=\\{x_{1}^{\prime},x_{2}^{\prime},x_{3},\dots,x_{r}\\}$; it follows that
$y=x_{j}$ for some $j\geq 4$. $\blacklozenge$

We have shown in Claims 3 and 4 that if
$A^{\prime}\notin\\{X_{1},X_{3},U^{\prime}\\}$ is any
$\operatorname{IR}(G)$-set such that
$X_{2}\overset{yy^{\prime}}{\sim}_{T}A^{\prime}$, then $y=x_{i}$ for $i\geq
4$, and $y^{\prime}\in V(G)-(X\cup Z)$. Assume without loss of generality that
$y=x_{4}$ and denote $y^{\prime}$ by $x_{4}^{\prime}$, so that
$A^{\prime}=\\{x_{1}^{\prime},x_{2}^{\prime},x_{3},x_{4}^{\prime},x_{5}\dots,,x_{r}\\}$
and $x_{4}\in\operatorname{EPN}(x_{4}^{\prime},A^{\prime})$. We determine the
two neighbours of $x_{4}^{\prime}$ in $A^{\prime}$ in Claim 5.

###### Claim 5

The neighbours of $y^{\prime}=x_{4}^{\prime}$ in $A^{\prime}$ are
$x_{2}^{\prime}$ and a vertex $x_{j}\in X$, where $j\geq 5$.

Proof of Claim 5. For the two neighbours $u$ and $v$ of $x_{4}^{\prime}$ in
$A^{\prime}$, we consider the possibilities for their external
$A^{\prime}$-private neighbours $u^{\prime}$ and $v^{\prime}$, respectively.
Clearly, if $\\{u^{\prime},v^{\prime}\\}\subseteq A-(X_{1}\cup X_{2})$, then
$d_{T}(X_{i},A)\geq 2$ for $i=1,2$ and we obtain a contradiction to
Observation 6 as before. Therefore we may assume that

$|\\{u^{\prime},v^{\prime}\\}\cap A\cap X_{1}|\geq 1\text{ \ or \
}|\\{u^{\prime},v^{\prime}\\}\cap A\cap X_{2}|\geq 1.$ (8)

By the properties of the $X_{i}$, no vertex in $\\{x_{5},...,x_{r}\\}$ is
adjacent to a vertex in $X\cup Z$. Thus, if (say) $u\in\\{x_{5},...,x_{r}\\}$,
then $u^{\prime}\notin X_{1}\cup X_{2}$, and the same holds for $v$ and
$v^{\prime}$. Hence the inequalities (8) imply that
$|\\{u,v\\}\cap\\{x_{5},...,x_{r}\\}|\leq 1$ and
$|\\{u,v\\}\cap\\{x_{1}^{\prime},x_{2}^{\prime},x_{3}\\}|\geq 1$. Since
$x_{1}^{\prime}\sim x_{1}\sim x_{3}$ and $x_{1}^{\prime}\sim
x_{3}^{\prime}\sim x_{3}$, we know that
$\\{u^{\prime},v^{\prime}\\}\cap\\{x_{1},x_{3}^{\prime}\\}=\varnothing$. Since
we also know that $u^{\prime},v^{\prime}\notin A^{\prime}$, the inequalities
(8) now reduce to
$\\{u^{\prime},v^{\prime}\\}\cap\\{x_{1},x_{2},x_{3}^{\prime}\\}=\\{x_{2}\\}$.
Necessarily, then, $x_{4}^{\prime}$ is adjacent to $x_{2}^{\prime}$ and to
some vertex $x_{j}\in X$, where $j\geq 5$, as required. $\blacklozenge$

Assume without loss of generality that $u^{\prime}=x_{2}$, that is,
$u=x_{2}^{\prime}$, and that $v$ and $v^{\prime}$ are $x_{5}$ and
$x_{5}^{\prime}$, respectively. Then
$A^{\prime}=\\{x_{1}^{\prime},x_{2}^{\prime},x_{3},x_{4}^{\prime},x_{5},...,x_{r}\\}$
and $A=\\{x_{1}^{\prime},x_{2},x_{3},x_{4},x_{5}^{\prime},...,x_{r}\\}$. Let
$B=(A-\\{x_{4}\\})\cup\\{x_{5}\\}$ and
$B^{\prime}=(A^{\prime}-\\{x_{5}\\})\cup\\{x_{4}\\}$ be the skip-sets of $A$
and $A^{\prime}$, respectively. By Lemma 5,
$\mathcal{A}=\\{A,A^{\prime},B,B^{\prime}\\}$ is a $4$-cluster. Clearly,
$\mathcal{A}$ and $\mathcal{X}=\\{X,X^{\prime},U,U^{\prime}\\}$ are disjoint
$4$-clusters.

We complete the proof of the theorem by showing, in Claim 6, that any other
leaf of $T$ belongs to a $4$-cluster disjoint from both $\mathcal{A}$ and
$\mathcal{X}$.

###### Claim 6

Any $\operatorname{IR}(G)$ set
$C^{\prime}\notin\\{X_{1},X^{\prime},A^{\prime},B^{\prime},U^{\prime}\\}$
adjacent to $X_{2}$ is obtained by swapping a vertex $x_{j}\in X_{2}$ for a
vertex $x_{j}^{\prime}$, where $j\geq 6$,
$x_{j}^{\prime}\notin\\{x_{1},...,x_{5},x_{1}^{\prime},...,x_{5}^{\prime}\\}$,
the only neighbours of $x_{j}^{\prime}$ in $C^{\prime}$ are $x_{2}^{\prime}$
and $x_{k}$ for some$\ k\geq 6,\ k\neq j$, and the $C^{\prime}$-external
private neighbour $x_{6}^{\prime}$ of $x_{6}$ also does not belong to
$\\{x_{1},...,x_{5},x_{1}^{\prime},...,x_{5}^{\prime}\\}$.

Proof of Claim 6. Suppose that
$C^{\prime}\notin\\{X_{1},X^{\prime},A^{\prime},B^{\prime},U^{\prime}\\}$ and
$X_{2}\overset{yy^{\prime}}{\sim}_{T}C^{\prime}$. We first consider
$C^{\prime}$ in relation to the $4$-cluster $\mathcal{X}$, repeating the
arguments above.

By Claim 2, $y^{\prime}$ is adjacent to exactly two vertices of $C^{\prime}$,
and by Claims 3 and 4, $y=x_{j}$, where $j\geq 4$ and $y^{\prime}\in
V(G)-(X\cup\\{x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime}\\})$. Say
$y^{\prime}=x_{j}^{\prime}$. By Claim 5, the neighbours of $x_{j}^{\prime}$ in
$C^{\prime}$ are $x_{2}^{\prime}$ and a vertex $x_{k}\in X$, where $k\geq 4$
and $k\neq j$. Note that
$G[\\{x_{2},x_{2}^{\prime},x_{4},x_{4}^{\prime},x_{5},x_{5}^{\prime}\\}]\cong
G[Z]$ under an isomorphism that fixes $x_{2}$ and $x_{2}^{\prime}$. Repeating
the proof above for the $4$-cluster $\mathcal{A}$, Claims 3 and 4 give that
$x_{j}\in\\{x_{1},x_{1}^{\prime},x_{3},x_{3}^{\prime},x_{6},...,x_{r}\\}$ and
$x_{j}^{\prime}\in
V(G)-(X\cup\\{x_{2}^{\prime},x_{4}^{\prime},x_{5}^{\prime}\\})$. The two
conditions on $x_{j}$ show that $j\geq 6$, while those on $x_{j}^{\prime}$
show that $x_{j}^{\prime}\in
V(G)-(X\cup\\{x_{1}^{\prime},...,x_{5}^{\prime}\\})$. Hence assume $j=6$,
i.e., $y=x_{6}$ and $y^{\prime}=x_{6}^{\prime}$. Now Claim 5 applied to
$\\{x_{2},x_{2}^{\prime},x_{4},x_{4}^{\prime},x_{5},x_{5}^{\prime},x_{6},x_{6}^{\prime}\\}$
asserts that the neighbours of $x_{6}^{\prime}$ in $C^{\prime}$ are
$x_{2}^{\prime}$ and a vertex in $C^{\prime}$ different from
$x_{2}^{\prime},x_{4},x_{5}$. Consolidating the two conditions obtained from
Claim 5, the neighbours of $x_{6}^{\prime}$ in $C^{\prime}$ are
$x_{2}^{\prime}$ and $x_{k}$, where $k\geq 7$; say $k=7$. Let
$x_{7}^{\prime}\in\operatorname{EPN}(x_{7},C^{\prime})$. As above,
$G[\\{x_{2},x_{2}^{\prime},x_{6},x_{6}^{\prime},x_{7},x_{7}^{\prime}\\}]\cong
G[Z]$ under an isomorphism that fixes $x_{2}$ and $x_{2}^{\prime}$. Thus
$(x_{6},x_{6}^{\prime},x_{7},x_{7}^{\prime},x_{6})$ is a $4$-cycle in $G$ in
which $x_{6}$ and $x_{7}$ are nonadjacent vertices of degree $2$, and the
skip-set $D^{\prime}=(C^{\prime}-\\{x_{7}\\})\cup\\{x_{6}\\}$ and the flip-
sets $C$ and $D$ of $C^{\prime}$ and $D^{\prime}$ obtained by using the
obvious private neighbours are all $\operatorname{IR}(G)$-sets which form a
$4$-cluster. $\blacklozenge$

By repeating the arguments in the proof of Claim 6, considering all existing
$4$-clusters in turn in each step until all vertices in $X$ have been used, we
show that the leaves of $T$ occur in disjoint $4$-clusters, thus obtaining the
desired result. $\blacksquare$

##  6 Open Problems

We conclude by mentioning a number of conjectures and open problems, most of
which also appear in [15].

###### Conjecture 1

_[15]_$\hskip 7.22743pt(i)\hskip 7.22743pt$The path $P_{n}$ is not an
$\operatorname{IR}$-graph for each $n\geq 3$.

  1. $(ii)$

The cycle $C_{n}$ is not an $\operatorname{IR}$-graph for each $n\geq 5$.

###### Problem 1

_[15] _Prove or disprove: Complete graphs and
$K_{m}\mathbin{\raisebox{0.85358pt}{$\scriptstyle\square$}}K_{n}$, where
$m,n\geq 2$, are the only connected claw-free $\operatorname{IR}$-graphs.

###### Problem 2

_[15] _Determine which double spiders are $\operatorname{IR}$-trees.

###### Problem 3

_[15] _Characterize $\operatorname{IR}$-graphs having diameter $2$.

###### Problem 4

Determine which graphs are $\operatorname{IR}$-graphs of a graph $G$ such that
$\operatorname{IR}(G)=2$.

Acknowledgements We acknowledge the support of the Natural Sciences and
Engineering Research Council of Canada (NSERC), PIN 253271.

Cette recherche a été financée par le Conseil de recherches en sciences
naturelles et en génie du Canada (CRSNG), PIN 253271.

## References

  * [1] S. Alikhani, D. Fatehi and S. Klavžar, On the structure of dominating graphs, _Graphs Combin._ 33 (2017), 665–672.
  * [2] A. Bień, Gamma graphs of some special classes of trees, _Ann. Math. Sil_. 29 (2015), 25–34.
  * [3] G. Chartrand, L. Lesniak, P. Zhang, _Graphs & Digraphs _(sixth edition), Chapman and Hall/CRC, Boca Raton, 2016.
  * [4] E. J. Cockayne, S. T. Hedetniemi, D. J. Miller, Properties of hereditary hypergraphs and middle graphs, _Canad. Math. Bull._ 21 (1978), 461–468.
  * [5] E. Connelly, S.T. Hedetniemi, K.R. Hutson, A note on $\gamma$-Graphs. _AKCE Intr. J. Graphs Comb._ 8(1) (2010), 23-31.
  * [6] A. Dyck, _The Realisability of_ $\gamma$_-Graphs_. Master’s Thesis, Simon Fraser University, 2017.
  * [7] M. Edwards, _Vertex-critically and bicritically for independent domination and total domination in graphs_. PhD Dissertation, University of Victoria, 2015.
  * [8] G.H. Fricke, S.M. Hedetniemi, S.T. Hedetniemi, K.R. Hutson, $\gamma$-graphs of graphs. _Discuss. Math. Graph Theory_ 31 (2011), 517-531.
  * [9] R. Haas, K. Seyffarth, The $k$-dominating graph, _Graphs Combin._ 30(3) (2014), 609–617.
  * [10] R. Haas, K. Seyffarth, Reconfiguring dominating sets in some well-covered and other classes of graphs, _Discrete Math._ 340 (2017), 1802–1817.
  * [11] A. Haddadan, T. Ito, A. E. Mouawad, N. Nishimura, H. Ono, A. Suzuki, Y. Tebbal, _The complexity of dominating set reconfiguration_ , _Theoret. Comput. Sci._ 651 (2016), 37–49.
  * [12] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, _Fundamentals of Domination in Graphs_. Marcel Dekker, New York, 1998.
  * [13] S. A. Lakshmanan, A. Vijayakumar, The gamma graph of a graph, _AKCE Int. J. Graphs Comb._ 7 (2010), 53–59.
  * [14] C. M. Mynhardt, S. Nasserasr, Reconfiguration of colourings and dominating sets in graphs, in F. Chung, R. Graham, F. Hoffman,L. Hogben, Ron Mullin and Doug West (Eds.), _50 Years of Combinatorics, Graph Theory, and Computing_ , Chapman and Hall/CRC Press, 2019.
  * [15] C. M. Mynhardt, A. Roux, Irredundance Graphs, submitted. arXiv:1812.03382
  * [16] C. M. Mynhardt, A. Roux, L. E. Teshima, Connected $k$-dominating graphs, _Discrete Math._ 342 (2019), 145-151.
  * [17] C. M. Mynhardt and L. Teshima, A note on some variations of the $\gamma$-graph, _J. Combin. Math. Combin. Comput._ 104 (2018), 217-230.
  * [18] N. Sridharan, S. Amutha, S. B. Rao, Induced subgraphs of gamma graphs, _Discrete Math. Algorithms Appl._ 5 (2013), no. 3, 1350012, 5 pp.
  * [19] K. Subramanian, N. Sridharan, $\gamma$-graph of a graph. _Bull. Kerala Math. Assoc._ 5(1) (2008), 17-34.
  * [20] A. Suzuki, A.E. Mouawad, N. Nishimura, Reconfiguration of dominating sets, in: Z. Cai, A. Zelikovsky, A. Bourgeois (Eds.), COCOON 2014, in: _LNCS_ , vol. 8591, Springer, Heidelberg, 2014, 405–416.


# Anti-Icing Properties of $\text{CeO}_{2}$ Coatings at Very Low Temperatures

Anna Cecilie Åsland [a] Simon P. Cooil  [b] Damir Mamedov  [c] Håkon I. Røst
[a,d] Johannes Bakkelund  [a] Zheshen Li  [e] Smagul Karazhanov  [c] Justin W.
Wells  *[a,b]

###### Abstract

## Introduction

Icing on surfaces is a huge problem in society 1, 2, 3. The ice can cause
power outages and dangerous situations within transportation and
communications, and removing the ice without damaging the surfaces on which it
has formed can be challenging and costly 1, 2, 3, 4, 5, 6, 7, 8. A possible
solution is to cover the ice-exposed surfaces with anti-icing coatings, and
several different coatings already exist 3, 2, 6, 1, 9, 10. It is important
that these coatings are suitable matches for the systems to which they will be
applied and the conditions in which they will operate. For example, coatings
that will be used on photovoltaics need an electronic band gap allowing
transmission of light within the active energy region (range of suitable
excitation energies) of the photovoltaic 5.

Thin ($50-400\,$nm thick) films of $\text{CeO}_{2}$ can potentially be used as
anti-icing coatings for photovoltaics because of their suitable band gap,
abundance, and robustness 11. They are hydrophobic and anti-fouling, and their
hydrophobicity can be enhanced by structuring the surface and/or applying
hydrocarbons 11, 12. Although hydrophobic coatings made from composites of
$\text{CeO}_{2}$ have previously been shown to be anti-icing, these studies
did not include sputtered thin film $\text{CeO}_{2}$ coatings and only
investigated the anti-icing properties down to temperatures of $T=170\,$K 13,
14, 15. Hence, it is not clear how the other molecules in the $\text{CeO}_{2}$
composites impact the anti-icing properties, or whether $\text{CeO}_{2}$-based
coatings are anti-icing at lower temperatures.

A variety of techniques have been used to evaluate the anti-icing properties
of coatings and their suitability for specific applications 13, 14, 11, 16.
However, X-ray photoelectron spectroscopy (XPS), a technique well suited to
determine the chemical composition and chemical environment of the elements of
surfaces receives much less attention and is often only used for checking the
quality/chemical composition of the coating in question 17, 18, 19, 20, 21,
22, 23 or investigating the resulting surface chemistry changes post treatment
20. The ability to study water and ice with XPS is well documented and
relatively straight forward24, 25, however, few studies are using XPS to
monitor the in-situ ice formation on anti-icing coatings.

Here we investigate the anti-icing capabilities and chemical composition of
thin film $\text{CeO}_{2}$ coatings in-situ using XPS. Measurements are
performed over a wide temperature range before and after exposing various
$\text{CeO}_{2}$ samples to water at temperatures as low as $T\approx
100\,\text{K}$. If no ice is observed following these conditions, the material
under investigation could be ascribed to possess outstanding anti-icing
capabilities, while also demonstrating the proof of concept for future XPS
studies of this type.

## Results and Discussion

Figure 1: Characterisation of the $\text{CeO}_{2}$ films. (a) Scanning
electron microscopy (SEM) and (b) X-ray diffraction (XRD) of a $200\,$nm thick
$\text{CeO}_{2}$ coating. In (b) (111), (200), (220), (331) and (222) indicate
the crystallographic planes corresponding to each peak in the XRD pattern. (c)
Overview X-ray photoelectron spectroscopy (XPS) measurement of a $50\,$nm
$\text{CeO}_{2}$ coating which has been heated at $T=870\,\text{K}$ in air
after growth (air-treated sample), and then to $T=1000\,\text{K}$ in vacuum.
The measurement was performed at $T\approx 320\,\text{K}$ with a
photoexcitation energy of $h\nu=600\,$eV.

The $\text{CeO}_{2}$ coatings were grown by sputter-deposition of Ce onto a Si
substrate in an oxygen-rich atmosphere (24%) as detailed in previous works 11.
Scanning electron microscopy (SEM) and X-ray diffraction (XRD) measurements of
the as-grown material are shown in Figure 1 panels (a) and (b), respectively.
SEM reveals that the samples are relatively uniform, whilst the XRD confirms a
fcc crystal structure (space group 225) with a lattice parameter of $a=5.4\,$Å
26. The diffraction peaks centred at $2\theta=28.7^{\circ}$, 33.3∘, 47.7∘,
56.5∘ and 59.4∘ were identified as reflections from the (111), (200), (220),
(311) and (222) planes, respectively, according to the JCPDS card #34-039. The
peak labelled (200) also contains a contribution from the underlying Si
substrate, indicating that the Si substrate is distorted, seemingly due to
internal stress caused by interactions between the substrate and the
$\text{CeO}_{2}$ coating 27.

XPS measurements were performed on two samples ($t\approx 50\,\text{nm}$): an
as-grown sample and an air-treated sample heated to $T=870\,\text{K}$ in air
after growth, in order to ascertain whether post heating the samples in air
plays any role in the anti-icing properties. Heating in an oxygen-deficient
atmosphere has been shown to change the ratio of $\text{Ce}^{4+}$ and
$\text{Ce}^{3+}$ in the coating due to a loss of O from the surface 12. Both
samples were mounted on the same sample holder to ensure equal treatment
during the experiment. Previous studies have shown that hydrocarbons on the
surface of $\text{CeO}_{2}$ can possibly cause or enhance its hydrophobicity
11, 28. For samples exposed to the atmosphere, a layer of hydrocarbons and
other carbon species (a.k.a. adventitious or surface carbon) normally covers
the surface 29. In order to investigate the anti-icing properties of
$\text{CeO}_{2}$ itself, the samples were heated to $T=1000\,\text{K}$ in
vacuum to remove the surface carbon. Figure 1(c) shows the overview XPS
measurement of the air-treated sample after the in-vacuum heating. As
expected, the most intense features in the spectra are related to the
photoemission of Ce and O, together with weak signatures of Si from the
underlying substrate. The peak labelled X is probably from Pr or Ta impurities
in the sputtering target used to grow the $\text{CeO}_{2}$, but can also be Mo
from the sample holder. A small C 1s peak indicates that not all carbon
species were removed during heating. The relative composition of Ce, O, and C
atoms on the surface (Ce:O:C) was calculated from the overview XPS
measurements for both samples and found to be: 1:2:4 before and 1:2:2 after
in-vacuum heating for the as-grown sample and 1:3:8 before and 1:2:1 after in-
vacuum heating for the air-treated sample. For both samples, there are 2-3
O-atoms for every Ce-atom, which is as expected for $\text{CeO}_{2}$ grown by
sputter deposition 12. A small reduction in the photoemission intensity from O
1s is observed consistent with the change from $\text{Ce}^{4+}$ to
$\text{Ce}^{3+}$ as previously discussed. A larger reduction of carbon species
is observed on the air-treated sample relative to the as-grown sample
following heating in vacuum, which could indicate that surface carbon is more
loosely bound. For both samples, however, the surface carbon is significantly
reduced.

To investigate the anti-icing properties of the $\text{CeO}_{2}$ coatings, the
samples were cooled to $T=100\,\text{K}$, and $\text{H}_{2}\text{O}$ was
leaked into the vacuum system at a constant pressure of $1\times
10^{-8}\,\text{mbar}$ for 10 min. This is equivalent to a dose of $(5\pm 1)\,$
Langmuir (atomic layers) 30. Assuming a sticking coefficient of $1$, i.e. that
all the deposited $\text{H}_{2}\text{O}$ adheres to the cold surface, this
corresponds to a $(1.4\pm 0.3)\,\text{nm}$ thick layer of ice.

Figure 2: Overview X-ray photoelectron spectroscopy (XPS) measurement of two
$50\,$nm thick $\text{CeO}_{2}$ coatings (as-grown and air-treated), and their
Mo sample holder, after exposure to $\text{H}_{2}\text{O}$. The samples and
the sample holder were kept at $T\approx 100\,\text{K}$ during the exposure
and the measurement, and measured with a photoexcitation energy of
$h\nu=600\,$eV.

Overview spectra of both samples measured after exposure to
$\text{H}_{2}\text{O}$ are shown in Figure 2. It can be seen that there is
little difference between the air-treated and as-grown samples, or any notable
change from the air-treated spectra presented in Figure 1(c). Hence, there
appears to be no ice (or very little ice) on the surface of either of the
$\text{CeO}_{2}$ samples. A rough quantification of the overview spectra in
Figure 2 yields Ce:O ratios of 1:4 (as-grown) and 1:2 (air-treated). In other
words, there is no significant increase in O on the sample surfaces after
exposure to $\text{H}_{2}\text{O}$ compared to just after heating. It can
therefore be inferred that the O 1s signal is mainly due to O in
$\text{CeO}_{2}$, and not from ice on the $\text{CeO}_{2}$ surface.
Contrarily, the Mo sample holder has a very large photoemission signal
originating from O. The O 1s and O KLL components are too large relative to
the Mo peaks to allow them to be attributed to Mo oxides. Furthermore, the
binding energy of the Mo 3d peak agrees with the accepted binding energy of
metallic Mo but is lower than that of oxidised Mo, suggesting that the Mo
sample holder is not fully oxidised 31. Consequently, the vast majority of the
intensity from O must be attributed to originate from the ice layer. The
thickness of the ice layer based on the photoemission intensity is calculated
as $\approx 2.7\,\text{nm}$ (see the Supporting Information 32 for details).
These measurements suggest that the ice layer is thicker than our earlier
prediction of $\approx 1.4\,\text{nm}$ estimated from the dose of
$\text{H}_{2}\text{O}$. However, the two estimates are consistent within a
factor of 2. Given the assumptions of these simple estimates (for example,
both assume a uniform overlayer thickness, which is likely not the case in
reality), one can expect a significant uncertainty (see further details in the
Supporting Information 32). Thus, the thickness estimates give a useful order-
of-magnitude estimate of the ice thickness, but should not be taken as precise
values. Ultimately, it is safe to conclude that the XPS measurements clearly
show that there is ice on the sample holder, but not on the $\text{CeO}_{2}$
surfaces.

High-resolution spectra of the O 1s and Ce 4p core-level from throughout the
experiments are presented in Figures 3 and 4, respectively. Deconvolution of
the photoemission profiles is undertaken through fitting pseudo-Voigt line
shapes and Shirley background step functions. The intensity is then normalised
to the total background intensity 32. As is shown in Figure 3 the measured
profile required 3 components to fit and are assigned as follows: O1 (dark
blue) corresponding to photoemission from $\text{Ce}^{4+}$, O2 (medium blue)
is assigned to photoemission from $\text{Ce}^{3+}$ along with hydroxyls (-OH)
and carbonates ($\text{-CO}_{3}$) similar to References 12, 33, 34 and 35. The
component labelled O3 (light blue) is ascribed $\text{SiO}_{2}$ from the
underlying oxidised Si substrate 33, 12, 34.

Figure 3: Photoemission intensity of the O 1s core level of the as-grown ((a)
and (b)) and air-treated ((c) and (d)) samples measured with photoexcitation
energy $h\nu=650\,$eV. (a) and (c) were measured at $T\approx 320\,$K after
heating to $T=1000\,$K in vacuum. (b) and (d) were measured at $T\approx
100\,$K after $\text{H}_{2}\text{O}$ exposure. The O1 peak (dark blue)
represents $\text{Ce}^{4+}$, the O2 peak (medium blue) represents
$\text{Ce}^{3+}$, -OH and $\text{-CO}_{3}$, and the O3 peak (light blue)
represents $\text{SiO}_{2}$.

As discussed earlier, the reduction of $\text{Ce}^{4+}$ to $\text{Ce}^{3+}$
during air treatment is known to occur, and is further confirmed by the higher
intensity of the component relating to $\text{Ce}^{3+}$ in the O 1s profile
for the air-treated sample in Figure 3 panels (c) and (d), compared to the as-
grown sample shown in panels (a) and (b). This reduction is also known to
occur for prolonged exposure to ultra-high vacuum (UHV) environments 12, 35
hence, an increase in the $\text{Ce}^{3+}$ component is expected during the
experiment. Although the increase in $\text{Ce}^{3+}$ is slightly higher in
our measurements than that found by Khan et al. 12, $\text{H}_{2}\text{O}$
exposure is not expected to result in further reduction at temperatures below
$650\,$K 15. The intensity increase could also be due to an increased amount
of $\text{-CO}_{3}$ or -OH, however, from the C 1s core level (see Figure S1
in the Supporting Information 32) the amount of $\text{-CO}_{3}$ was found to
decrease, and the amount of C-OH increased only slightly. Finally, the
component relating to the oxidised Si substrate is reduced or unchanged after
$\text{H}_{2}\text{O}$ exposure. Considering all of these factors it is
difficult to assign any of the observed component variations to the growth of
an ice layer on either of the $\text{CeO}_{2}$ samples.

Figure 4: Photoemission intensity of the Ce 4p core level of the as-grown ((a)
and (b)) and air-treated ((c) and (d)) samples measured with photoexcitation
energy $h\nu=600\,$eV. (a) and (c) were measured at $T\approx 320\,$K after
heating in to $T=1000\,$K in vacuum. (b) and (d) were measured at $T\approx
100\,$K after $\text{H}_{2}\text{O}$ exposure. The measured envelope is
deconvoluted into one spin-orbit coupled doublet, $\text{P1}_{3/2}$ and
$\text{P1}_{1/2}$ (dark purple), a charge transfer related satellite,
$\text{P2}_{3/2}$ (light purple), and a shake-up satellite, $\text{P3}_{3/2}$
(medium purple). The peaks labelled dynamic effects (grey) are assigned to
Coster-Kronig transitions.

The photoemission intensity from the Ce 4p region shown in Figure 4 is similar
to previous measurements11, 36, 37, and changes very little after
$\text{H}_{2}\text{O}$ exposure. $\text{CeO}_{2}$ has mixed valency, meaning
that its 4f orbital is close to the Fermi-level and can either be occupied or
unoccupied 38, 39. As a consequence of this, there are atoms with different
electronic configurations both in the ground state and after the creation of a
photohole during the photoemission process 38, 39. The measured kinetic energy
of the emitted electron will depend on the final state electronic
configuration 38. Thus, the mixed valency causes additional peaks and complex
intensity variations in the measured spectra 38, 39, 36. Even if such final
state effects are not commonly seen in XPS, they are well known for
$\text{CeO}_{2}$ and similar oxides of f-block elements 38, 39, 11, 36, 40,
41. For $\text{CeO}_{2}$ the different final states result in three main
doublets, P1, P2 and P3, shown in Figure 4 as dark ($\text{P1}_{3/2}$ and
$\text{P1}_{1/2}$), light ($\text{P2}_{3/2}$) and medium ($\text{P3}_{3/2}$)
purple, respectively 11, 36, 38. The separations between the peaks are
reported in Table 1 and predominately agree with those found in literature 36.
The separations labelled with an asterisk are larger than previously reported,
however, the uncertainty in their position is larger at this stage in the
experiment, as the intensity of the $\text{P2}_{3/2}$ peak is small and
difficult to distinguish from the other peaks related to dynamic effects.

The peaks labelled “dynamic effects” (grey) are thought to be caused by
Coster-Kronig transitions for which the final state photoholes are in the same
main shell as the emitted electron 42, 36. The total intensity of peaks
related to Coster-Kronig transitions is somewhat lower at $100\,$K compared to
at $1000\,$K, suggesting that there are fewer Coster-Kronig transitions after
cooling and $\text{H}_{2}\text{O}$ exposure.

Table 1: Energy separation between the peaks in the Ce 4p spectra. Separation | As-grown | Air-treated
---|---|---
between |  $1000\,$K |  $100\,$K |  $1000\,$K |  $100\,$K
$\text{P1}_{3/2}$ and: |  | $+\text{H}_{2}\text{O}$ |  | $+\text{H}_{2}\text{O}$
$\text{P1}_{1/2}$ |  $16.7\,$eV |  $16.7\,$eV |  $16.7\,$eV |  $16.7\,$eV
$\text{P2}_{3/2}$ |  $8.0\,$eV* |  $6.7\,$eV |  $7.3\,$eV* |  $6.5\,$eV
$\text{P3}_{3/2}$ |  $13.6\,$eV |  $13.8\,$eV |  $13.8\,$eV |  $13.7\,$eV

XPS measurements showing the evolution of the valence band maximum and O 1s,
Ce 4p, and C 1s core levels after the samples have been loaded into the vacuum
chamber, heated to increasingly higher temperatures, and cooled and exposed to
$\text{H}_{2}\text{O}$ have been included in the Supporting Information 32.
These spectra shift towards lower binding energies when heated, and shift
(partly) back upon cooling and $\text{H}_{2}\text{O}$ exposure. Binding energy
shifts have also been observed in previous studies and were explained by the
transition from $\text{Ce}^{4+}$ to $\text{Ce}^{3+}$ 36, 34. However, there
the shifts were towards higher binding energies upon heating in vacuum, i.e.
opposite to the shifts observed in the spectra presented in this manuscript
36, 34. Possible explanations of the shifts include (temperature dependent)
changes in the electrostatic potential at the surface or at the interface
between the $\text{CeO}_{2}$ coating and the Si substrate, potentially caused
by adsorbates, band bending, or resistivity changes of the $\text{CeO}_{2}$
43, 44, 32. The spectra from the as-grown sample shifted only partly back to
higher binding energies when it was cooled, indicating that heating removed
some surface adsorbates which acted as $n$-type dopants before the surface was
heated.

## Conclusion

The anti-icing properties of $\approx 50\,$nm thick $\text{CeO}_{2}$ coatings
have been investigated before and after exposing the cold sample surfaces to
$(5\pm 1)\,$ Langmuir of $\text{H}_{2}\text{O}$, equivalent to $(1.4\pm
0.3)\,\text{nm}$ of ice. Via analysis of high-resolution core level
spectroscopy, it was shown that ice does not form on the sample surfaces, even
if the measurements indicated that a $\approx 2.7\,\text{nm}$ thick layer of
ice had formed on the surrounding areas. Both the O 1s and Ce 4p spectra have
their main component related to $\text{CeO}_{2}$ and show little change before
and after exposure to $\text{H}_{2}\text{O}$. The film that received a post-
growth in-air treatment appears to have a slightly higher proportion of
$\text{Ce}^{3+}$ compared to the as-grown film, however, this does not seem to
have a noticeable effect on the anti-icing properties. Since post-growth
treatment is not required, the coatings can be made more efficiently and
affordable compared to many other coatings 3, 9 making them ideal candidates
for anti-icing applications. Additionally, it has been demonstrated that XPS
is a sensitive and suitable method to evaluate the anti-icing properties of
surfaces and coatings.

## Supporting Information

The Supporting Information 32 at [insert link] include References 26, 45, 46,
47, 48, 49, 50, 11, 28, 34, 12, 33, 36, 37, 22, 51, 52, 53 and contain
information about the the experimental details, further details about the
normalisation and the ice thickness calculation from the XPS, additional
spectra measured after annealing the samples to increasingly higher
temperatures, and a discussion of the binding energy shifts of the spectra.

## Acknowledgements

This work was partly supported by the Research Council of Norway, project
numbers 262 633, 309 827, and 335 022. The authors acknowledge the staff at
the ASTRID2 synchrotron in Aarhus, Denmark, for providing access to their
synchrotron radiation facilities, and for practical assistance and
discussions.

Keywords:

## References

  * [1] A. Azimi Yancheshme, A. Allahdini, K. Maghsoudi, R. Jafari, G. Momen, _Journal of Energy Storage_ 2020, _31_ , 101638.
  * [2] H. He, Z. Guo, _iScience_ 2021, _24_ , 103357.
  * [3] B. Li, J. Bai, J. He, C. Ding, X. Dai, W. Ci, T. Zhu, R. Liao, Y. Yuan, _Coatings_ 2023, _13_ , 301.
  * [4] C. Lian, C. Emersic, F. H. Rajab, I. Cotton, X. Zhang, R. Lowndes, L. Li, _IEEE Transactions on Power Delivery_ 2022, _37_ , 972.
  * [5] R. M. Fillion, A. R. Riahi, A. Edrisy, _Renewable and Sustainable Energy Reviews_ 2014, _32_ , 797.
  * [6] S. S. Latthe, R. S. Sutar, A. K. Bhosale, S. Nagappan, C.-S. Ha, K. K. Sadasivuni, S. Liu, R. Xing, _Progress in Organic Coatings_ 2019, _137_ , 105373.
  * [7] G. Azimi, R. Dhiman, H.-M. Kwon, A. T. Paxson, K. K. Varanasi, _Nature Materials_ 2013, _12_ , 315.
  * [8] L. Zhou, R. Liu, X. Yi, _Ocean Engineering_ 2022, _260_ , 112008\.
  * [9] L. Cao, A. K. Jones, V. K. Sikka, J. Wu, D. Gao, _Langmuir_ 2009, _25_ , 12444.
  * [10] M. J. Kreder, J. Alvarenga, P. Kim, J. Aizenberg, _Nature Reviews Materials_ 2016, _1_ , 1.
  * [11] D. Mamedov, A. C. Åsland, S. P. Cooil, H. I. Røst, J. Bakkelund, A. Allaniyazov, J. W. Wells, S. Karazhanov, _Materials Today Communications_ 2023, _35_ , 106323.
  * [12] S. Khan, G. Azimi, B. Yildiz, K. K. Varanasi, _Applied Physics Letters_ 2015, _106_ , 061601.
  * [13] S.-P. Fu, R. P. Sahu, E. Diaz, J. R. Robles, C. Chen, X. Rui, R. F. Klie, A. L. Yarin, J. T. Abiade, _Langmuir_ 2016, _32_ , 6148.
  * [14] P. Wang, C. Peng, B. Wu, Z. Yuan, F. Yang, J. Zeng, _IOP Conference Series: Materials Science and Engineering_ 2015, _87_ , 012062.
  * [15] M. A. Henderson, C. L. Perkins, M. H. Engelhard, S. Thevuthasan, C. H. F. Peden, _Surface Science_ 2003, _526_ , 1.
  * [16] J. Liang, Y. Hu, Y. Fan, H. Chen, _Surface and Interface Analysis_ 2013, _45_ , 1211.
  * [17] Y. Qi, Z. Yang, T. Chen, Y. Xi, J. Zhang, _Applied Surface Science_ 2020, _501_ , 144165.
  * [18] L.-B. Zhang, H.-X. Zhang, Z.-J. Liu, X.-Y. Jiang, S. Agathopoulos, Z. Deng, H.-Y. Gao, L. Zhang, H.-P. Lu, L.-J. Deng, L.-J. Yin, _Journal of Colloid and Interface Science_ 2023, _630_ , 1.
  * [19] B. Zhang, M. Qiao, W. Xu, B. Hou, _Journal of Industrial and Engineering Chemistry_ 2022, _115_ , 430.
  * [20] Y. Wang, J. Xue, Q. Wang, Q. Chen, J. Ding, _ACS Applied Materials & Interfaces_ 2013, _5_ , 3370.
  * [21] G. H. Major, N. Fairley, P. M. A. Sherwood, M. R. Linford, J. Terry, V. Fernandez, K. Artyushkova, _Journal of Vacuum Science & Technology A_ 2020, _38_ , 061203.
  * [22] S. Hüfner, _Photoelectron Spectroscopy_ , Springer Berlin Heidelberg 2003.
  * [23] Ph. Hofmann, _Surface Physics: An Introduction_ , Philip Hofmann 2016.
  * [24] T. Fransson, Y. Harada, N. Kosugi, N. A. Besley, B. Winter, J. J. Rehr, L. G. M. Pettersson, A. Nilsson, _Chemical Reviews_ 2016, _116_ , 7551.
  * [25] M. A. Henderson, _Surface Science Reports_ 2002, _46_ , 1.
  * [26] L. Gerward, J. Staun Olsen, L. Petit, G. Vaitheeswaran, V. Kanchana, A. Svane, _Journal of Alloys and Compounds_ 2005, _400_ , 56.
  * [27] L. Zhao, M. Steinhart, M. Yosef, S. K. Lee, T. Geppert, E. Pippel, R. Scholz, U. Gösele, S. Schlecht, _Chemistry of Materials_ 2005, _17_ , 3.
  * [28] D. J. Preston, N. Miljkovic, J. Sack, R. Enright, J. Queeney, E. N. Wang, _Applied Physics Letters_ 2014, _105_.
  * [29] T. L. Barr, S. Seal, _Journal of Vacuum Science & Technology A: Vacuum, Surfaces, and Films_ 1995, _13_ , 1239.
  * [30] H. Lüth, _Surfaces and Interfaces of Solid Materials_ , Springer Science & Business Media 2013, google-Books-ID: nzjvCAAAQBAJ.
  * [31] B. Brox, I. Olefjord, _Surface and Interface Analysis_ 1988, _13_ , 3.
  * [32] See the Supporting Information at [insert link] including References 26, 45, 46, 47, 48, 49, 50, 11, 28, 34, 12, 33, 36, 37, 22, 51, 52, 53 and information about the the experimental details, further details about the normalisation and the ice thickness calculation from the XPS, additional spectra measured after annealing the samples to increasingly higher temperatures, and a discussion of the binding energy shifts of the spectra.
  * [33] L. Martínez, E. Román, J. L. de Segovia, S. Poupard, J. Creus, F. Pedraza, _Applied Surface Science_ 2011, _257_ , 6202.
  * [34] E. J. Preisler, O. J. Marsh, R. A. Beach, T. C. McGill, _Journal of Vacuum Science & Technology B: Microelectronics and Nanometer Structures Processing, Measurement, and Phenomena_ 2001, _19_ , 1611.
  * [35] F. Zhang, P. Wang, J. Koberstein, S. Khalid, S.-W. Chan, _Surface Science_ 2004, _563_ , 74.
  * [36] K. I. Maslakov, Y. A. Teterin, A. J. Popel, A. Y. Teterin, K. E. Ivanov, S. N. Kalmykov, V. G. Petrov, P. K. Petrov, I. Farnan, _Applied Surface Science_ 2018, _448_ , 154.
  * [37] P. Burroughs, A. Hamnett, A. F. Orchard, G. Thornton, _Journal of the Chemical Society, Dalton Transactions_ 1976, pages 1686–1698.
  * [38] A. Fujimori, _Physical Review B_ 1983, _28_ , 2281.
  * [39] A. Fujimori, _Physical Review B_ 1983, _27_ , 3992.
  * [40] A. Kotani, M. Okada, T. Jo, _Physica Scripta_ 1987, _35_ , 566\.
  * [41] Å. Monsen, F. Song, Z. Li, J. Boschker, T. Tybell, E. Wahlstrœm, J. Wells, _Surface Science_ 2012, _606_ , 1360.
  * [42] R. Nyholm, N. Martensson, A. Lebugle, U. Axelsson, _Journal of Physics F: Metal Physics_ 1981, _11_ , 1727.
  * [43] G. Cabailh, J. W. Wells, I. T. McGovern, A. R. Vearey-Roberts, A. Bushell, D. A. Evans, _Applied Surface Science_ 2004, _234_ , 144.
  * [44] T. U. Kampen, G. Gavrila, H. Mendez, D. R. T. Zahn, A. R. Vearey-Roberts, D. A. Evans, J. Wells, I. McGovern, W. Braun, _J. Phys. Cond Matt._ 2003, _15_ , S2679.
  * [45] T. Xu, K. C. Adamsen, Z. Li, L. Lammich, J. V. Lauritsen, S. Wendt, _The Journal of Physical Chemistry C_ 2022, _126_ , 2493.
  * [46] A. Sassaroli, S. Fantini, _Physics in Medicine & Biology_ 2004, _49_ , N255.
  * [47] D. Y. Zemlyanov, M. Jespersen, D. N. Zakharov, J. Hu, R. Paul, A. Kumar, S. Pacley, N. Glavin, D. Saenz, K. C. Smith, T. S. Fisher, A. A. Voevodin, _Nanotechnology_ 2018, _29_.
  * [48] F. Song, Å. Monsen, Z. S. Li, E. M. Choi, J. L. MacManus-Driscoll, J. Xiong, Q. X. Jia, E. Wahlstrœm, J. W. Wells, _Surface Science_ 2012, _606_ , 1771.
  * [49] C. J. Powell, _Journal of Vacuum Science & Technology A_ 2020, _38_ , 023209.
  * [50] A. Zangwill, _Physics at Surfaces_ , Cambridge University Press 1988.
  * [51] S. Astley, D. Hu, K. Hazeldine, J. Ash, R. E. Cross, S. Cooil, M. W. Allen, J. Evans, K. James, F. Venturini, D. C. Grinter, P. Ferrer, R. Arrigo, G. Held, G. T. Williams, D. Andrew Evans, _Faraday Discussions_ 2022, _236_ , 191.
  * [52] T. J. Šarapatka, _Surface Science_ 1992, _275_ , 443.
  * [53] Y. d. J. Acosta-Silva, R. Castañedo-Perez, G. Torres-Delgado, A. Méndez-López, O. Zelaya-Ángel, _Journal of Sol-Gel Science and Technology_ 2017, _82_ , 20.