[table]capposition=top

# On the spectral radius of minimally 2-(edge)-connected graphs with given
size111This work is supported by National Natural Science Foundation of China
(Nos. 12061074 and 11971274) and the China Postdoctoral Science Foundation
(No. 2019M661398).

Zhenzhen Loua, Gao Mina, Qiongxiang Huanga222Corresponding author. Email
addresses<EMAIL_ADDRESS><EMAIL_ADDRESS>
aCollege of Mathematics and Systems Science, Xinjiang University, Urumqi,
Xinjiang 830046, China

Abstract

A graph is minimally $k$-connected ($k$-edge-connected) if it is $k$-connected
($k$-edge-connected) and deleting arbitrary chosen edge always leaves a graph
which is not $k$-connected ($k$-edge-connected). A classic result of minimally
$k$-connected graph is given by Mader who determined the extremal size of a
minimally $k$-connected graph of high order in 1937. Naturally, for a fixed
size of a minimally $k$-(edge)-connected graphs, what is the extremal spectral
radius? In this paper, we determine the maximum spectral radius for the
minimally $2$-connected ($2$-edge-connected) graphs of given size, moreover
the corresponding extremal graphs are also determined.

Keywords: Minimally 2-(edge)-connected graph; spectral radius; extremal graph;
double eigenvectors

AMS Classification: 05C50 05C75

##  1 Introduction

A graph is said to be _connected_ if for every pair of vertices there is a
path joining them. Otherwise the graph is disconnected. The _connectivity_ (or
_vertex-connectivity_) $\kappa(G)$ of a graph $G$ is the minimum number of
vertices whose removal results in a disconnected graph or in the trivial
graph. The edge-connectivity $\kappa^{\prime}(G)$ is defined analogously, only
instead of vertices we remove edges. A graph is _$k$ -connected_ if its
connectivity is at least $k$ and $k$-edge-connected if its edge-connectivity
is at least $k$. It is almost as simple to check that the minimal degree
$\delta(G)$, the edge-connectivity and vertex connectivity satisfy the
following inequality:

$\delta(G)\geq\kappa^{\prime}(G)\geq\kappa(G).$

One of the most important task for characterization of $k$-connected graphs is
to give certain operation such that they can be produced from simple
$k$-connected graphs by repeatedly applying this operation[1]. This goal has
accomplished by Tutte [21] for $3$-connected graphs, by Dirac [8] and Plummer
[17] for 2-connected graphs and by Slater [18] for $4$-connected graphs. A
graph is said to be _minimally $k$-connected_ if it is $k$-connected but
omitting any of edges the resulting graph is no longer $k$-connected. Clearly,
a $k$-connected graph whose every edge is incident with one vertex of degree
$k$ is minimally $k$-connected, especially a $k$-regular and $k$-connected
graph is minimally $k$-connected.

Questions in extremal graph theory ask to maximize or minimize a graph
invariant over a fixed family of graphs. A classic result of minimally
$k$-connected graph is given by Mader who determined the extremal size of a
minimally $k$-connected graph of high order in [13]. Giving a graph class
$\mathcal{G}$ to study the bounds of spectral radius of graphs in
$\mathcal{G}$ and to characterize the extremal graphs that achieves the bound
is a famous problem in the spectral extremal graph theory [4], which attracts
some authors and have produced many interesting results published in various
magazines [16, 14, 12, 20, 24].

In the origin of researches, $\mathcal{G}$ is restricted to the graphs of
order $n$ or size $m$. For examples, Brualdi and Hoffman [4] gave an upper
bound on spectral radius in terms of size $m$: if $m\leq\binom{k}{2}$ for some
integer $k\geq 1$ then $\rho(G)\leq k-1$, with equality if and only if $G$
consists of a $k$-clique and isolated vertices. Extending this result, Stanley
[19] showed that $\rho(G)\leq\frac{\sqrt{1+8m}-1}{2}$. In particular, Nosal
[16] in 1970 proved that if $G$ is a triangle-free graph with $m$ edges then
$\rho(G)\leq\sqrt{m}$.

In the subsequent study, $\mathcal{G}$ is restricted to the graphs that have
some combinatorial structure. For examples, in 2002, Nikiforov [14, 15] showed
that $\rho(G)\leq\sqrt{2m(1-\frac{1}{r})}$ for a graph $G$ with given size
$m$. Bollobás, Lee, and Letzter 2018 studied the maximizing spectral radius of
subgraphs of the hypercube for giving size $m$ [2]. Very recently, Lin, Ning
and Wu [12] proved that $\rho(G)\leq\sqrt{m-1}$ when $G$ is non-bipartite and
triangle-free with giving size $m$. Zhai, Lin and Shu [24] obtained that if
$G$ contains no pentagon or hexagon with giving size $m$, then
$\rho(G)\leq\frac{1}{2}+\sqrt{m-\frac{3}{4}}$, with equality holds if and only
if $G$ is a book graph.

In the recent works, some authors restrict $\mathcal{G}$ to the graphs that
have connectivity. For examples, given order $n$ of a graph, Chen and Guo in
2019 showed that $K_{2,n-2}$ attained the maximal spectral radius among all
the minimally 2-(edge)-connected graphs [5]. Fan, Goryainov and Lin in 2021
proved that $K_{3,n-3}$ has the largest spectral radius over all minimally
3-connected graphs [9].

All the above studies indicate that the spectral radius of a graph are related
with the parameters of graphs( such as order $n$ and size $m$ ), structure of
graphs ( such as forbidding subgraphs ) and vertex or edge connectivity of
graphs.

Motivated by this researches, our paper is to study the spectral extremal
problem of minimally $2$-(edge)-connected graph under edge-condition
restrictions. Precisely, our aim is to give an answer to the following
question.

######  Problem 1.

Given size $m$, what is the maximum spectral radius among minimally
$k$-(edge)-connected graphs?

Denote by $SK_{2,\frac{m-1}{2}}$ the graph obtained from the complete
bipartite graph $K_{2,\frac{m-1}{2}}$ by subdividing an edge once. Set
$K_{2,\frac{m-3}{2}}*K_{3}$ is the graph obtained by identifying a maximum
degree of $K_{2,\frac{m-3}{2}}$ and a vertex of $K_{3}$ from the disjoint
union of $K_{2,\frac{m-3}{2}}$ and $K_{3}$. _A friend graph_ , denoted by
$F_{t}$, is a graph obtained from $t$ triangles by sharing a common vertex. In
this paper, we solve Problem 1 for $k=2$ and attain the unique extremal graph
in the following two theorems.

######  Theorem 1.1.

Let $G$ be a minimally 2-connected graph of size $m$.
$\mathrm{(i)}$ If $m$ is even, then $\rho(G)\leq\sqrt{m}$, the equality holds
if and only if $G\cong K_{2,\frac{m}{2}}$.
$\mathrm{(ii)}$ If $m$ is odd and $m\geq 9$, then
$\rho(G)\leq\rho_{1}^{*}(m)$, where $\rho_{1}^{*}(m)$ is the largest root of
$x^{3}-x^{2}-(m-2)x+m-3=0$, the equality holds if and only if $G\cong
SK_{2,\frac{m-1}{2}}$.

######  Theorem 1.2.

Let $G$ be a minimally 2-edge-connected graph of size $m$.
$\mathrm{(i)}$ If $m$ is even, then $\rho(G)\leq\sqrt{m}$, the equality holds
if and only if $G\cong K_{2,\frac{m}{2}}$.
$\mathrm{(ii)}$ If $m\geq 11$ is odd and $m\neq 15$, then
$\rho(G)\leq\rho_{2}^{*}(m)$, where $\rho_{2}^{*}(m)$ is the largest root of
$x^{4}-x^{3}+(1-m)x^{2}+(m-3)x+m-3=0$, the equality holds if and only if
$G\cong K_{2,\frac{m-3}{2}}*K_{3}$. If $m=15$, then
$\rho(G)\leq\frac{1+\sqrt{41}}{2}$, the equality holds if and only if $G\cong
F_{5}$.

A famous sharp lower bound of spectral radius $\rho(G)\geq\frac{2m}{n}$ giving
by L. Collatz, U. Sinogowitz in [6], equality holds if and only if $G$ is a
regular graph. Thus, the $m$-cycle has the minimal spectral radius among all
minimally 2-(edge)-connected graphs with size $m$. Therefore, by Theorems 1.1
and 1.2, we obtain that the spectral radius of a minimally 2-(edge)-connected
graph lies the interval $[2,\sqrt{m}]$. It means that a graph whose spectral
radius out of $[2,\sqrt{m}]$ will not be minimally 2-(edge)-connected which
indeed indicates the relationship of spectral radius and connectivity for a
graph.

The rest of the paper is organized as follows. In the next section, we will
give some lemmas and some properties of a minimally 2-(edge)-connected graph.
In Section 3 and 4, we will give the proof of Theorem 1.1 and 1.2,
respectively.

##  2 Preliminary

In this section, we firstly list some symbols and then write some properties
of minimally 2-(edge)-connected graphs and some useful lemmas.

Let $G$ be a graph with vertex set $V(G)=\\{v_{1},v_{2},\cdots,v_{n}\\}$ and
edge set $E(G)$. For $v\in V(G)$, $A\subset V(G)$, denote by $N(v)$ and $d(v)$
the neighborhood and the degree of the vertex $v$ in $G$, and denote
$N_{A}(v)=N(v)\cap A$, $d_{A}(u)=|N_{A}(v)|$. The adjacent matrix of a graph
$G$ is defined as the $n\times n$ square matrix $A(G)=(a_{ij})$ whose entries
are $1$ if $v_{i}v_{j}\in E(G)$, otherwise $0$. The spectral radius of $G$,
denote by $\rho(G)$, is defined to be the largest eigenvalue of $A(G)$. A
_chord_ of a graph is an edge between two vertices of a cycle that is not an
edge on the cycle. If a cycle has at least one chord, then it is called a
_chorded cycle_.

A graph is 2-(edge)-connected graph if it contains a 2-vertex (edge) cut set.
A graph is minimally 2-(edge)-connected, introduced in [1], if it is a
$2$-(edge)-connected but omitting any edge the resulting graph is no longer
$2$-(edge)-connected. By definition, a 2-connected graph is also 2-edge-
connected, but vice versa. However there exists a minimally 2-connected graph
that is not minimally 2-edge-connected, for example the graph $H(2,2)$ shown
as Fig.1. There exists a minimally 2-edge-connected graph that is not
minimally 2-connected, for example the graph $C_{n}*C_{m}$. Clearly, $C_{n}$
is both of minimally 2-(edge)-connected. Furthermore, we will give some the
properties of a minimally 2-(edge)-connected graph.

######  Lemma 2.1 ([8]).

A minimally 2-connected graphs with more than three vertices contains no
triangles.

######  Lemma 2.2 ([1]).

Every cycle of a minimally 2-connected graph contains at least two vertices of
degree two.

######  Lemma 2.3 ([17]).

$G$ is a minimally 2-connected graph if and only if no cycle of $G$ has a
chord.

######  Lemma 2.4 ([3]).

If $G$ is a minimally 2-(edge)-connected graph, then $\delta(G)=2$.

######  Lemma 2.5.

A $2$-edge-connected subgraph of a minimally $2$-edge-connected graph is also
minimally $2$-edge-connected.

###### Proof.

Let $G$ be a minimally 2-edge-connected graph, and $H$ be a 2-edge-connected
subgraph of $G$. By contrary that $H$ is not minimal, then there exists an
edge $uv\in E(H)$ such that $H-uv$ is 2-edge-connected. Since $G$ is a
minimally 2-edge-connected graph, we get that $G-uv$ is $1$-edge-connected.
Thus $G-uv$ has a cut edge, say $xy,$ which divides $V(G-uv)$ into two
vertices sets $U$ and $V$ such that $x\in U$ and $y\in V$, and so
$e_{G-uv}(U,V)=1$. Also we have $u\in U$ and $v\in V$ since $G$ is a 2-edge-
connected graph. Noticed that $H-uv$ is a subgraph of $G-uv$ that is assumed
to be 2-edge connected, we claim that $H-uv$ has a cycle $C$ connecting $u$
and $v$ which must be contained in $G-uv$. It is a contradiction. Thus, $H$ is
a minimally 2-edge-connected graph. ∎

######  Lemma 2.6.

If $G$ is a minimally 2-edge-connected graph, then no cycle of $G$ has a
chord.

###### Proof.

Suppose by contrary that the cycle of the minimally 2-edge-connected graph $G$
has a chord. Then $G$ contains a chorded cycle, which is not minimally 2-edge-
connected. This is a contradiction from Lemma 2.5. ∎

Recall that $\kappa(G)$ ($\kappa^{\prime}(G)$) denoted the vertex connectivity
(edge connectivity) of $G$.

######  Lemma 2.7.

If $G$ be a minimally 2-edge-connected graph with no cut vertex, then $G$ is
minimally 2-connected.

###### Proof.

Since $G$ is a 2-edge-connected graph and $G$ has no cut vertex, we have
$2=\kappa^{\prime}(G)\geq\kappa(G)\geq 2$, and so $\kappa(G)=2$. Note that $G$
is minimally 2-edge connected. We have
$\kappa(G-e)\leq\kappa^{\prime}(G-e)\leq 1$ for any $e\in E(G)$. Thus $G$ is
minimally 2-connected. ∎

######  Lemma 2.8 ([7]).

Let $G$ be a graph with adjacency matrix $A(G)$, and let $\pi$ be an equitable
partition of $G$ with quotient matrix $B_{\pi}$. Then $\det(xI-
B_{\pi})\mid\det(xI-A(G)).$ Furthermore, the largest eigenvalue of $B_{\pi}$
is just the spectral radius of $G$.

By Lemma 2.8, we can give the bound of the spectral radius of
$SK_{2,\frac{m-1}{2}}$.

######  Lemma 2.9.

For odd number $m>5$, we have $\rho(SK_{2,\frac{m-1}{2}})$ is the largest root
of $x^{3}-x^{2}-(m-2)x+m-3=0$ and
$\sqrt{m-2}<\rho(SK_{2,\frac{m-1}{2}}))<\sqrt{m-1}$.

###### Proof.

The vertices set of $SK_{2,\frac{m-1}{2}}$ has equitable partition and the
quotient matrix is

$\displaystyle B_{\pi}=\begin{array}[]{ll}\begin{pmatrix}1&1&0\\\
1&0&\frac{m-3}{2}\\\ 0&2&0\end{pmatrix}\end{array}.$

We have $f(x)=\det(xI_{3}-B_{\pi})=x^{3}-x^{2}-(m-2)x+m-3$. By Lemma 2.8,
$\rho(SK_{2,\frac{m-1}{2}})$ is the largest root of $f(x)=0$. Moreover, one
can verify that $f(\sqrt{m-2})<0$, and so
$\rho(SK_{2,\frac{m-1}{2}})>\sqrt{m-2}$. Also, we have
$f(\sqrt{m-1})=\sqrt{m-1}-2>0$ for $m\geq 6$ and
$f^{\prime}(x)=3x^{2}-2x-(m-2)>0$ for $x\geq\sqrt{m-1}$. Thus,
$\rho(SK_{2,\frac{m-1}{2}})<\sqrt{m-1}$. ∎

Notice that if each edge of a $k$-connected graph is incident with at least
one vertex of degree $k$ then the graph is minimally $k$-(edge)-connected.
Clearly, $SK_{2,\frac{m-1}{2}}$ is the minimally $2$-(edge)-connected.
Moreover, we have the following lemma.

######  Lemma 2.10.

Let $G^{*}$ attain the maximum spectral radius among all minimally 2-edge-
connected graph of size $m\geq 6$, then $\rho(G^{*})>\sqrt{m-2}$.

###### Proof.

If $m$ is even, then
$\rho(G^{*})\geq\rho(K_{2,\frac{m}{2}})=\sqrt{m}>\sqrt{m-2}$ since
$K_{2,\frac{m}{2}}$ is minimally 2-edge-connected. If $m$ is odd, then
$\rho(G^{*})\geq\rho(SK_{2,\frac{m-1}{2}})>\sqrt{m-2}$ from Lemma 2.9. ∎

######  Lemma 2.11 ([10, 11]).

Let $G$ and $H$ be two graphs, and let $P(G,x)$ be the characteristic
polynomial of $G$.
$\mathrm{(i)}$ If $H$ is a proper subgraph of $G$, then $\rho(H)<\rho(G)$.
$\mathrm{(ii)}$ If $P(H,\lambda)>P(G,\lambda)$ for $\lambda\geq\rho(G)$, then
$\rho(H)<\rho(G)$.

######  Lemma 2.12 ([14, 15]).

Let $G$ be a $C_{3}$-free graph of size $m$. Then $\rho(G)\leq\sqrt{m}$, the
equality holds if and only if $G\cong K_{a,b}$, where $ab=m$.

######  Lemma 2.13 ([23]).

Let $u$, $v$ be two distinct vertices in a connected graph $G$, $\\{v_{i}\mid
i=1,2,\ldots,s\\}\subseteq N_{G}(v)\setminus N_{G}(u)$.
$X=(x_{1},x_{2},\ldots,x_{n})^{T}$ is the Perron vector of $G$, where $x_{i}$
is corresponding to $v_{i}$ ($1\leq i\leq n$). Let $G^{\prime}=G-\\{vv_{i}\mid
1\leq i\leq s\\}+\\{uv_{i}\mid 1\leq i\leq s\\}$. If $x_{u}\geq x_{v}$, then
$\rho(G)<\rho(G^{\prime})$.

######  Lemma 2.14 ([7]).

Let $G$ be a connected graph with Perron vector
$X=(x_{1},x_{2},\ldots,x_{n})^{T}$. Let $U$, $V$ and $W$ be three disjoint
subsets of $V(G)$ such that there are no edges between $V$ and $W$. Let
$G^{\prime}$ be the graph obtained from $G$ by deleting the edges between $V$
and $U$, and adding all the edges between $V$ and $W$. If $\sum_{u\in
U}x_{u}\leq\sum_{w\in W}x_{w}$, then $\rho(G)<\rho(G^{\prime})$.

######  Lemma 2.15 ([22]).

Let $(H,v)$ and $(K,w)$ be two connected rooted graphs. Then

$\rho((H,v)*(K,w))\leq\sqrt{{\rho(H)}^{2}+{\rho(K)}^{2}},$

the equality holds if and only if both $H$ and $K$ are stars, where
$(H,v)*(K,w)$ is obtained by identifying $v$ and $w$ from disjoint union of
$H$ and $K$.

##  3 Proof of Theorem 1.1

In this section, we will give the proof of Theorem 1.1. Let $G^{*}$ attain
maximal spectral radius $\rho^{*}=\rho(G^{*})$ among all minimally 2-connected
graphs with size $m$. Lemma 2.1 and Lemma 2.4 indicate $G^{*}$ has no
triangles and $\delta(G^{*})=2$. First, by Lemma 2.12 we claim that
$G^{*}\cong K_{2,\frac{m}{2}}$ if $m$ is even. In what follows, we always
assume that $m$ is odd.

Next we will consider the structure of extremal graph $G^{*}$ for odd size
$m\geq 9$. Let $X=(x_{1},x_{2},\ldots,x_{n})^{T}$ be the Perron vector of
$G^{*}$ with coordinate $x_{u^{*}}=\max\\{x_{i}\mid i\in V(G^{*})\\}$. Denote
by $A=N(u^{*})$ and $B=V(G^{*})\setminus{(A\cup{u^{*}})}$ . Since $G^{*}$ has
no triangles, we have $e(A)=0$, that is, $\sum_{i\in A}d_{A}(i)x_{i}=0$, and
thus

$\displaystyle{\rho^{*}}^{2}x_{u^{*}}$ $\displaystyle=$
$\displaystyle\sum\limits_{v\in A}{\sum\limits_{u\in
N(v)}{x_{u}}}=d(u^{*})x_{u^{*}}+\sum_{i\in A}d_{A}(i)x_{i}+\sum_{i\in
A}d_{B}(i)x_{i}=d(u^{*})x_{u^{*}}+\sum_{i\in A}d_{B}(i)x_{i}$ (2)
$\displaystyle\leq$
$\displaystyle\left(d(u^{*})+e(A,B)\right)x_{u^{*}}=\left(m-e(B)\right)x_{u^{*}}$

By Lemma 2.10, ${\rho^{*}}^{2}>m-2$. Combining with (2), we get $e(B)<2$.
Thus, $e(B)=0$ or $1$.

In the following, we will give four claims to finish our proof.

######  Claim 3.1.

$d(u^{*})\geq 3$.

###### Proof.

Otherwise, $d(u^{*})\leq 2$. Since $G^{*}$ is minimally 2-connected, we have
$d(u^{*})\geq\delta(G^{*})=2$ by Lemma 2.4. This induces $d(u^{*})=2$ and so
$|A|=2$. We may assume $A=\\{u_{1},u_{2}\\}$. Note that $e(B)=0$ or $1$. If
$e(B)=0$ then each vertex in $B$ is adjacent with both of $u_{1}$ and $u_{2}$
since $\delta(G^{*})=2$. This leads to the size of $G^{*}$ is even, a
contradiction. Thus $e(B)=1$, and we may assume $B=\\{w_{1}w_{2}\\}\cup I$,
where $I=\\{v_{1},v_{2},\ldots,v_{t}\\}$ is isolated vertices set. Moreover,
we see that each $v_{i}$ is adjacent to $u_{j}$ for $j=1,2$ due to
$\delta(G^{*})=2$, and $N_{A}(w_{1})\cap N_{A}(w_{2})=\emptyset$,
$d_{A}(w_{1})=d_{A}(w_{2})=1$ since $G$ has no triangles. Without loss of
generality, let $N_{A}(w_{1})=u_{1}$ and $N_{A}(w_{2})=u_{2}$. Now $G^{*}$ is
determined and $m=2t+5$ in this situation, where $t\geq 2$. By the symmetry,
we have $x_{u_{1}}=x_{u_{2}}$, $x_{w_{1}}=x_{w_{2}}$, and
$x_{u^{*}}=x_{v_{i}}$ for $i=1,2,\cdots,t$. Thus from $A(G^{*})X=\rho^{*}X$,
we have

$\displaystyle\left\\{\begin{array}[]{ll}\rho^{*}x_{u^{*}}&=2x_{u_{1}},\\\
\rho^{*}x_{u_{1}}&=(t+1)x_{u^{*}}+x_{w_{1}},\\\
\rho^{*}x_{w_{1}}&=x_{w_{2}}+x_{u_{1}}=x_{w_{1}}+x_{u_{1}}.\end{array}\right.$

Furthermore, we get

$({\rho^{*}}^{2}-2t-2)x_{u^{*}}=\frac{1}{\rho^{*}-1}x_{u_{1}}.$ (4)

Let
$g(\rho^{*})=({\rho^{*}}^{2}-2t-2)(\rho^{*}-1)-1={\rho^{*}}^{3}-{\rho^{*}}^{2}-(2t+2)\rho^{*}+2t+1$.
Then $g(\rho^{*})={\rho^{*}}^{3}-{\rho^{*}}^{2}-(m-3)\rho^{*}+m-4$. Since
$\rho^{*}>\sqrt{m-2}$ by Lemma 2.10 and

$g^{\prime}(\rho^{*})=3{\rho^{*}}^{2}-2\rho^{*}-(m-3)>g^{\prime}(\sqrt{m-2})=2m-2\sqrt{m-2}-3>0,$

we have $g(\rho^{*})>g(\sqrt{m-2})=\sqrt{m-2}-2>0$. Thus
${\rho^{*}}^{2}-2t-2>\frac{1}{\rho^{*}-1}$. Therefore, from (4) we get
$x_{u^{*}}<x_{u_{1}}$, which contradicts the maximality of $x_{u^{*}}$. ∎

$u^{*}$$u^{*}$$A_{1}$$A_{2}$$B$$H$$H(s,t)$$v_{1}$$v_{s}$$v_{2}$$u_{1}$$u_{2}$$u_{t}$$w_{1}$$w_{2}$$\cdots$$\cdots$$\cdots$$\cdots$
Figure 1: The graphs $H$ and $H(s,t)$, where $s,t\geq 1$.

######  Claim 3.2.

$e(B)=1$.

###### Proof.

Suppose to the contrary that $e(B)=0$, that is, $B$ induces an independent
set. Recall that $A$ is independent, for $u\in B$, it lies in a $4$-cycle
$C=(u,v_{1},u^{*},v_{2})$ where $v_{1},v_{2}\in A$. There is at least one of
$v_{1}$ and $v_{2}$ having degree three since otherwise $u^{*}$ will be a cut
vertex. Also there is at least one of $v_{1}$ and $v_{2}$ having degree two
since otherwise $C$ contains at most one vertex of degree two, which
contradicts Lemma 2.2. It implies that $d(u)=2$ due to $d(u^{*})\geq 3$, and
then we may assume that $d(v_{1})=2$ and $d(v_{2})\geq 3$. In addition, the
vertex as $v_{2}$ in $A$ is unique, because two vertices ( in $A$ ) of degree
greater than $2$ must lie in a $4$-cycle along with $u^{*}$ and in this cycle
there have been three vertices of degree greater than $2$. Therefore, $G^{*}$
is isomorphic to $H$ showed in Fig.1. By quotient matrix of $H$, we have
$\rho^{*}=1+\sqrt{\frac{m-1}{3}}<\sqrt{m-2}$ for $m\geq 9$, which contradicts
Lemma 2.10. Thus $e(B)=1$. ∎

######  Claim 3.3.

$G^{*}[B]=K_{2}$.

###### Proof.

Otherwise, by Claim 3.2, we have $G^{*}[B]=\\{w_{1}w_{2}\\}\cup I$, where $I$
is nonempty isolated vertex set. Choosing a vertex $v\in I$. Clearly,
$d(v)\geq 2$. If $N(v)\subset A_{1}=\\{v\in A\mid d(v)=2\\}$, then $u^{*}$ is
a cut vertex, a contradiction. If $N(v)\subset A_{2}=A\backslash A_{1}$, then
$v$ is included in a $4$-cycle which has at most one vertex with degree two, a
contradiction. So, $|N_{A_{1}}(v)|=1$ and $|N_{A_{2}}(v)|=1$. Let $v_{1}\in
N_{A_{1}}(v)$, $v_{2}\in N_{A_{2}}(v)$. Then $u^{*}v_{1}vv_{2}$ forms a
$4$-cycle. Notice that $|N_{A}(w_{1})|,|N_{A}(w_{2})|\geq 1$. Choosing two
vertices $u_{1}\in N(w_{1})$ and $u_{2}\in N(w_{2})$, respectively, then
$u^{*}u_{1}w_{1}w_{2}u_{2}$ forms a $5$-cycle. Moreover, the $4$-cycle and
$5$-cycle either have a common vertex $u^{*}$ or have a common edge
$u^{*}v_{2}$ ($u_{2}$ coincides $v_{2}$). If the former occurs then $u^{*}$ is
a cut vertex, otherwise $G^{*}$ contains a chorded cycle, a contradiction. ∎

By Claims 3.2 and 3.3, $G^{*}[B]=\\{w_{1}w_{2}\\}$. Since $G^{*}$ has no
triangles, $N_{A}(w_{1})\cap N_{A}(w_{2})=\emptyset$. Furthermore,
$N_{A}(w_{1})\cup N_{A}(w_{2})=A$. Assume $\left|N_{A}(w_{1})\right|=s$,
$\left|N_{A}(w_{2})\right|=t$. Clearly, $s,t\geq 1$ since $\delta(G^{*})=2$.
Let ${H}(s,t)$ be a graph obtained from a double star graph $D_{s,t}$ by
joining an isolated vertex $u^{*}$ to all its leaves vertices (see Fig.1). Now
we get that $G^{*}\cong{H}(s,t)$ for some $s$ and $t$ satisfying $2s+2t+1=m$.

######  Claim 3.4.

$G^{*}\cong H(1,\frac{m-3}{2})$.

###### Proof.

Without loss of generality, we assume $s\leq t$. If $s=1$, then
$t=\frac{m-3}{2}$, and so $H(s,t)\cong H(1,\frac{m-3}{2})$. The result holds.
Suppose $G^{*}\cong H(s,t)$ for $s\geq 2$. Let $Y$ be the Perron eigenvector
of $H(s,t)$ with spectral radius $\rho=\rho(H(s,t))$, and let
$N_{A}(w_{1})=\\{v_{1},\cdots,v_{s}\\}$ and
$N_{A}(w_{2})=\\{u_{1},\cdots,u_{t}\\}$. By the symmetry,
$y_{v_{1}}=\cdots=y_{v_{s}}$ and $y_{u_{1}}=\cdots=y_{u_{t}}$. We have

$\displaystyle\left\\{\begin{array}[]{ll}\rho
y_{v_{1}}&=y_{u^{*}}+y_{w_{1}},\\\ \rho
y_{u_{1}}&=y_{u^{*}}+y_{w_{2}},\end{array}\right.$
$\displaystyle\left\\{\begin{array}[]{ll}\rho
y_{w_{1}}&=sy_{v_{1}}+y_{w_{2}},\\\ \rho
y_{w_{2}}&=ty_{u_{1}}+y_{w_{1}}.\end{array}\right.$

Then $y_{v_{1}}-y_{u_{1}}=\frac{1}{\rho}(y_{w_{1}}-y_{w_{2}})$ and then

$(\rho+1)(y_{w_{1}}-y_{w_{2}})=sy_{v_{1}}-ty_{u_{1}}=\frac{s}{\rho}(y_{w_{1}}-y_{w_{2}})+(s-t)y_{u_{1}},$

which indicates that

$(\rho+1-\frac{s}{\rho})(y_{w_{1}}-y_{w_{2}})=(s-t)y_{u_{1}}\leq 0.$

Clearly, $\rho>\frac{s}{\rho}$ since $H(s,t)$ has $K_{1,s}$ as a subgraph. It
follows that $y_{w_{1}}\leq y_{w_{2}}$. Note that $s\geq 2$, obviously,
$G^{\prime}=H(s,t)-v_{s}w_{1}+v_{s}w_{2}$ is also a minimally $2$-connected
graph. By Lemma 2.13, we have $\rho(G^{\prime})>\rho(G^{*})$, which is a
contradiction. ∎

By the definition of $SK_{2,\frac{m-1}{2}}$ and $H(1,\frac{m-3}{2})$, it is
clear that $SK_{2,\frac{m-1}{2}}\cong H(1,\frac{m-3}{2})$. Thus Claim 3.4 and
Lemma 2.9 imply the Theorem 1.1.

##  4 Proof of Theorem 1.2

In this section, we will give the proof of Theorem 1.2. As we know, a _block_
of a graph is a maximal 2-connected subgraph with respect to vertices. A block
of a graph is called _leaf block_ if it contains exactly one cut vertex. By
Lemma 2.7, a minimally 2-edge-connected graph $G$ without cut vertex is
minimally 2-connected. Otherwise, $G$ is made of some blocks including at
least two leaf blocks, in which each block is minimally 2-connected by Lemma
2.7 and they intersect at cut vertices. In general, we write $G=B(t,k)$ to
denote a minimally 2-edge-connected graph with $t$ cut vertices and $k$
blocks. If $t=0$ then $k=1$ and $G=B(0,1)$ is a type of minimally 2-connected
graph that is considered in Theorem 1.1. If $t>1$ then $k\geq 2$ and each
block of $G=B(t,k)$ has some cut vertices, in this case $G=B(t,k)$ can be
viewed as a tree if each block is regarded as an edge.

###### Proof of Theorem 1.2 (i).

We may assume that $m\geq 4$ and $X=(x_{1},\ldots,x_{n})^{T}$ is the Perron
eigenvector of $G$.

Case 1. $G$ has no cut vertices.

In this case, $G$ is minimally 2-connected. By Theorem 1.1,
$\rho(G)\leq\sqrt{m}$ and the equality holds if and only if $G\cong
K_{2,\frac{m}{2}}$, which are just required.

Case 2. $G$ has some cut vertices.

By definition, $G=B(t,k)$ for some $t\geq 1$ and $k\geq 2$. Let
$B_{1},\ldots,B_{k}$ be its $k$ blocks and $m(B_{i})=m_{i}$ for
$i=1,2,\ldots,k$. We know that each $B_{i}$ is minimally 2-connected graph and
$m=m(B(t,k))=\sum_{i=1}^{k}m_{i}$. By Theorem 1.1,
$\rho(B_{i})\leq\sqrt{m_{i}}$, and the equality holds if and only if
$B_{i}\cong K_{2,\frac{m_{i}}{2}}$ for $i=1,2,\ldots,k$. Notice that each
$B_{i}$ is not a star since $B_{i}$ is minimally 2-connected. By Lemma 2.15,
we obtain

$\rho(B(t,k))<\sqrt{\rho^{2}(B_{1})+\rho^{2}(B_{2})+\cdots+\rho^{2}(B_{k})}\leq\sqrt{m_{1}+m_{2}+\cdots+m_{k}}=\sqrt{m},$

as desired. ∎

In what follows we will show (ii) of Theorem 1.2, and first we give some
lemmas and propositions for the preparations. Clearly, if we transfer a leaf
block of $B(t,k)$ to another leaf block, one can simply verify the following
result.

######  Lemma 4.1.

For a minimally 2-edge-connected graph $G=B(t,k)$, let $B_{i}$ be a leaf block
of $G$ and $u\in B_{i}$ be a cut vertex. For any $v\in V(G)\setminus\\{u\\}$,
we have $G^{\prime}=G-\sum_{w\in N(u)\cap B_{i}}wu+\sum_{w\in N(u)\cap
B_{i}}wv$ is also minimally $2$-edge-connected.

$\cdots$$1$$2$${t_{2}}$$\vdots$$\cdots$$t_{3}$$1$$2$$F_{1}(t_{1},t_{2},t_{3})$$\cdots$$t_{1}$$t_{1}$$1$$2$${t_{2}}$$\vdots$$\cdots$${t_{3}}$$1$$2$$F_{0}(t_{1},t_{2},t_{3})$
Figure 2: The graphs $F_{0}(t_{1},t_{2},t_{3})$ and
$F_{1}(t_{1},t_{2},t_{3})$.

Denote by $u_{1}$ the maximal degree vertex of the friend graph with $t_{1}$
triangles, $u_{2}$ a maximal degree vertex of $K_{2,t_{2}}$, and $u_{3}$ a
vertex of $K_{2,t_{3}+1}$ with degree two. Let $F_{0}(t_{1},t_{2},t_{3})$ be
the graph obtained from the above three graphs by identifying $u_{1},u_{2}$
and $u_{3}$. Denote $F_{1}(t_{1},t_{2},t_{3})$ the graph by identifying a
vertex of $C_{5}$ and the maximum degree vertex of $F_{0}(t_{1},t_{2},t_{3})$
(see Fig.2), where $t_{i}\geq 0$.

In order to give the proof of Theorem 1.2 (ii), we begin by proving the
following two useful propositions.

$\cdots$$t_{1}$$w_{3}$$w_{4}$$w_{1}$$w_{2}$$u_{1}$$u_{2}$$u_{t_{2}}$$v$$\vdots$$\cdots$$v_{t_{3}}$$\cdots$$t_{1}$$w_{3}$$w_{4}$$w_{1}$$w_{2}$$u_{1}$$u_{2}$$v$$\cdots$$v_{t_{3}}$$u_{1}^{\prime}$$u^{*}$$u^{*}$$v_{1}$$v_{2}$$v_{1}$$v_{2}$$G_{1}$$G_{1}^{\prime}$$\vdots$$u_{t_{2}}$$u_{1}^{\prime}$
Figure 3: The vertex labels of $G_{1}\cong F_{1}(t_{1},t_{2},t_{3})\cup K_{1}$
and $G_{1}^{\prime}\cong F_{0}(t_{1}+1,t_{2}+1,t_{3})\cup 2K_{1}$.

######  Proposition 4.1.

$\rho(F_{1}(t_{1},t_{2},t_{3}))<\rho(F_{0}(t_{1}+1,t_{2}+1,t_{3}))$, where
$F_{1}(t_{1},t_{2},t_{3})$ and $F_{0}(t_{1}+1,t_{2}+1,t_{3})$ have the same
number of edges

$m=\left\\{\begin{array}[]{ll}3t_{1}+2t_{2}+2t_{3}+7&\ \ \mbox{for any
$t_{1}\geq 0$, $t_{2}=0$ or $\geq 2$ and $t_{3}\geq 1$},\\\ 3t_{1}+2t_{2}+5&\
\ \mbox{for any $t_{1}\geq 0$, $t_{2}=0$ or $\geq 2$ and
$t_{3}=0$.}\end{array}\right.$ (6)

###### Proof.

Let $G_{1}=F_{1}(t_{1},t_{2},t_{3})\cup K_{1}$ and let

$G_{1}^{\prime}=G_{1}-(w_{1}w_{2}+w_{1}w_{3}+w_{2}w_{4})+(w_{3}w_{4}+u^{*}u_{1}^{\prime}+u_{1}^{\prime}v)\cong
F_{1}(t_{1}+1,t_{2}+1,t_{3})\cup 2K_{1},$

where the labels of $V(G_{1})$ and $V(G_{1}^{\prime})$ are shown in Fig.4.
Clearly, $\rho(G_{1})=\rho(F_{1}(t_{1},t_{2},t_{3}))$,
$\rho(G_{1}^{\prime})=\rho(F_{0}(t_{1}+1,t_{2}+1,t_{3}))$ and

$m(G_{1})=m(G_{1}^{\prime})=m=\left\\{\begin{array}[]{ll}3t_{1}+2t_{2}+2t_{3}+7&\
\ \mbox{for any $t_{1}\geq 0$, $t_{2}=0$ or $\geq 2$ and $t_{3}\geq 1$},\\\
3t_{1}+2t_{2}+5&\ \ \mbox{for any $t_{1}\geq 0$, $t_{2}=0$ or $\geq 2$ and
$t_{3}=0$.}\end{array}\right.$

It suffices to show $\rho=\rho(G_{1})<\rho^{\prime}=\rho(G_{1}^{\prime})$.

Let $Y=(y_{1},\ldots,y_{n})$ and $Z=(z_{1},\ldots,z_{n})$ be the Perron
eigenvector of $G_{1}$ and $G_{1}^{\prime}$, respectively. Then we obtain

$\displaystyle(\rho^{\prime}-\rho)Y^{T}Z$ $\displaystyle=$ $\displaystyle
Y^{T}A(G_{1}^{\prime})Z-Y^{T}A(G_{1})Z$ $\displaystyle=$
$\displaystyle\sum_{ij\in
E(G_{1}^{\prime})}(y_{i}z_{j}+z_{i}y_{j})-\sum_{ij\in
E(G_{1})}(y_{i}z_{j}+z_{i}y_{j})$ $\displaystyle=$
$\displaystyle(y_{w_{3}}z_{w_{4}}+z_{w_{3}}y_{w_{4}})+(y_{u^{*}}z_{u_{1}^{\prime}}+z_{u^{*}}y_{u_{1}^{\prime}})+(y_{u_{1}^{\prime}}z_{v}+z_{u_{1}^{\prime}}y_{v})$
$\displaystyle-[(y_{w_{1}}z_{w_{3}}+z_{w_{1}}y_{w_{3}})+(y_{w_{2}}z_{w_{1}}+z_{w_{2}}y_{w_{1}})+(y_{w_{2}}z_{w_{4}}+z_{w_{2}}y_{w_{4}})].$

Notice that $y_{u_{1}^{\prime}}=0$, $y_{w_{1}}=y_{w_{2}}$,
$y_{w_{3}}=y_{w_{4}}$, $z_{w_{1}}=z_{w_{2}}=0$ and $z_{w_{3}}=z_{w_{4}}$, we
have

$\displaystyle(\rho^{\prime}-\rho)Y^{T}Z=2(y_{w_{3}}-y_{w_{1}})z_{w_{3}}+y_{u^{*}}z_{u_{1}^{\prime}}+y_{v}z_{u_{1}^{\prime}}.$
(7)

Since $C_{5}$ is a proper subgraph of $G_{1}$, by Lemma 2.11, we have
$\rho>\rho(C_{5})=2$. By the eigen-equation $\rho
y_{w_{1}}=y_{w_{2}}+y_{w_{3}}=y_{w_{1}}+y_{w_{3}}$, we have
$y_{w_{3}}=(\rho-1)y_{w_{1}}>y_{w_{1}}$, and so the right of (7) is more than
$0$. Note that $Y^{T}Z\geq 0$. It follows that $\rho^{\prime}>\rho$. ∎

$t_{1}$$t_{1}$$\cdots$$\vdots$$v_{1}^{\prime}$$v_{2}^{\prime}$$v_{1}$$v_{2}$$v_{t_{3}}$$\cdots$$\cdots$$u_{1}$$u_{2}$$u_{t_{2}}$$u_{1}^{\prime}$$u^{\prime}_{t_{3}+1}$$u^{*}$$v$$\cdots$$\vdots$$v_{1}^{\prime}$$v_{2}^{\prime}$$v_{1}$$v_{2}$$v_{t_{3}}$$\cdots$$\cdots$$u_{1}$$u_{2}$$u_{t_{2}}$$u_{1}^{\prime}$$u^{\prime}_{t_{3}+1}$$u^{*}$$v$$G_{2}$$G_{2}^{\prime}$
Figure 4: The vertex labels of $G_{2}\cong
F_{0}(t_{1},t_{2},t_{3})\cup(t_{3}+1)K_{1}$ and $G_{2}^{\prime}\cong
F_{0}(t_{1},t_{2}+t_{3}+1,0)\cup(t_{3}+2)K_{1}$.

######  Proposition 4.2.

$\rho(F_{0}(t_{1},t_{2},t_{3}))<\rho(F_{0}(t_{1},t_{2}+t_{3}+1,0))$, where
$F_{0}(t_{1},t_{2},t_{3})$ and $F_{0}(t_{1},t_{2}+t_{3}+1,0)$ have the same
number of edges $m=3t_{1}+2t_{2}+2t_{3}+2$, where $t_{1}\geq 0$, $t_{2}=0$ or
$\geq 2$, and $t_{3}\geq 1$.

###### Proof.

Let $G_{2}=F_{0}(t_{1},t_{2},t_{3})\cup(t_{3}+1)K_{1}$, its vertices be
labelled as in Fig.3 and the isolated set
$I_{2}=\\{u_{1}^{\prime},u_{2}^{\prime},\cdots,u_{t_{3}+1}^{\prime}\\}$. Let

$G_{2}^{\prime}=G_{2}-(\sum_{i=1}^{2}u^{*}v_{i}^{\prime}+\sum_{i=1}^{2}\sum_{j=1}^{t_{3}}v_{i}^{\prime}v_{j})+(\sum_{i=1}^{t_{3}+1}(u^{*}u_{i}^{\prime}+vu_{i}^{\prime}))\cong
F_{0}(t_{1},t_{2}+t_{3}+1,0)\cup(t_{3}+2)K_{1}.$

Clearly, $\rho(F_{0}(t_{1},t_{2},t_{3}))=\rho(G_{2})$ and
$\rho(F_{0}(t_{1},t_{2}+t_{3}+1,0))=\rho(G_{2}^{\prime})$. Also,
$F_{0}(t_{1},t_{2},t_{3})$ and $F_{0}(t_{1},t_{2}+t_{3}+1,0)$ have the same
number of edges $3t_{1}+2t_{2}+2t_{3}+2=m$. It suffices to show
$\rho=\rho(G_{2})<{\rho}^{\prime}=\rho(G_{2}^{\prime})$.

Suppose to the contrary that $\rho\geq{\rho}^{\prime}$. Let
$Y=(y_{1},\ldots,y_{n})$ and $Z=(z_{1},\ldots,z_{n})$ be the Perron
eigenvector of $G_{2}$ and $G_{2}^{\prime}$, respectively. By symmetry, we
have $y_{u_{1}^{\prime}}=0$, and $z_{v_{1}}=z_{v_{1}^{\prime}}=0$. Thus we
obtain

$\displaystyle(\rho{{}^{\prime}}-\rho)Y^{T}Z=Y^{T}A(G_{2}^{{}^{\prime}})Z-Y^{T}A(G_{2})Z=\sum_{ij\in
E(G_{2}^{{}^{\prime}})}(y_{i}z_{j}+z_{i}y_{j})-\sum_{ij\in
E(G_{2})}(y_{i}z_{j}+z_{i}y_{j})$ (8) $\displaystyle=$
$\displaystyle(t_{3}+1)(y_{u^{*}}z_{u_{1}^{\prime}}+z_{u^{*}}y_{u_{1}^{\prime}}+y_{v}z_{u_{1}^{\prime}}+z_{v}y_{u_{1}^{\prime}})-2(y_{u^{*}}z_{v_{1}^{\prime}}+z_{u^{*}}y_{v_{1}^{\prime}})-2t_{3}(y_{v_{1}}z_{v_{1}^{\prime}}+z_{v_{1}}y_{v_{1}^{\prime}})$
$\displaystyle=$
$\displaystyle(t_{3}+1)(y_{u^{*}}z_{u_{1}^{\prime}}+y_{v}z_{u_{1}^{\prime}})-2y_{v_{1}^{\prime}}z_{u^{*}}.$

By eign-equation of $A(G_{2})$ and $A(G^{\prime}_{2})$, we have

$\displaystyle\left\\{\begin{array}[]{ll}\rho y_{v}=t_{2}y_{u_{1}},\\\ \rho
y_{u_{1}}=y_{u^{*}}+y_{v}.\end{array}\right.$
$\displaystyle\left\\{\begin{array}[]{ll}\rho
y_{v_{1}^{\prime}}=y_{u^{*}}+t_{3}y_{v_{1}},\\\ \rho
y_{v_{1}}=2y_{v_{1}^{\prime}}.\end{array}\right.$
$\displaystyle\left\\{\begin{array}[]{ll}\rho^{\prime}z_{u_{1}^{\prime}}=z_{u^{*}}+z_{v},\\\
\rho^{\prime}z_{v}=(t_{3}+t_{2}+1)z_{u_{1}^{\prime}}.\end{array}\right.$

Then we obtain

$y_{v}=\frac{t_{2}}{{\rho}^{2}-t_{2}}y_{u^{*}},\ \
y_{v_{1}^{\prime}}=\frac{\rho}{{\rho}^{2}-2t_{3}}y_{u^{*}}\ \ \mbox{and}\ \
z_{u_{1}^{\prime}}=\frac{\rho^{\prime}}{{\rho^{\prime}}^{2}-(t_{3}+t_{2}+1)}z_{u^{*}}.$

From (8), we get

$\displaystyle(\rho^{\prime}-\rho)Y^{T}Z$ $\displaystyle=$
$\displaystyle(\frac{(t_{3}+1)\rho^{\prime}}{{\rho^{\prime}}^{2}-(t_{3}+t_{2}+1)}\frac{{\rho}^{2}}{{\rho}^{2}-t_{2}}-\frac{2\rho}{{\rho}^{2}-2t_{3}})y_{u^{*}}z_{u^{*}}.$
(10)

Since $\frac{(t_{3}+1)\rho^{\prime}}{{\rho^{\prime}}^{2}-(t_{3}+t_{2}+1)}$
monotonically decreases with respect to $\rho^{\prime}$ and
$\rho\geq\rho^{\prime}$, from (10) we get

$\displaystyle(\rho^{\prime}-\rho)Y^{T}Z$ $\displaystyle\geq$
$\displaystyle(\frac{(t_{3}+1)\rho}{{\rho}^{2}-(t_{3}+t_{2}+1)}\frac{{\rho}^{2}}{{\rho}^{2}-t_{2}}-\frac{2\rho}{{\rho}^{2}-2t_{3}})y_{u^{*}}z_{u^{*}}$
(11) $\displaystyle=$
$\displaystyle(\frac{t_{3}+1}{{\rho}^{2}-(t_{3}+t_{2}+1)}\frac{{\rho}^{2}}{{\rho}^{2}-t_{2}}-\frac{2}{{\rho}^{2}-2t_{3}})\rho
y_{u^{*}}z_{u^{*}}$ $\displaystyle\geq$
$\displaystyle(\frac{t_{3}+1}{{\rho}^{2}-(t_{3}+t_{2}+1)}-\frac{2}{{\rho}^{2}-2t_{3}})\rho
y_{u^{*}}z_{u^{*}}$

Let
$g(\rho)=(t_{3}+1)({\rho}^{2}-2t_{3})-2({\rho}^{2}-(t_{3}+t_{2}+1))=(t_{3}-1){\rho}^{2}-2t_{3}^{2}+2t_{2}+2$.
It is clear that $g(\rho)>0$ for $\rho>\rho(K_{2,t_{3}+1})=\sqrt{2t_{3}+2}$.
One can also verify that $\rho^{2}>t_{2}+t_{3}+1$. Hence,

$\frac{(t_{3}+1)}{{\rho}^{2}-(t_{3}+t_{2}+1)}-\frac{2}{{\rho}^{2}-2t_{3}}>0.$

From (11) we have $\rho^{\prime}>\rho$, a contradiction. Therefore,
$\rho<\rho^{\prime}$. ∎

Now is the time to prove (ii) of Theorem 1.2.

###### Proof of Theorem 1.2 (ii).

Let $G^{*}$ be the graph with the maximum spectral radius over all minimally
2-edge-connected graph of odd size $m\geq 11$, and let
$X=(x_{1},\ldots,x_{n})^{T}$ be the Perron eigenvector of $G^{*}$ with
coordinate $x_{u^{*}}=\max\\{x_{i}\mid i\in V(G^{*})\\}$. Denote by
$\rho^{*}=\rho(G^{*})$, $A=N(u^{*})$ and
$B=V(G^{*})\setminus{(A\cup{u^{*}})}$. Notice that $\delta(G^{*})=2$. Now we
give Claims 4.1-4.8 to finish the proof of Theorem 1.2 (ii).

######  Claim 4.1.

$G^{*}[A]$ is isomorphic to the union of some independent edges and isolated
vertices.

###### Proof.

On the one hand, $G^{*}[A]$ contains no cycle. Otherwise, we assume that a
cycle $C_{l}\subset G^{*}[A]$ ($l\geq 3$). Then there exists a wheel $W_{l+1}$
in $G^{*}$, it forms a chorded cycle in $G^{*}$, which contradicts Lemma 2.6.
On the other hand, $G^{*}[A]$ contains no $P_{3}$. Otherwise, $G^{*}$ contains
a chorded cycle with order $4$, a contradiction. ∎

Let $A_{1}$ be the isolated vertex set of $G^{*}[A]$. Then $A_{2}=A\setminus
A_{1}$ consists of some independent edges if $A_{2}\not=\emptyset$.

######  Claim 4.2.

$N_{B}(u)=\emptyset$ for any $u\in A_{2}$.

###### Proof.

Otherwise, there exists a vertex $v\in B$ that is adjacent to a vertex
$u_{2}\in A_{2}$. We may further assume that $u_{2}\sim u_{2}^{\prime}\in
A_{2}$. If $v$ has no neighbor in $B$, then there exists a vertex $u\in A$
adjacent to $v$ due to $\delta(G^{*})\geq 2$. It follows that

$\left\\{\begin{array}[]{ll}C=u^{*}u_{2}^{\prime}u_{2}vu_{1}\mbox{ is a cycle
with the chord $u^{*}u_{2}$ }&\mbox{ if $u=u_{1}\in A_{1}$ }\\\
C=u^{*}u_{2}^{\prime}vu_{2}\mbox{ is a cycle with the chord
$u_{2}^{\prime}u_{2}$ }&\mbox{ if $u=u_{2}^{\prime}\in A_{2}$ }\\\
C=u^{*}u_{2}^{\prime}u_{2}vu_{3}\mbox{ is a cycle with the chord
$u_{2}^{*}u_{2}$ }&\mbox{ if $u=u_{3}\in A_{2}$ }\end{array}\right.$

It is impossible since any cycle of $G^{*}$ has no chord. So, $d_{B}(v)\geq
1$. However, in this situation, there exists a path $P:=vv_{1}\cdots v_{t}$ in
$G^{*}[B]$ such that $v_{t}$ is adjacent to some $u^{\prime}\in A$ since
otherwise $u_{2}v$ will be a cut edge. By regarding $u^{\prime}$ as the above
$u$, as similar above we can find a chorded cycle in $G^{*}$, a contradiction.
∎

If $A_{2}\neq\emptyset$, then, from Claim 4.1, $\\{u^{*}\\}\cup A_{2}$ induces
$t_{1}=\frac{|A_{2}|}{2}$’s triangles with a common vertex $u^{*}$. Moreover,
we see from Claim 4.2 that each of these triangles must be a leaf block of
$G^{*}$.

######  Claim 4.3.

$e(B)=0$ or $1$.

###### Proof.

By Claims 4.1 and 4.2, we know that $A_{2}$ induces some independent edges and
$N_{B}(A_{2})=\emptyset$. Recall that $A_{1}$ induces some isolated vertices.
Clearly, $\sum_{i\in A_{1}}d_{A_{1}}(i)x_{i}=0$. From Lemma 2.10,
$\rho^{*}>\sqrt{m-2}\geq 3$ for $m\geq 11$. By symmetry, for any $i,j\in
A_{2}$, we have $x_{i}=x_{j}$ and so
$\rho^{*}x_{i}=x_{u^{*}}+x_{j}=x_{u^{*}}+x_{i}$, which induces
$x_{i}=\frac{x_{u^{*}}}{\rho^{*}-1}<\frac{x_{u^{*}}}{2}$. Then we have

$\displaystyle{\rho^{*}}^{2}x_{u^{*}}$ $\displaystyle=$ $\displaystyle
d(u^{*})x_{u^{*}}+\sum_{i\in A_{1}}d_{A_{1}}(i)x_{i}+\sum_{i\in
A_{2}}d_{A_{2}}(i)x_{i}+\sum_{i\in B}d_{A}(i)x_{i}$ $\displaystyle<$
$\displaystyle d(u^{*})x_{u^{*}}+\frac{x_{u^{*}}}{2}\sum_{i\in
A_{2}}d_{A_{2}}(i)+e(A,B)x_{u^{*}}$ $\displaystyle=$ $\displaystyle
d(u^{*})x_{u^{*}}+\frac{x_{u^{*}}}{2}\cdot 2e(A_{2})+e(A,B)x_{u^{*}}$
$\displaystyle=$ $\displaystyle(d(u^{*})+e(A)+e(A,B))x_{u^{*}}$
$\displaystyle=$ $\displaystyle(m-e(B))x_{u^{*}}.$

Combining it with $(m-2)x_{u^{*}}<{\rho^{*}}^{2}x_{u^{*}}$, we have $e(B)<2$.
It follows the result. ∎

If $e(B)=1$, we may denote $e=w_{1}^{*}w_{2}^{*}$ the unique edge in
$G^{*}[B]$ in what follows. Without loss of generality, we may assume
$d_{A}(w_{1}^{*})\leq d_{A}(w_{2}^{*})$.

######  Claim 4.4.

$G^{*}[\\{u^{*},w_{1}^{*},w_{2}^{*}\\}\cup
N_{A_{1}}(\\{w_{1}^{*},w_{2}^{*}\\})]\cong C_{5}$.

###### Proof.

Firstly, we will show $N_{A_{1}}(w_{1}^{*})\cap
N_{A_{1}}(w_{2}^{*})=\emptyset$. Otherwise, let $u_{0}\in A_{1}$ be the common
vertex. If $\\{u_{0},w_{1}^{*},w_{2}^{*}\\}$ induces a $3$-cycle, then
$u_{0}w_{1}^{*}w_{2}^{*}$ a leaf block of $G^{*}$. Thus
$G^{\prime}=G^{*}-u_{0}w_{1}^{*}-u_{0}w_{2}^{*}+u^{*}w_{1}^{*}+u^{*}w_{2}^{*}$
is minimally 2-edge-connected and $\rho(G^{\prime})>\rho(G^{*})$ by Lemma
2.13. Therefore, there exists another vertex $u_{2}\in A_{1}$ that is adjacent
to at least one of $\\{w_{1}^{*},w_{2}^{*}\\}$. It follows that

$\left\\{\begin{array}[]{ll}C=w_{2}^{*}u_{0}u^{*}u_{2}w_{1}^{*}\mbox{ is a
cycle with the chord $u_{0}w_{1}^{*}$ }&\mbox{ if $u_{2}\sim w_{1}^{*}$, }\\\
C=u^{*}u_{0}w_{1}^{*}w_{2}^{*}u_{2}\mbox{ is a cycle with the chord
$u_{0}w_{2}^{*}$ }&\mbox{ if $u_{2}\sim w_{2}^{*}$, }\\\ \end{array}\right.$

which always leads a contradiction.

Secondly, we will show $d_{A_{1}}(w_{1}^{*})=1$ and $d_{A_{1}}(w_{2}^{*})\geq
1$. In fact, since $\delta(G^{*})=2$ and
$N_{A_{2}}({w_{1}^{*}})=N_{A_{2}}({w_{2}^{*}})=\emptyset$ by Claim 4.2, we
have $d_{A_{1}}(w_{1}^{*}),d_{A_{1}}(w_{2}^{*})\geq 1$. If
$d_{A_{1}}(w_{1}^{*}),d_{A_{1}}(w_{2}^{*})\geq 2$, then $G^{*}$ contains
$H(2,2)$ (see Fig.1) as a subgraph. We see that $H(2,2)$ is not minimally
2-edge-connected, which contradicts Lemma 2.5.

Combining the above two facts, we have
$G^{*}[\\{u^{*},w_{1}^{*},w_{2}^{*}\\}\cup
N_{A_{1}}(\\{w_{1}^{*},w_{2}^{*}\\})]\cong H(1,t_{2})$ for some positive
$t_{2}\geq 1$, and clearly $H(1,t_{2})$ is a leaf block of $G^{*}$. Finally,
it suffices to show $t_{2}=1$. Suppose to the contrary that $t_{2}\geq 2$. Now
let $N_{A_{1}}(w_{1}^{*})=\\{u_{0}\\}$ and
$N_{A_{1}}(w_{2}^{*})=\\{u_{1},u_{2},\ldots,u_{t_{2}}\\}$. Then
$G^{\prime}=G^{*}-w_{1}^{*}w_{2}^{*}+w_{1}^{*}u^{*}$ is a graph obtained from
$G$ by replacing the block $H(1,t_{2})$ to $K_{2,t_{2}}*K_{3}$. Thus,
$G^{\prime}$ is also minimally 2-edge-connected. By Lemma 2.13, we have
$\rho(G^{\prime})>\rho(G^{*})$, a contradiction. ∎

Denote by $B_{1}$ the set of all isolated vertices in $B$. By Claim 4.3,
$B=B_{1}\cup\\{w_{1}^{*}w_{2}^{*}\\}$. By Claim 4.4, we may assume that
$N_{A_{1}}(w_{1}^{*})=\\{v_{1}^{*}\\}$ and
$N_{A_{1}}(w_{2}^{*})=\\{v_{2}^{*}\\}$ in what follows.

######  Claim 4.5.

$N_{B_{1}}(\\{v_{1}^{*},v_{2}^{*}\\})=\emptyset$.

###### Proof.

Suppose to the contrary that there exists a vertex $w$ in $B_{1}$ with
neighbor $v_{1}^{*}$ or $v_{2}^{*}$. Without loos of generality, we assume
$N_{A_{1}}(w)=v_{1}^{*}$. Notice that $d(w)\geq 2$. We claim that
$N_{A_{1}}(w)=\\{v_{1}^{*},v_{2}^{*}\\}$. Since otherwise, $w\sim v\in
A_{1}\backslash\\{v_{1}^{*},v_{2}^{*}\\}$, then
$u^{*}vwv_{1}^{*}w_{1}^{*}w_{2}^{*}v_{2}^{*}$ is a cycle with the chord
$v_{1}^{*}u^{*}$, a contradiction. Thus,
$W=\\{u^{*},w,w_{1}^{*},w_{2}^{*},v_{1}^{*},v_{2}^{*}\\}$ induces a minimally
2-edge-connected leaf block of $G^{*}$. By symmetry, we also have
$x_{v_{1}^{*}}=x_{v_{2}^{*}}$. Let
$G^{\prime}=G^{*}-w_{2}^{*}v_{2}^{*}+w_{2}^{*}v_{1}^{*}$. We see that $W$ also
induces a leaf block of $G^{\prime}$ and so $G^{\prime}$ is also a minimally
2-edge connected graph. By Lemma 2.13, we have $\rho(G^{\prime})>\rho(G^{*})$,
a contradiction. ∎

Let $A_{1}^{\prime}=A_{1}\backslash\\{v_{1}^{*},v_{2}^{*}\\}$. By Claim 4.5,
each vertex of $B_{1}$ only joins some vertices in $A_{1}^{\prime}$. i.e.
$N_{A_{1}}(w_{i})=N_{A_{1}^{\prime}}(w_{i})$ for any $w_{i}\in B_{1}$.

######  Claim 4.6.

$|B_{1}|\geq 2$ and $|N_{A_{1}}(w_{1})\cap N_{A_{1}}(w_{2})|=0$ or $2$ for any
$w_{1}\not=w_{2}\in B_{1}$.

###### Proof.

Firstly, we show that $|B_{1}|\geq 2$. Otherwise, we may assume
$B_{1}=\\{w_{1}\\}$, then $G^{*}[N_{A_{1}}(w_{1})\cup\\{w_{1},u^{*}\\}]\cong
K_{2,a_{1}}$, where $a_{1}=|N_{A_{1}}(w_{1})|$. By Claims 4.2, 4.4 and 4.5, we
have $G^{*}\cong F_{1}(t_{1},a_{2},0)$ for some positive $t_{1}\geq 0$,
$a_{2}\geq 2$ and $3t_{1}+2a_{2}+7=m(G^{*})=m$. By Proposition 4.1, we know
that $\rho(G^{*})=\rho(F_{1}(t_{1},a_{2},0))<\rho(F_{0}(t_{1}+1,a_{2}+1,0)$, a
contradiction.

Suppose that $|N_{A_{1}}(w_{1})\cap N_{A_{1}}(w_{2})|\geq 3$, let
$\\{v_{1},v_{2},v_{3}\\}\subseteq N_{A_{1}}(w_{1})\cap N_{A_{1}}(w_{2})$, then
$G^{*}$ contains a $5$-cycle $C_{2}=v_{1}w_{1}v_{2}w_{2}v_{3}$ with chord
$v_{1}w_{2}$, a contradiction. Next we show that $|N_{A_{1}}(w_{1})\cap
N_{A_{1}}(w_{2})|\not=1$. Otherwise, let $N_{A_{1}}(w_{1})\cap
N_{A_{1}}(w_{2})=\\{v\\}$, then $G^{*}$ contains a $6$-cycle
$C_{1}=u^{*}w_{1}^{\prime}w_{1}vw_{2}w_{2}^{\prime}$ with chord $u^{*}v$,
where $w_{1}^{\prime}\in N_{A_{1}}(w_{1})\backslash v$ and $w_{2}^{\prime}\in
N_{A_{1}}(w_{2})\backslash v$, it is a contradiction. Thus, we have
$|N_{A_{1}}(w_{1})\cap N_{A_{1}}(w_{2})|=0$ or $2$. ∎

Notice that $d_{A_{1}}(w_{i})\geq 2$ for any $w_{i}\in B_{1}$. By Claims
4.1-4.6 we can get the structure of $G^{*}$ shown as Fig.5. In particular, if
$e(B)=\emptyset$, then $G^{*}$ contains no 5-cycle
$C=u^{*}v_{1}^{*}w_{1}^{*}w_{2}^{*}v_{2}^{*}$.

$t_{1}$$v_{1}^{*}$$v_{2}^{*}$$w_{1}^{*}$$w_{2}^{*}$$r_{1}$$r_{p}$$w_{1}$$w_{p}$$\cdots$$s_{1}$$s_{2}$$s_{q}$$\cdots$$\cdots$$\cdots$$A_{1}^{\prime}$$B_{1}$$u^{*}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$w_{1}^{\prime}$$w_{2}^{\prime}$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$
Figure 5: The structure of $G^{*}$, where $t_{1}\geq 0$,
$p+\sum_{i=1}^{q}s_{i}=|B_{1}|$ and $\sum_{i=1}^{p}r_{i}+2q=|A_{1}^{\prime}|$.

For nonnegative integer $p$, $q$, $G^{*}[N_{A_{1}}(B_{1})\cup
B_{1}]\cong\bigcup_{i=1}^{p}K_{1,r_{i}}\bigcup_{j=1}^{q}K_{2,s_{j}}$ and
satisfy $3t_{1}+2\sum_{i=1}^{p}r_{i}+2\sum_{i=1}^{q}s_{i}+2q+5=m$ ($r_{i}$,
$s_{i}\geq 2$). Furthermore, we will determine the values of $p,q$.

######  Claim 4.7.

$p\leq 1$ and $q\leq 1$.

###### Proof.

We firstly show $p\leq 1$. Suppose $p\geq 2$, then there exists two vertices,
say $w_{1},w_{2}$ in $B_{1}$ with
$G^{*}[N_{A_{1}^{\prime}}(w_{i})\cup\\{w_{i}\\}=K_{1,r_{i}}$ for $i=1,2$.
Without loss of generality, we may assume that $x_{w_{1}}\geq x_{w_{2}}$.
Denote by

$G^{{}^{\prime}}=G^{*}-\sum_{v\in N_{A_{1}}(w_{2})}vw_{2}+\sum_{v\in
N_{A_{1}}(w_{2})}vw_{1}.$

By Lemma 2.13, we have $\rho(G^{{}^{\prime}})>\rho^{*}$. Clearly $w_{2}$ is an
isolated vertex of $G^{{}^{\prime}}$. Set
$G^{{}^{\prime\prime}}=G^{{}^{\prime}}-\\{w_{2}\\}$. Then
$G^{{}^{\prime\prime}}$ is also a minimally 2-edge-connected graph since
$N_{A_{1}}(w_{1})\cup N_{A_{1}}(w_{2})\cup\\{w_{1},u^{*}\\}$ induces a block
$K_{2,r_{1}+r_{2}}$ in $G^{{}^{\prime\prime}}$. However
$\rho(G^{{}^{\prime\prime}})=\rho(G^{{}^{\prime}})>\rho^{*}$, a contradiction.

Now we will show $q\leq 1$. Otherwise, $q\geq 2$. Then
$G^{*}[N_{A_{1}}(B_{1})\cup B_{1}]$ contains $K_{2,s_{1}},K_{2,s_{2}}$
($s_{1},s_{2}\geq 2$) as induced subgraphs. Denote by $w_{i}^{\prime}\in
V(K_{2,s_{i}})\cap B_{1}$ for $i=1,2$. Set
$N_{A_{1}}(w_{1}^{\prime})=\\{v_{1},v_{2}\\}$ and
$N_{A_{1}}(w_{2}^{\prime})=\\{v_{3},v_{4}\\}$. Let $X$ be the Perron vector of
$G^{*}$ whose entry $x_{v}$ is labelled by vertex $v$. By the symmetry,
$x_{v_{1}}=x_{v_{2}}$ and $x_{v_{3}}=x_{v_{4}}$. Without loss of generality,
we may assume that $x_{v_{1}}\geq x_{v_{3}}$. Then $x_{v_{1}}+x_{v_{2}}\geq
x_{v_{3}}+x_{v_{4}}$. Let
$G^{{}^{\prime\prime\prime}}=G^{*}-w_{2}^{\prime}v_{3}-w_{2}^{\prime}v_{4}+w_{2}^{\prime}v_{1}+w_{2}^{\prime}v_{2}$,
and $\rho^{\prime\prime\prime}=\rho(G^{{}^{\prime\prime\prime}})$. Clearly,
$G^{{}^{\prime\prime\prime}}$ is minimally 2-edge-connected. By Lemma 2.14, we
get $\rho^{\prime\prime\prime}>\rho^{*}$, which contradicts with the
maximality of $\rho^{*}$. ∎

By comparing Fig. 2 and Fig. 5, we have $t_{2}=r_{1}$ and $t_{3}=s_{1}$. From
Claims 4.1-4.7, we know that $G^{*}$ has two forms: $F_{0}(t_{1},t_{2},t_{3})$
or $F_{1}(t_{1}^{\prime},t_{2}^{\prime},t_{3}^{\prime})$, where
$t_{1},t_{3},t_{1}^{\prime},t_{3}^{\prime}\geq 0$, $t_{2},t_{2}^{\prime}=0$ or
$t_{2},t_{2}^{\prime}\geq 2$ and satisfy

$m=\left\\{\begin{array}[]{ll}3t_{1}+2t_{2}&\mbox{ if $t_{3}=0$}\\\
3t_{1}+2t_{2}+2t_{3}+2&\mbox{ if $t_{3}\geq 1$}\\\
3t_{1}^{\prime}+2t_{2}^{\prime}+5&\mbox{ if $t_{3}^{\prime}=0$}\\\
3t_{1}^{\prime}+2t_{2}^{\prime}+2t_{3}^{\prime}+2+5&\mbox{ if
$t_{3}^{\prime}\geq 1$}.\end{array}\right.$

Clearly, $t_{1}\geq 1$ since otherwise $m$ is even. Suppose that $G^{*}\cong
F_{1}(t_{1}^{\prime},t_{2}^{\prime},t_{3}^{\prime})$, by Proposition 4.1, we
have
$\rho(F_{1}(t_{1}^{\prime},t_{2}^{\prime},t_{3}^{\prime}))<\rho(F_{0}(t_{1}^{\prime}+1,t_{2}^{\prime}+1,t_{3}^{\prime}))$,
which contradicts the maximality of $\rho(G^{*})$. Thus $G^{*}\cong
F_{0}(t_{1},t_{2},t_{3})$, where $t_{3}\geq 0$, $t_{2}=0$ or $\geq 2$ and
satisfy

$m=\left\\{\begin{array}[]{ll}3t_{1}+2t_{2}&\mbox{ if $t_{3}=0$}\\\
3t_{1}+2t_{2}+2t_{3}+2&\mbox{ if $t_{3}\geq 1$}.\end{array}\right.$

If $t_{3}=0$, then $t_{2}=\frac{m-3t_{1}}{2}$, and thus $G^{*}\cong
F_{0}(t_{1},t_{2},0)=F_{0}(t_{1},\frac{m-3t_{1}}{2},0))$. If $t_{3}\geq 1$,
then $t_{2}+t_{3}+1=\frac{m-3t_{1}}{2}$. By Proposition 4.2, we have

$\rho\left(F_{0}(t_{1},t_{2},t_{3})\right)<\rho\left(F_{0}(t_{1},t_{2}+t_{3}+1,0)\right)=\rho\left(F_{0}(t_{1},\frac{m-3t_{1}}{2},0)\right).$

By the maximality of $\rho(G^{*})$ again, we get $G^{*}\cong
F_{0}(t_{1},\frac{m-3t_{1}}{2},0)$ for some $t_{1}\geq 1$ and
$\frac{m-3t_{1}}{2}=0$ or $\geq 2$. At last, we will show $t_{1}=1$.

######  Claim 4.8.

$G^{*}\cong F_{0}(1,\frac{m-3}{2},0)$ for $m\geq 11$ and $m\neq 15$, and
$G^{*}\cong F_{5}$ for $m=15$.

###### Proof.

Denote by $f(G,x)$ the characteristic polynomial of quotient matrix of $A(G)$.
Let

$f_{1}(x)=f(F_{0}(t_{1},\frac{m-3t_{1}}{2},0),x)=x^{4}-x^{3}+(t_{1}-m)x^{2}+(m-3t_{1})x-3{t_{1}}^{2}+mt_{1},$

where $t_{1}\geq 2$, and let
$f_{2}(x)=f(F_{0}(1,\frac{m-3}{2},0),x)=x^{4}-x^{3}+(1-m)x^{2}+(m-3)x+m-3.$
Then

$f_{1}(x)-f_{2}(x)=(t_{1}-1)x^{2}+(3-3t_{1})x-3{t_{1}}^{2}+3+(t_{1}-1)m=(t_{1}-1)g(x),$
(12)

where $g(x)=x^{2}-x+m-3(t_{1}+1)$.

If $\frac{m-3t_{1}}{2}\geq 2$, then $2\leq t_{1}\leq\frac{m-4}{3}$. Note that
$m\geq 11$. One can verify that $g(x)>0$ for $x>\sqrt{m-2}$. From (12), we
have $f_{1}(x)-f_{2}(x)>0$ for $x>\sqrt{m-2}$. Notice that
$f_{2}(\sqrt{m-2})=-\sqrt{m-2}-1<0$. By Lemma 2.11 (ii), we have
$\rho(F_{0}(t_{1},\frac{m-3t_{1}}{2},0))<\rho(F_{0}(1,\frac{m-3}{2},0))$ for
any $t_{1}\geq 2$. Thus, $G^{*}\cong F_{0}(1,\frac{m-3}{2},0)$.

If $\frac{m-3t_{1}}{2}=0$, then $t_{1}=\frac{m}{3}$, i.e. $G^{*}\cong
F_{0}(\frac{m}{3},0,0),$ where $3\mid m$ and $m\geq 11$. By the computation,

$\rho\left(F_{0}\left(\frac{m}{3},0,0\right)\right)=\frac{1+\sqrt{1+\frac{8}{3}m}}{2}<\sqrt{m-2}<\rho\left(F_{0}\left(1,\frac{m-3}{2},0\right)\right)$

for $m\geq 19$. For $11\leq m\leq 17$, i.e. $m=15$, we have
$\frac{1+\sqrt{41}}{2}=\rho(F_{5})>\rho(F_{0}(1,6,0))$. By the above
arguments, $G^{*}\cong F_{5}$ for $m=15$, and $G^{*}\cong
F_{0}(1,\frac{m-3}{2},0)$ for $m\geq 11$ and $m\neq 15$. ∎

Notice that $F_{0}(1,\frac{m-3}{2},0)\cong K_{2,\frac{m-3}{2}}*K_{3}$ and
$\rho(F_{0}(1,\frac{m-3}{2},0))$ is the largest root of
$x^{4}-x^{3}+(1-m)x^{2}+(m-3)x+m-3=0$. It completes the proof of Theorem 1.2
(ii). ∎

######  Remark 1.

For odd $m<11$, by Claims 4.1-4.7, we get that the minimally 2-edge connected
graph and the extremal graph $G^{*}$ is given by the following Tables.

$m$ |  Minimally 2-edge-connected graph |  $G^{*}$ |  $\rho(G^{*})$
---|---|---|---
$3$ |  $C_{3}$ |  $C_{3}$ |  2
$5$ |  $C_{5}$ |  $C_{5}$ |  2
$7$ |  $C_{7}$, $SK_{2,3}$, $C_{3}*C_{4}$ |  $C_{3}*C_{4}$ |  2.5035
$9$ |  $C_{9}$, $SK_{2,4}$, $C_{3}*C_{6}$, $C_{3}*K_{2,3}$, $C_{4}*C_{5}$, $F_{3}$ |  $F_{3}$ |  3

## References

  * [1] B. Bollobás, Extremal graph theory, dover publications, New York, 1978.
  * [2] B. Bollobás, J. Lee, S. Letzter, Eigenvalues of subgraphs of the cube, European J. Combin. 70 (2018) 125–148.
  * [3] A. Bondy, U.S.R. Murty, Graph theory, Springer, New York, 2008.
  * [4] R.A. Brualdi, A. J. Hoffman, On the spectral radius of $(0,1)$-matrices, Linear Algebra Appl. 65 (1985) 133–146.
  * [5] X. Chen, L. Guo, On minimally 2-(edge)-connected graphs with extremal spectral radius, Discrete Math. 342 (2019) 2092–2099.
  * [6] L. Collatz, U. Sinogowitz, Spektren endlicher Grafen, Abh. Math. Sem. Univ. Hamburg 21 (1957) 63–77.
  * [7] D. Cvetković, P. Rowlinson, S. Simić, An Introduction to the Theory of Graph Spectra, Cambrige University Press, New York (2010).
  * [8] G. Dirac, Minimally 2-connected graphs, J. Reine Angew. Math. 228 (1967) 204–216.
  * [9] D.D. Fan, S. Goryainov, H.Q. Lin, On the (signless Laplacian) spectral radius of minimally $k$-(edge)-connected graphs for small $k$, Discrete Appl. Math. 305 (2021), 154–163.
  * [10] A.J. Hoffman, J.H. Smith, in: Fiedler(Ed.), Recent Advances in Graph Theory, Academic Praha, (1975) 273-281.
  * [11] Q. Li, K.Q. Feng, On the largest eigenvalues of graphs, Acta Math. Appl. Sinica 2 (1979)167-175. (in Chinese).
  * [12] H.Q. Lin, B. Ning, B. Wu, Eigenvalues and triangles in graphs, Combin. Probab. Comput. 30(2) (2021) 258–270.
  * [13] W. Mader, Uber minimal $n$-fach zusammenhngende, tlnendbchc Graphen und ein Extremal problem, Archiv. Math. (Basel) 23 (1972) 553–560.
  * [14] V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 11 (2002) 179–189.
  * [15] V. Nikiforov, Walks and the spectral radius of graphs, Linear Algebra Appl. 418 (2006) 257–268.
  * [16] E. Nosal, Eigenvalues of Graphs (Master’s thesis), University of Calgary, 1970.
  * [17] M. Plummer, On minimal blocks, Trans. Amer. Math. Soc. 134 (1) (1968) 85–94.
  * [18] P.J. Slater, A classification of $4$-connected graphs, J. Combin. Theory Ser. B 17 (1974) 281–298.
  * [19] R.P. Stanley, A bound on the spectral radius of graphs with $e$ edges, Linear Algebra Appl. 87 (1987) 267–269.
  * [20] M. Tait, J. Tobin, Three conjectures in extremal spectral graph theory, J. Combin. Theory Ser. B 126 (2017) 137–161.
  * [21] W. Tutte, A theory of $3$-connected graphs, Indag. Math. 64 (1961) 441–455.
  * [22] Z.W. Wang, J-M. Guo, Some upper bounds on the spectral radius of a graph, Linear Algebra Appl. 601 (2020) 101–112.
  * [23] B. Wu, E. Xiao, Y. Hong, The spectral radius of trees on k pendant vertices, Linear Algebra Appl. 395 (2005) 343–349.
  * [24] M.Q. Zhai, H.Q. Lin, J.L. Shu, Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs, European J. Combin. 95 (2021) 103322.


# Activity-controlled Annealing of Colloidal Monolayers

Sophie Ramananarivo1 Etienne Ducrot2 Jeremie Palacci1∗
1Department of Physics, University of California San Diego, USA
2Department of Physics, New York University, USA

###### Abstract

Molecular motors are essential to the living, they generate additional
fluctuations that boost transport and assist assembly. Self-propelled
colloids, that consume energy to move, hold similar potential for the man-made
assembly of microparticles. Yet, experiments showing their use as a powerhouse
in materials science lack. Our work explores the design of man-made materials
controlled by fluctuations, arising from the internal forces generated by
active colloids. Here we show a massive acceleration of the annealing of a
monolayer of passive beads by moderate addition of self-propelled
microparticles. We rationalize our observations with a model of collisions
that drive active fluctuations to overcome kinetic barriers and activate the
annealing. The experiment is quantitatively compared with Brownian dynamic
simulations that further unveil a dynamical transition in the mechanism of
annealing. Active dopants travel uniformly in the system or co-localize at the
grain boundaries as a result of the persistence of their motion. Our findings
uncover the potential of man-made materials controlled by internal activity
and lay the groundwork for the rise of materials science beyond equilibrium.

In the classical picture of Brownian motion, particles and fluid molecules are
passive and driven by thermal fluctuations[1, 2, 3]. The incessant motion of
suspended particles is then due to multiple collisions with the surrounding
fluid molecules. In living systems, molecular motors ballistically zoom
around, push and pull on each others, and exert forces on passive elements,
yielding a riotous environment radically different from the more mundane
equilibrium one. This non-equilibrium dynamics induces additional
fluctuations[4, 5] that boost transport in biological systems[6, 7] or quickly
bring building blocks into contact while reducing unwanted connections[8].
Furthermore, the effect of internal agitation was explored in the different
context of driven vortex lattices in high-temperature superconductors[9, 10].
Active colloids, which were made available by recent synthetic progress,
similarly inject energy locally and drive systems out of equilibrium[11].
Developments on active colloids have surged in recent years, focused on exotic
behavior without equilibrium counterpart: broken microscopic reversibility[12,
13], and mesoscopic fluxes such as flocks[14], flows[15, 16], phase
separation[17, 18, 19, 20] or anomalous transport of dispersed tracers[21, 22,
23]. It largely overlooked their practical impact to deploy materials science
beyond equilibrium and control matter. Active particles added to a material
generate forces from within and provide a unique opportunity to overcome the
naturally occurring kinetic barriers and modulate the energy landscape of soft
materials. This potential was highlighted by Reichhardt & Reichhardt[24], who
numerically studied the case of a single colloid driven through a colloidal
crystal. They showed that a local melting can occur when the electrostatic
charge of the driven particle is larger or comparable to that of the colloids
comprising the crystal, leading to the generation of lattice defects that
increase the drag force and generate large noise fluctuations[24].
Opportunities in colloidal assembly were further stressed by recent numerical
works that considered mixtures of active, autonomously-driven particles, in
passive phases. They showed that the presence of active particles can favor
the annealing of a passive polycrystal by melting its grain boundaries[25, 26,
27] or act as an internal field to control the structural and dynamical
properties of a colloidal gel[28]. Notwithstanding, experimental realizations
of mixtures of active particles in a passive phase are scarce and have not
demonstrated control of the passive phase. Dietrich et al[29] showed that the
motion of self-propelled particles is altered by the presence of a loosely
packed crystal, an interesting result, however solely focused on the dynamics
of the active individuals. Alternatively, Kummel et al[27] showed that in
sparse colloidal layers, active particles tend to gather colloids into
dynamical clusters, while in denser ones, they accumulate at the grain
boundaries separating crystalline domains, where they initiate melting and
widen those disordered regions. Although further numerical modeling of their
system suggests that this localized melting could lead to a large defect-free
crystal[27], the exploitation of active dopants as a workforce for material
design still remains to be achieved experimentally. Experimental roadblocks
thwarted progress towards this goal, preventing the implementation of this
seemingly simple new pathway for material control. In this work, we devised a
microfluidic system of confining arenas with slanted walls, that allows
exchange of active particles with an external reservoir and enables a uniform
injection of energy to the passive phase. It made possible the control of the
annealing of a colloidal monolayer in time and space by harnessing the
activity of embedded active intruders, offering the first experimental
demonstration of man-made materials externally controlled by active noise.

Accelerated annealing. Our experimental system consists of a suspension of
beads of diameter $\sigma=5\mu m$ (Sigma aldrich, silicon dioxide, 44054)
filling a hexagonal well which is embossed on the bottom substrate of a
microfluidic chamber. After sedimentation, the beads form a dense monolayer of
spheres at a surface fraction $\Phi_{s}\sim 0.68\pm 0.03$ with a local hexatic
order [Methods and SI-Fig.1]. The rapid increase of the surface density of the
sedimenting particles quenches the system into adjacent crystallites separated
by grain boundaries [Fig.1A], a metastable state that eventually converts into
a single crystal. At thermal equilibrium, it takes about $12$ hours for a
system of 2200 beads to form a single crystal in a hexagonal chamber of width
$260\mu m$. We explore the impact of the addition of a small fraction of
active intruders to this initially polycrystalline monolayer of silica
spheres. The active intruders are light-activated microswimmers, consisting of
a hematite (Fe2O3) portion protruding out of a polymer sphere[20]; they are
$2\mu m$ in diameter and exhibit a two-dimensional persistent random walk in
free space[30]. In a nutshell, the iron oxide photocatalytically decomposes a
solution of hydrogen peroxide fuel after activation by a wavelength
$\lambda=390-480nm$, resulting in subsequent propulsion of the particle in the
concentration gradient[20]. The velocity is controlled by the intensity of the
light[20] that illuminates the microfluidic chamber uniformly. We periodically
interrupt the propulsion of the active particles by short periods of
extinction, light off, to allow the swimmers possibly wedged between the
passive spheres and the substrate to reorient and be released. We observe a
qualitative difference of dynamics between thermal and active annealing. In
the latter, streaks form following the displacement of the intruders in the
crystal [MovieS1]. Within 40 mins, the activated system reorganizes towards a
fully ordered state [Fig.1A] whereas its thermal counterpart -with no swimming
activity- has undergone little change [Fig.1A-insets, MovieS1].

To gain insight into the phenomenon, we vary the numeric fraction $\alpha$ of
intruders in the monolayer, $\alpha=0.1-5\%$ of the total number of passive
beads, and their propulsion velocity $V$ using the control offered by light.
We perform the experiments in larger systems with $5600$ passive beads, for
which the reorganization can be followed on larger spatial and temporal
scales. The passive beads are gravitationally confined in a hexagonal arena,
whose slant and limited depth $h\sim 4\mu m$, allow the self-propelled
particles to escape and enter[31]. This avoids the accumulation of the active
particles at the walls and maintains a constant surface fraction $\Phi_{s}$ of
passive beads and swimmers, an important prescription to the present study of
annealing.

We quantify the temporal and spatial properties of the monolayer using the
bond-orientational correlation function $g_{6}(r,t)$, calculated from the six-
fold bond-order parameter [see Methods, SI-Fig.1]. The function $g_{6}(r)$
increases with time as long-range order develops [Fig.1B-inset]: the system
coarsens and large grains develop at the expense of the smaller ones with the
walls favoring crystallites that are geometrically compatible with the
boundaries [MovieS2]. A characteristic grain size $R_{6}$ is set by the
threshold of the bond-orientational correlation function, $g_{6}(R_{6},t)=0.5$
[Fig.1B] as previously introduced in thermal systems[32, 33], and confirmed as
a relevant length scale of the grain structure by the time-independent
rescaling $g_{6}(r,t)=f(r/R_{6}(t))$ [SI-Fig.2]. The grain size $R_{6}(t)$
increases with time and shows a reasonable agreement with the normal law for a
curvature-driven grain growth, $dR_{6}/dt=\gamma/R_{6}$, where $\gamma$ is the
mobility of the grain boundary[34] [Fig.1B]. It offers a convenient proxy to
quantify the large speeding up of the observed annealing [see SI]. Devising
more intricate models, that capture in finer details the coarsening mechanisms
in such strongly out-of-equilibrium systems, constitutes exciting developments
but are beyond the scope of this work. We further use $\gamma$ as a measure of
the observed dynamics and study its dependence on the speed and the fraction
of active intruders. We report a massive increase in $\gamma$, up to 40-fold,
compared to a thermal system.

Microscopic dynamics and activated process. In order to connect the observed
phenomenon with the individual dynamics of the particles, we follow the
trajectories of the self-propelled particles in the well. They travel along
the local directions of the surrounding crystal with a speed $V=3-10\mu m/s$,
controlled by light, and a persistence time of $\tau_{r}\sim 2$s comparable
with the values measured in free space [Fig.2A, SI-Fig.4]. The trajectories
show no apparent directional persistence from one crystallite to the next, as
they tend to reorient upon crossing a grain boundary. Swimmers travel
uniformly in the chamber with limited accumulation at the walls and show no
significant localization at the grain boundaries or elsewhere [Fig.2B]. This
confirms the absence of Motility-Induced Phase Separation[35, 36] that would
notably arise from a non-uniform illumination. This result contrasts with
previous numerical reports of intruders accumulating at the grain boundaries
and initiating the melting from the surface[25, 26].

We further quantify the impact of the activity by tracking the individual
trajectories of the passive beads. The dynamics are complex and depend on
local rearrangements and instantaneous interactions with the self-propelled
particles. In virtue of the uniform distribution of the self-propelled
particles [Fig.2B], we adopt a coarse-grained approach and consider an
ensemble average of the passive particles during the first 20mins of the
experiment. The dynamics are diffusive at long times and we extract the
effective diffusion coefficient $D_{\mathrm{eff}}$ from the linear fit of the
mean square displacement [SI-Fig.3]. Experimental results for varying speeds
and fraction of swimmers [Fig.2C-top inset] gather on a master curve:
$D_{\mathrm{eff}}=D^{*}+\beta\ \alpha V$, where $D^{*}$ is the diffusivity at
equilibrium measured independently and $\beta\sim 3.10^{-2}\mu m$, the single
fitting parameter for the experimental data [Fig.2C]. We rationalize this
result by a kinetic model of intruders colliding with the monolayer, similar
in spirit to Mino et al[23] in the opposite limit of dilute tracers in an
active bath. Considering the passive beads as fixed targets, their
decorrelation $\tau$ time is set by the inverse of the collision rate with the
active particles, $\tau^{-1}\propto\phi_{a}V\ell$, where
$\phi_{a}\sim\alpha\Phi_{S}/\sigma^{2}$ is the number of intruders per unit
area, and $\ell$ is the interaction length transverse to the motion of the
swimmers. Each collision induces a displacement $d$, independent of the
velocity $V$ at low Reynolds number, so that the active contribution to the
diffusivity of the beads scales as
$d^{2}/\tau\propto\frac{d^{2}\ell\Phi_{S}}{\sigma^{2}}\alpha V$. Comparison
with the experiment gives $\frac{d^{2}\ell\Phi_{S}}{\sigma^{2}}\sim
3.10^{-2}\mu m$. This leads to ${d^{2}\ell}\sim 1\mu m^{3}$, that is
$d\sim\ell\sim\sigma/5$, in line with experimental observations and a simple
scenario dominated by hard-sphere collisions without entrainment
[Fig.2C-bottom inset].

Next, we connect the grain mobility $\gamma$ with the behavior of the passive
beads in the monolayer. The grain-growth increase correlates with the
enhancement of the diffusivity [Fig.2D] and follows an Arrhenius-like law,
$\gamma\propto\exp{-A/D_{\mathrm{eff}}}$ [Fig.2F]. Active fluctuations that
originate from the presence of the self-propelled particles allow to cross the
energy barrier $E$ required to displace grain boundaries. We extract from the
data, $A\sim E/\mu^{*}\sim 8.10^{-3}\pm 1.10^{-3}\mu m^{2}/s$, where $\mu^{*}$
is the equilibrium mobility relating equilibrium fluctuation and
dissipation[37], $D^{*}=kT/\mu^{*}$, larger than the Stokes mobility due to
additional dissipation from confinement. It gives $E\sim 4\pm 1\ kT$, a
reasonable value for the entropic barrier of a dense monolayer of hard
spheres.

Numerical simulation of a colloidal monolayer. Finally, we compare our
experiments with the results of two-dimensional Brownian dynamics
simulations[38, 39] of a polycrystalline monolayer of $2.10^{4}$ particles,
with $\Phi_{s}=0.67$, and periodic boundary conditions [Methods]. A fraction
$\alpha=0.3-1.2\%$ of active particles, with diameter $0.2\sigma$, is pulled
at a constant force and displaced into the monolayer. The persistence time of
the motion can be modified to explore regimes which are not accessible to the
experiment. For persistence times comparable with the experiment, the
simulations qualitatively capture the behavior of the system: the intruders
propel, following the local order of the crystallites. They form streaks in
the monolayer [Fig.3B] and speed up its annealing towards a long-range hexatic
order [MovieS3]. We vary the amplitude of the pulling force and extract the
velocity of the active particles, the mobility of the grain boundary and the
effective diffusivity of the passive beads as in experiments. In order to
compare experimental and numerical results, we express distances in bead
diameters $\sigma$ and time in diffusive time $t_{B}=\sigma^{2}/4D^{*}$: the
time taken by a passive bead of the monolayer to diffuse one diameter $\sigma$
in the absence of activity. The numerical relationship between the resulting
dimensionless velocity $\tilde{V}$ and effective diffusivity
$\tilde{D}_{\mathrm{eff}}$ deviates from that of experiments as a result of
differences in momentum transfer between both systems: absence of
hydrodynamics, dissipation with the substrate, or purely two-dimensional
dynamics in simulations [SI]. However, the numerical result and the experiment
agree reasonably when comparing the dimensionless grain mobilities with the
effective diffusivity of the passive beads,
$\tilde{\gamma}(\tilde{D}_{\mathrm{eff}}$), [Fig.2E], both showing an
Arrhenius-like behavior. It confirms and highlights the origin of the
phenomenon: active fluctuations resulting from the collision of the active
beads with the passive matrix activate the process of annealing [Fig.2F].
Larger swimmers close in size to the passive beads, comparatively stall in the
monolayer as their motion requires the formation of energetically costly
disclinations, as previously reported by van der Meer et al[25] in simulations
where all particles have identical sizes. Collisions with the passive matrix
are largely reduced, and the effect of the active doping on the annealing is
substantially hindered. Next, we vary the persistence time of the self-
propelled particles at fixed velocity in the simulations, which cannot be
realized experimentally. We then observe a qualitative change in the dynamics
of coarsening as a function of the associated persistence length $L_{p}$
[Fig.3]. Swimmers with large persistence navigate through the system uniformly
and form streaks [Fig.3B], while self-propelled particles with short
persistence co-localize at grain boundaries [Fig.3A, MovieS4], a reminiscence
of the effective attraction of hot particles in a cold bath[40]. The melting
from the boundaries is analogous to previous numerical results[27, 25] but
contrasts with our experimental observations. Further, we study the level of
added fluctuations induced by active intruders by measuring the effective
diffusivity of the passive spheres $D_{\mathrm{eff}}$, as a function of
$L_{p}$ at fixed propulsion. We observe a transition in $D_{\mathrm{eff}}$
that plateaus for persistence lengths shorter than the passive colloids’ size,
$L_{p}\lesssim 0.4\sigma$. The qualitative change observed in the dopants’
dynamics [Fig. 3A and 3B] coincides with a transition in energy transfer
between the dopants and the passive particles. The co-localization of active
particles at the grain boundaries limits the collisions with the passive phase
and the level of added noise: the annealing is slowed down. Although the
mobility of the grain is conveniently described by an activated process with
an effective temperature, the observed dynamical transition highlights the
intrinsic non-equilibrium nature of the annealing process.

Spatial control of the activity. We further exploit the potential of activity-
driven assembly of colloidal materials by demonstrating spatial control of the
annealing in the monolayer. Taking advantage of the flexibility offered by
photocatalytic swimmers and light patterns, we selectively activate one half
of the colloidal monolayer while keeping the other half in the dark, i.e. in
thermal state [Fig.4, MovieS5]. Activity generates fluctuations in the
monolayer and passive particles in illuminated regions diffuse many times
faster than in dark regions, where $D_{\mathrm{eff}}$ drops back to its
equilibrium value [Fig.4C]. Following, the activated region quickly
rearranges, while the thermal region barely evolves, illustrating a dynamical
control with a spatial resolution of only a few colloids [Movie S5]. It shows
the first experimental demonstration of a man-made material controlled by
internal activity, regulated in time and space.

Conclusion and Perspective. Heat treatments, e.g. annealing, quenching or
tempering, were originally developed for metals, to alter macroscopic
properties such as strength, ductility, or toughness. Annealing is achieved
through cycles of high temperatures and slow cooling: high temperatures steps
allow the system to escape kinetic traps, while the slow cooling relaxes the
system to its ground state with reduced defects. We showed that active
particles embedded in an otherwise passive system offer an untapped approach
to annealing. The addition of in situ large fluctuations, mimics macroscopic
annealing by heating and locally reorganizing the system. It allows local
equilibration and avoids metastable states, a crucial problem in the
experimental assembly of complex architectures. We further unveil a transition
in the dynamics of annealing, set by the persistence of the active dopants,
which has no equilibrium counterpart and had not been predicted in previous
numerical works. By using light patterns, we demonstrate a spatial control of
the annealing with a spatial resolution of a few microns. The spatiotemporal
control of internal fluctuations paves the way to the tuning of material
properties, as well as the engineering of bio-inspired sensors harnessing
active noise for enhanced accuracy[41, 42]. The variety of available synthetic
and biological microswimmers, including particles which could remotely be
steered by magnetic fields or light patterns[43, 44], offers opportunities for
a wide range of control. As grain boundaries are essential to material
properties, from yield strength[45, 46] to electrical conductivity[47], our
findings usher materials science to a new age, where the properties of matter
are not controlled macroscopically but microscopically and in real time by
active dopants. Further, the use of traveling particles that navigate a matrix
as in this work, may suggest innovative numerical protocols of simulated
annealing using virtual active intruders rather than global temperature
cycling to explore complex energy landscapes.

## Material and Methods

Experimental set-up. Our colloidal model system consists of silica beads of
diameter $\sigma=5\mu m$ (Sigma aldrich, 44054) suspended in a $6\%$ solution
of hydrogen peroxide $H_{2}O_{2}$ in deionized water (Millipore,
$18.2M\Omega$). Within a few minutes, the heavy particles sediment on the
bottom wall of the sample cell to form a dense monolayer of area fraction
$\Phi_{S}=\pi N\sigma^{2}/4A\approx 0.68\pm 0.03$, where $N$ is the number of
particle contained in the hexagonal area $A$. The equilibrium gravitational
height is much smaller than $\sigma$, so that out-of-plane thermal
fluctuations are negligible in the absence of swimmers and the system is quasi
two-dimensional. When active intruders are introduced in the layer however,
passive particle are observed to slightly lift from the bottom surface as
smaller swimmers pass by. The numeric fraction of intruders $\alpha=N_{s}/N$,
with $N_{s}$ the number of swimmers, is varied. They are light activated
$2\mu$m-diameter particles, consisting of a hematite cube embedded in a
polymer bead [20, 48]. Under UV-light, the photo-catalytic hematite triggers
the local decomposition of the hydrogen peroxide contained in the solution,
creating a gradient that sets the swimmer into motion through phoretic
effects. They then exhibit a persistent random walk along the bottom surface.
The sample cell containing the solution is assembled from a glass microscope
slide on top and a 0.38mm-thick polymethylmethacrylate PMMA sheet (Goodfellow
ME303001) on the bottom, separated by rectangular capillaries (Vitrocom 3524)
used as spacers of approximate height $600\mu$m. Shallow $4\mu$m-deep
hexagonal wells are heat embossed in the PMMA bottom surface using a
polydimethylsiloxane PDMS mold fabricated via soft lithography. This
confinement arena allows to keep the surface fraction $\Phi_{S}$ constant for
the duration of an experiment. A narrow trench additionally surrounds the
hexagon, to trap exterior colloids and prevent them from falling into the
well. Quantitative measurements are conducted in $400\mu$m-wide hexagons,
containing about 5600 passive particles. Prior to assembly, all components are
washed with Hellmanex III and thoroughly rinsed with deionized water (Milli-Q,
resistivity 18.2 M). After injecting the colloidal solution, the cell is
sealed with capillary wax (Hampton Research HR4-328).
The system is observed using an inverted optical microscope (Nikon Eclipse-Ti)
equipped with a 20$\times$ objective. A LED with a wavelength
$\lambda=390-480nm$ (Lumencor, Spectra X) uniformly illuminates the hexagonal
chamber through the bottom wall and activates the swimmers. The intensity of
the LED can be adjusted to modify the speed of the intruders. The UV
illumination is periodically interrupted for short intervals of 20s every 80s
to allow for swimmers that are wedged between passive particles and the
substrate to reorient through Brownian motion and escape. The evolution of the
monolayer is monitored with a camera (Hamamatsu, C11440-22CU) recording images
at a frame rate of 2.5fps for 90 min, and 0.1fps for 12 hours for a thermal
system (with no swimmers). The position of the passive particles is extracted
in each frame using standard image analysis routines[49].
Characterization of the grain structure. The organization of the
polycrystalline layer at a time $t$ is visualized and quantified through the
local orientational bond order parameter $\psi_{6}$. For each passive
particle,
$\psi_{6}(\vec{r}_{j},t)=\frac{1}{N_{j}}\sum_{j=1}^{N_{j}}e^{6i\theta(\vec{r}_{jk})}$
is computed based on the arrangement of its $N_{j}$ nearest neighbors (defined
using Delaunay triangulation), where $\theta(\vec{r}_{jk})$ is the angle
between a particle $j$ and its neighbor $k$ with respect to a reference axis
chosen here as one of the direction of the hexagonal well [see SI-Fig.1b]. The
amplitude of $\psi_{6}$, which takes values within [0.9-1] at the exception of
the grain boundaries, reflects local hexagonal order [see SI-Fig.1c]. Its
phase provides the local crystalline orientation
$\theta_{6}(\vec{r}_{j},t)=\frac{1}{6}\text{arg}(\psi_{6}(\vec{r}_{j},t))$
that varies from 0 to $60^{o}$ due to rotational symmetry. In Fig.1, Fig.3 and
Fig.4, particles are color-coded with the crystalline orientation to visualize
the grain structure. We monitor the evolution of spatial structures using the
bond-orientational correlation function $g_{6}(r,t)$, calculated from the six-
fold bond-order parameter. As previously introduced with thermal systems[32],
the field $\psi_{6}$ is first smoothed by averaging local values
$\psi_{6}(\vec{r}_{j},t)$ over the two first shells of neighbors surrounding
particle $j$. The resulting field is then normalized, both operations allowing
for a more accurate probing of the correlations at short distances [50, 33].
The bond-orientational correlation function is then computed as
$g_{6}(r,t)=\operatorname{Re}\left(\left<\hat{\psi}_{6}^{*}(\vec{r}+\vec{r}_{0},t)\hat{\psi}_{6}(\vec{r}_{0},t)\right>\right),$
with $\hat{\psi}_{6}$ the smoothed and normalized parameter and
$\left<.\right>$ referring to the average over all pairs of particles
separated by a distance r. This definition of $g_{6}(r,t)$ evaluates the
spatial correlation in the argument of the bond-orientation parameter,
singling out the angle component of the long-range order developing in the
system over time.

Numerical simulations. We performed Brownian dynamics simulations using HOOMD-
blue [38, 39] to model the experiment. A two-dimensional rectangular box with
periodic boundary conditions is filled with 20 000 spheres of diameter
$\sigma=1$ at an area fraction $\Phi_{S}=0.05$. A fraction $\alpha$ of those
particles is randomly selected to form the active particles subset. Their
diameter is set to $\sigma_{S}=0.2$. All the particles interact through a
purely repulsive WCA potential given by :

$\displaystyle U(r)=$ $\displaystyle
4\epsilon\left[\left(\frac{\xi}{r}\right)^{2n}-\left(\frac{\xi}{r}\right)^{n}+1/4\right]\
\text{for}\ r\leq 2^{1/n}\xi,$ $\displaystyle U(r)=$ $\displaystyle 0\
\text{for}\ r>2^{1/n}\xi,$

where $n=6$, $\epsilon=10$ and $\xi=R_{i}+R_{j}$, with $R_{i,j}$ the radius of
the interacting particles. $R_{i,j}=\sigma/2$ for passive particles and
$R_{i,j}=\sigma_{S}/2$ for active particles.

The initial configurations are prepared by compressing the diluted box until
an area fraction $\Phi_{S}=0.67$ in $4.10^{5}$ steps of length $\Delta
t=0.0001$ using the Langevin dynamics integrator. At all times, the box
dimensions are set to accommodate a hexagonal lattice (i.e.
$L_{x}=L_{y}\times\sqrt{3}$). During this preparation step, the temperature is
linearly decreased from $kT=2$ to $0.0005$. Once quenched, the particles form
a polycrystalline 2D layer.

Thermal annealing runs are performed by letting the system relax for 500
million steps without adding activity to the small particles. For boosted
annealing runs, an active force is applied to the small particles. It is
parametrized by its amplitude $F_{a}$ and a rotational diffusion constant
$D_{r}$ that controls the random change of direction of the active force.
Typical values for $F_{a}$ are between 0 and 4 and shown here in the range
[0-1.5], and $D_{r}$ is taken between 0.1 and 5. Simulations of activated
monolayers are run for 100 million steps. The equations of motion for the
simulations are given by :

$\displaystyle m\dfrac{d\vec{v}}{dt}=$
$\displaystyle\vec{F}_{\mathrm{C}}-\zeta\cdot\vec{v}+\vec{F}_{\mathrm{R}}$
$\displaystyle\langle\vec{F}_{\mathrm{R}}\rangle=$ $\displaystyle 0$
$\displaystyle\langle|\vec{F}_{\mathrm{R}}|^{2}\rangle=$ $\displaystyle
2dkT\zeta/\delta t$

where $\vec{F}_{\mathrm{C}}$ is the force applied on the particles originated
from all potentials and constraint forces, $\zeta$ is the drag coefficient
($\zeta=1$ here), $\vec{v}$ is the particle’s velocity, $\vec{F}_{\mathrm{R}}$
is a uniform random force and $d$ is the dimensionality of the system ($d=2$
here).

For active particles, an active force is added to the equation of motion such
that $\delta\vec{r}_{i}=\delta tF_{a}\vec{p}_{i}$, where $F_{a}$ is the active
velocity and $\vec{p}_{i}=(\cos\theta_{i},\sin\theta_{i})$ is the active force
vector for the particle i. The rotational diffusion of this active force
vector follows $\delta\theta/\delta t=\sqrt{2D_{r}/\delta t}\Gamma$, where
$D_{r}$ is the rotational diffusion constant and the gamma function $\Gamma$
is a unit-variance random variable that decorrelates space, time and
particles.

The particles positions are recorded every 10000 steps. Following the same
treatment as the experiments, the dynamic of the passive colloids and the
swimmers is analyzed. For each set of parameters, six independent runs are
performed to improve statistics.

## REFERENCES

## References

  * [1] Perrin, J.  Mouvement brownien et réalité moléculaire.  _Annales de Chimie et de Physique_ (1909).
  * [2] Brown, R.  On the particles contained in the pollen of plants; and on the general existence of active molecules in organic and inorganic bodies.  _Edinburgh new Philosophical Journal_ (1828).
  * [3] Einstein, A.  The motion of elements suspended in static liquids as claimed in the molecular kinetic theory of heat.  _Annalen der physik_ 17, 549–560 (1905).
  * [4] Brugués, J. & Needleman, D.  Physical basis of spindle self-organization.  _Proceedings of the National Academy of Sciences of the U.S.A_ 111, 18496–18500 (2014).
  * [5] Wittmann, T., Hyman, A. & Desai, A.  The spindle: a dynamic assembly of microtubules and motors.  _Nature Cell Biology_ 3, E28–E34 (2001).
  * [6] Brangwynne, C. P., Koenderink, G. H., MacKintosh, F. C. & Weitz, D. A.  Cytoplasmic diffusion: molecular motors mix it up.  _The Journal of Cell Biology_ 183, 583–587 (2008).
  * [7] Guo, M. _et al._ Probing the Stochastic, Motor-Driven Properties of the Cytoplasm Using Force Spectrum Microscopy.  _Cell_ 158, 822–832 (2014).
  * [8] Hess, H.  Self-assembly driven by molecular motors.  _Soft Matter_ 2, 669–677 (2006).
  * [9] Koshelev, A. & Vinokur, V.  Dynamic Melting of the Vortex Lattice.  _Physical Review Letters_ 73, 3580–3583 (1994).
  * [10] Paltiel, Y. _et al._ Dynamic instabilities and memory effects in vortex matter.  _Nature_ 403, 398–401 (2000).
  * [11] Sengupta, S., Ibele, M. E. & Sen, A.  Fantastic Voyage: Designing Self-Powered Nanorobots.  _Angewandte Chemie-International Edition In English_ 51, 8434–8445 (2012).
  * [12] Di Leonardo, R. _et al._ Bacterial ratchet motors.  _Proceedings of the National Academy of Sciences_ 107, 9541–9545 (2010).
  * [13] Sokolov, A., Apodaca, M. M., Grzybowski, B. A. & Aranson, I. S.  Swimming bacteria power microscopic gears.  _Proceedings of the National Academy of Sciences_ 107, 969–974 (2010).
  * [14] Bricard, A., Caussin, J.-B., Desreumaux, N., Dauchot, O. & Bartolo, D.  Emergence of macroscopic directed motion in populations of motile colloids.  _Nature_ 503, 95 (2013).
  * [15] Wu, K.-T. _et al._ Transition from turbulent to coherent flows in confined three-dimensional active fluids.  _Science_ 355, eaal1979–18 (2017).
  * [16] Lushi, E., Wioland, H. & Goldstein, R. E.  Fluid flows created by swimming bacteria drive self-organization in confined suspensions.  _Proceedings of the National Academy of Sciences of the U.S.A_ 111, 9733–9738 (2014).
  * [17] Cates, M. E. & Tailleur, J.  Motility-Induced Phase Separation.  _Annual Review of Condensed Matter Physics_ 6, 219–244 (2015).
  * [18] Theurkauff, I., Cottin-Bizonne, C., Palacci, J., Ybert, C. & Bocquet, L.  Dynamic clustering in active colloidal suspensions with chemical signaling.  _Physical Review Letters_ 108, 268303 (2012).
  * [19] Buttinoni, I. _et al._ Dynamical clustering and phase separation in suspensions of self-propelled colloidal particles.  _Physical Review Letters_ 110, 238301 (2013).
  * [20] Palacci, J., Sacanna, S., Steinberg, A. P., Pine, D. J. & Chaikin, P. M.  Living crystals of light-activated colloidal surfers.  _Science_ 1230020 (2013).
  * [21] Wu, X.-L. & Libchaber, A.  Particle diffusion in a quasi-two-dimensional bacterial bath.  _Physical Review Letters_ 84, 3017 (2000).
  * [22] Leptos, K. C., Guasto, J. S., Gollub, J. P., Pesci, A. I. & Goldstein, R. E.  Dynamics of enhanced tracer diffusion in suspensions of swimming eukaryotic microorganisms.  _Physical Review Letters_ 103, 198103 (2009).
  * [23] Mino, G. _et al._ Enhanced diffusion due to active swimmers at a solid surface.  _Physical Review Letters_ 106, 048102 (2011).
  * [24] Reichhardt, C. & Reichhardt, C. J. O.  Local Melting and Drag for a Particle Driven through a Colloidal Crystal.  _Physical Review Letters_ 92, 095504–4 (2004).
  * [25] van der Meer, B., Filion, L. & Dijkstra, M.  Fabricating large two-dimensional single colloidal crystals by doping with active particles.  _Soft Matter_ 12, 3406–3411 (2016).
  * [26] van der Meer, B., Dijkstra, M. & Filion, L.  Removing grain boundaries from three-dimensional colloidal crystals using active dopants.  _Soft Matter_ 12, 5630–5635 (2016).
  * [27] Kümmel, F., Shabestari, P., Lozano, C., Volpe, G. & Bechinger, C.  Formation, compression and surface melting of colloidal clusters by active particles.  _Soft Matter_ 11, 6187–6191 (2015).
  * [28] K Omar, A., Wu, Y., Wang, Z.-G. & F Brady, J.  Swimming to Stability: Structural and Dynamical Control via Active Doping.  _Acs Nano_ 13, 1–13 (2018).
  * [29] Dietrich, K. _et al._ Active Atoms and Interstitials in Two-Dimensional Colloidal Crystals.  _Physical Review Letters_ 120, 268004 (2018).
  * [30] Howse, J. R. _et al._ Self-motile colloidal particles: from directed propulsion to random walk.  _Physical Review Letters_ 99, 048102 (2007).
  * [31] Koumakis, N., Lepore, A., Maggi, C. & Di Leonardo, R.  Targeted delivery of colloids by swimming bacteria.  _Nature Communications_ 4, 2588 (2013).
  * [32] Lavergne, F. A., Aarts, D. G. A. L. & Dullens, R. P. A.  Anomalous grain growth in a polycrystalline monolayer of colloidal hard spheres.  _Physical Review X_ 7, 041064 (2017).
  * [33] Sicilia, J. J., A.and Arenzon _et al._ Experimental test of curvature-driven dynamics in the phase ordering of a two dimensional liquid crystal.  _Physical Review Letters_ 101, 197801 (2008).
  * [34] Rollett, A., Humphreys, F. J., Rohrer, G. S. & Hatherly, M.  _Recrystallization and related annealing phenomena_ (Elsevier, 2004).
  * [35] McCandlish, S. R., Baskaran, A. & Hagan, M. F.  Spontaneous segregation of self-propelled particles with different motilities.  _Soft Matter_ 8, 2527–2534 (2012).
  * [36] Cates, M. E., Marenduzzo, D., Pagonabarraga, I. & Tailleur, J.  Arrested phase separation in reproducing bacteria creates a generic route to pattern formation.  _Proceedings of the National Academy of Sciences of the U.S.A_ 107, 11715–11720 (2010).
  * [37] Barrat, J.-L. & Hansen, J.-P.  _Basic concepts for simple and complex liquids_ (Cambridge University Press, 2003).
  * [38] Anderson, J. A., Lorenz, C. D. & Travesset, A.  General purpose molecular dynamics simulations fully implemented on graphics processing units.  _Journal of Computational Physics_ 227, 5342–5359 (2008).
  * [39] Glaser, J. _et al._ Strong scaling of general-purpose molecular dynamics simulations on gpus.  _Computer Physics Communications_ 192, 97–107 (2015).
  * [40] Tanaka, H. & Brenner, M.  Hot particles attract in a cold bath.  _Physical Review Fluids_ 2, 043103 (2017).
  * [41] Lan, G., Sartori, P., Neumann, S., Sourjik, V. & Tu, Y.  The energy–speed–accuracy trade-off in sensory adaptation.  _Nature Physics_ 8, 422–428 (2012).
  * [42] Berut, A. _et al._ Gravisensors in plant cells behave like an active granular liquid.  _Proceedings Of The National Academy Of Sciences Of The United States Of America_ 115, 5123–5128 (2018).
  * [43] Frangipane, G. _et al._ Dynamic density shaping of photokinetic E. coli.  _eLife_ 7 (2018).
  * [44] Arlt, J., Martinez, V. A., Dawson, A., Pilizota, T. & Poon, W. C. K.  Painting with light-powered bacteria.  _Nature Communications_ 9, 1–7 (2018).
  * [45] Meyers, M. A., Mishra, A. & Benson, D. J.  Mechanical properties of nanocrystalline materials.  _Progress in Materials Science_ 51, 427–556 (2006).
  * [46] Huang, P. Y. _et al._ Grains and grain boundaries in single-layer graphene atomic patchwork quilts.  _Nature_ 469, 389–392 (2011).
  * [47] Kreuer, K. D.  Proton-Conducting Oxides.  _Annual Review of Materials Research_ 33, 333–359 (2003).
  * [48] Palacci, J. _et al._ Light-activated self-propelled colloids.  _Phil. Trans. R. Soc. A_ 372, 20130372 (2014).
  * [49] Blair, D. & Dufresne, E.  _Matlab particle tracking code retrieved from http://physics.georgetown.edu/matlab/_.
  * [50] Blundell, R. E. & Bray, A. J.  Phase-ordering dynamics of the o (n) model: Exact predictions and numerical results.  _Physical Review E_ 49, 4925 (1994).

is available in the online version of the paper

We thank S. Sacanna and M. Youssef for the synthesis of the active particles.
We thank L. Bocquet, P. Chaikin and S. Sacanna for discussions. This material
is based upon work supported by the National Science Foundation under Grant
No. DMR-1554724. J.P. thanks the Sloan Foundation for support through grant
FG-2017-9392. E.D. acknowledges support of the US National Science Foundation
under Award Number DMR-1610788, as well as the NYU IT High Performance
Computing resources, services, and staff expertise.

S.R. and J.P. designed the study; S.R. performed the experiments and analyzed
the results; E.D. performed the numerical simulations; all authors contributed
to interpreting the results and writing the paper.

The authors declare that they have no competing financial interests.

Correspondence and requests for materials should be addressed to J.P. (email:
palacci@ucsd.edu).

The data that support the plots within this paper and other findings of this
study are available from the corresponding author upon request.

Figure 1: Accelerated annealing. (A) Optical microscopy of a hexatic monolayer
of passive beads (circles) containing a small fraction of active intruders
(not visible at this magnification). The passive beads are color-coded by the
local orientational field of the hexatic order. The system is initially
quenched in adjacent polycristallites (left panel) and rapidly relaxes towards
an ordered monolayer (right panel), following the activation of the self-
propelled particles in the layer. The thermal experiment, in the absence of
active particles, is significantly slower and shows little evolution within
the same time span [insets]. Scale bars, $50\mu m$. (B-inset) Bond
orientational correlation function $g_{6}(r,t)$ as a function of distance $r$
and for increasing times $t$ (blue to yellow color gradient) [see main text].
It increases with time as long-range order develops: large grains grow at the
expense of smaller ones. (B): Time-evolution of the characteristic grain
radius $R_{6}$, in units of colloid diameters $\sigma$, defined from
$g_{6}(R_{6},t)=0.5$ for thermal (black) monolayer or in the presence of
embedded self-propelled particles (color, $V=10\mu m/s$, $\alpha=1.3\%$) and
fit by a normal grain growth $R_{6}(t)^{2}=R_{6}(0)^{2}+\gamma t$ (dotted
lines, see Main text). The grey area delimits grain sizes $>20\sigma$ which
cannot be measured accurately in the experiment.  Figure 2: Microscopic
dynamics. (A) Individual trajectories of self-propelled particles in an
ordered monolayer. Some trajectories are highlighted in black for better
visibility. The probability distribution of propulsion direction $\theta_{V}$
of the active particles shows peaks along the natural directions of the
crystal. (B) Probability distribution of the presence of swimmers in the
colloidal layer over the first 20min of an experiment. It is uniform (value
for a uniform distribution indicated by an arrow), the swimmers do not
localize on the walls, the grain boundaries or elsewhere. Scale bars, $50\mu
m$. (C) [top inset] Measured diffusivity $D_{\text{eff}}$ of the passive
colloids of the monolayer as a function of the speed $V$ of the active
particles. Colors distinguish speeds $V=3$ (yellow), $5$ (orange), $10\mu m/s$
(dark red); and symbols refer to different fraction of swimmers $\alpha=0.4$
(upward triangle), $1.3$ (square), $3.1$ (circle), $4.1$ (downward triangle),
and $5.0\%$ (star). The data collapse onto a master curve
$D_{\text{eff}}=D^{*}+\beta\alpha V$ when plotted as a function of $\alpha V$,
with $D^{*}$ the diffusivity for a purely passive system (black diamond)
simply described by a model of collisions of the passive beads with the active
particles (see Main text). (C)[bottom inset] Displacement of colloids induced
by a swimmer (red dot, the arrow indicates the direction of motion); the
color-coding of particles denotes the amplitude of displacement (traced by red
lines) following a collision. (D) Grain mobility $\gamma$ as a function of
$D_{\text{eff}}$ in experiments; the presence of intruders speed up the
reorganization of the monolayer by nearly two orders of magnitude. (E)
$\gamma(D_{\text{eff}})$ obtained in simulations by varying the velocity of
self-propelled particles at a fixed persistence time comparable with the
experiments [see Methods]. Data are nondimensionalized using $\sigma$ and the
Brownian time $t_{B}$ as a characteristic length and time (see Main text);
symbols differentiate between fractions of swimmers $\alpha=0.3$ (upward
triangle), $0.6$ (right-pointing triangle), and $1.2\%$ (square). (F) Log-lin
plot of $\gamma$ as a function of $1/D_{\text{eff}}$ shows an Arrhenius-like
behavior in the experiment (color symbols) and the simulations (hollow
symbols).  Figure 3: Numerical simulation of a colloidal monolayer, with added
active particles of different persistence. Evolution of the system starting
from the same initial configuration (inset, t=0) with a fraction
$\alpha=0.6\%$ of active intruders, with same speed but different persistence
time, leading to persistence lengths of (A) $L_{p}=0.3\sigma$, and (B)
$L_{p}=7\sigma$ comparable to experiments. The dynamics of the swimmers change
qualitatively with the persistent time: they navigate along the directions of
the crystal in one case (B) and localize at the grain boundaries in the other
(A). The colors correspond to the local hexactic orientational order as in
[Fig.1] The active particles are shown as black points bigger than their
actual size to improve visibility, and black lines trace their trajectories
within the $3.10^{6}$ time steps preceding the snapshots. (C) The diffusivity
$D_{\text{eff}}$ of the passive particles shows a dynamic transition set by
the persistence length $L_{p}$ of the active dopants and plateaus for
$L_{p}\leq 0.4\sigma$. Active dopants co-localize at the grain boundary for
$L_{p}\leq 0.4\sigma$ and travel in bulk otherwise, as illustrated with
typical trajectories on the side panels, which correspond to the highlighted
points on the graph. The qualitative change in the annealing mechanism, as
visible on panels (A) and (B), coincides with a transition in energy transfer
between the dopants and the passive particles. Figure 4: Spatial control of
the active particles’ activity and effect on the monolayer. (A) Selective
reorganization of the polycrystalline layer by activating only the intruders
in the left half of the well. Scale bars, $50\mu m$. (B) Diffusivity of the
passive particles $D_{\text{eff}}$ compared to that in a thermal system
$D^{*}$, and plotted as a function of the distance to the illumination
interface expressed in units of diameter. It illustrates dynamical control
with a spatial resolution of only a few colloids. Vertical errorbars denote
the standard deviation over particles located within each spatial window,
whose boundaries are shown through horizontal errorbars.