# Computer simulations of the Gardner transition in structural glasses

Yuliang Jin  CAS Key Laboratory of Theoretical Physics, Institute of
Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China
School of Physical Sciences, University of Chinese Academy of Sciences,
Beijing 100049, China  Wenzhou Institute, University of Chinese Academy of
Sciences, Wenzhou, Zhejiang 325000, China  Hajime Yoshino  Cybermedia Center,
Osaka University, Toyonaka, Osaka 560-0043, Japan  Graduate School of Science,
Osaka University, Toyonaka, Osaka 560-0043, Japan

###### Contents

  1. I Connections between Gardner and spin-glass transitions
  2. II Gardner transition under compression
    1. II.1 Preparation of ultra-stable glasses
    2. II.2 Key observables and protocols
    3. II.3 Aging effects
    4. II.4 Anomalous order parameters and responses
  3. III Gardner transition under shear
  4. IV Discussion and outlook

##  I Connections between Gardner and spin-glass transitions

The exact mean-field theory for the simplest glass-forming system - the dense
assembly of hard spheres in the large dimensional limit \- predicts the
existence of a Gardner phase Parisi  _et al._ (2020); Berthier  _et al._
(2019). This transition is characterized by full replica symmetry breaking
(RSB) that implies two fascinating physical consequences. (i) A hierarchical
free-energy landscape, i.e., the thermal fluctuations are organized
hierarchically, meaning that configurations are grouped into meta-basins that
are further grouped into meta-meta basins, … (ii) The marginal stability,
i.e., the system responds sensitively to infinitesimal perturbations. Here we
discuss recent results of numerical simulations to examine these mean-field
predictions in physical dimensions.

From the viewpoint of RSB, the Gardner transition in structural glasses
belongs to the same full RSB universality class of the spin-glass transition
(see Fig. 1(A)). This theoretical ground motivates us to borrow ideas from the
extensive research on spin-glasses to study the Gardner transition. To this
end, it is useful to review firstly some of the essential results obtained in
spin-glass experiments and simulations.

The RSB solution immediately implies a hierarchy of linear responses through
the fluctuation-dissipation relation Mézard  _et al._ (1987). One expects
short-time, intermediate-time, and long-time linear responses associated with
thermal fluctuations inside basins, meta-basins, and meta-meta-basins. A
remarkable consequence is the “anomaly” that gives a natural explanation for
the protocol-dependent linear responses observed experimentally Nagata  _et
al._ (1979). In one protocol called field cooling (FC), one measures the
magnetization $m_{\rm FC}$ of a spin-glass under cooling from a high
temperature $T_{\rm max}$ down to a low temperature $T_{\rm min}$ below the
spin-glass transition temperature $T_{\rm SG}$ in the presence of a weak
external magnetic field $\delta h$; in the other protocol called zero field
cooling (ZFC), one cools the spin-glass from $T_{\rm max}$ down to $T_{\rm
min}$ without the field ($h=0$), then switches on the magnetic field $\delta
h$ and measures the magnetization $m_{\rm ZFC}$ under heating the spin-glass
back to $T_{\rm max}$ (see Fig. 1(B)). The two susceptibilities $\chi_{\rm
FC}=m_{\rm FC}/\delta h$ and $\chi_{\rm ZFC}=m_{\rm ZFC}/\delta h$ are the
same above $T_{\rm SG}$, but different ($\chi_{\rm FC}>\chi_{\rm ZFC}$) below
(see Fig. 2(A)). The fact that $\chi_{\rm FC}$ and $\chi_{\rm ZFC}$ are
different in the spin-glass phase is referred to as an “anomaly”, because the
susceptibility is protocol-independent in standard magnetic systems. The RSB
theory gives $\chi_{\rm FC}-\chi_{\rm
ZFC}=\beta\left[\int_{0}^{1}dqP(q)q-q_{\rm EA}\right]$, with $\beta$ the
inverse temperature. Here $q_{\rm EA}$ is the Edwards-Anderson (EA) order
parameter Edwards and Anderson (1975) representing the strength of the thermal
fluctuation within lowest-level basins, while $\int_{0}^{1}dqP(q)q$ represents
the integral of thermal fluctuations coming from all levels in the hierarchy.
In the replica symmetric (RS) solution, $P(q)=\delta(q-q_{\rm EA})$, so that
the anomaly vanishes.

Figure 1:  (A) Correspondence between spin and structural glasses. Note that
one step RSB (1-RSB) exists in certain spin-glass models such as the spherical
p-spin ($p>2$) model Castellani and Cavagna (2005). (B) Schematic of ZFC/FC
protocols. In spin and hard-sphere glasses, the control parameter is the
temperature $T$ and the density (volume fraction) $\varphi$ respectively, and
the external field is the magnetic field $h$ and the shear-strain $\gamma$
respectively.

The anomaly is known to be not a transient but a long-time effect, as
demonstrated by a series of experiments that reveal aging effects in spin-
glasses Granberg  _et al._ (1988); Vincent  _et al._ (1997); Nordblad and
Svedlindh (1998). To study the dynamical effects, one can generalize the ZFC
protocol by introducing a waiting time $t_{\rm w}$ before switching on the
magnetic field, and a measurement time $\tau$ elapsed in the presence of the
field. By increasing $\tau$, $m_{\rm ZFC}(\tau,t_{\rm w})$ increases passing
through $m_{\rm ZFC}$ and heads toward $m_{\rm FC}$ (see Fig. 2(B)). However,
$m_{\rm ZFC}(\tau,t_{\rm w})$ does not reach $m_{\rm FC}$ within finite time,
and its time evolution as a function of $\tau$ slows down with increasing
waiting time $t_{\rm w}$, manifested by scaling laws depending on $\tau/t_{\rm
w}$. These experimental observations are significant because they reveal the
out-of-equilibrium nature of spin-glasses. To describe the aging effects and
the anomaly from a purely dynamical point of view, a dynamical mean-field
theory on spin-glass models is developed Cugliandolo and Kurchan (1993, 1994).
The dynamical theory relates RSB to the notion of effective temperature that
characterizes out-of equilibrium glassy dynamics Cugliandolo  _et al._ (1997);
Franz  _et al._ (1998). The numerical evidence of effective temperature
Marinari  _et al._ (2000) and non-zero anomaly in the long-time limit Yoshino
_et al._ (2002) has been indicated by detailed simulations of finite-
dimensional spin-glass models.

The marginal stability of the spin-glass phase may account for various complex
non-linear responses, such as the effect of static chaos with respect to an
infinitesimal change of temperature, or avalanches with respect to an
infinitesimal change of magnetic field. Indeed the equilibrium spin
configurations at large length scales are completely reshuffled by
infinitesimal perturbations, which is predicted first by the droplet theory
Bray and Moore (1987); Fisher and Huse (1988a, b), and later by theories based
on RSB Kondor (1989); Rizzo and Crisanti (2003); Rizzo and Yoshino (2006);
Yoshino and Rizzo (2008); Parisi and Rizzo (2010); Le Doussal  _et al._ (2010,
2012); Franz and Spigler (2017). The rejuvenation-memory effects observed
experimentally Jonason  _et al._ (1998) may be related to such non-linear
responses Yoshino  _et al._ (2001); Jönsson  _et al._ (2004).

Once one is aware of the correspondence between spin and structural glasses
(see Fig. 1(A)), it is natural to use strategies inherited from spin-glass
studies to explore the physics of Gardner phase in structural glasses. For
example, in the ZFC/FC protocols, the role of the magnetic field $h$ for spin-
glasses can be replaced by the shear strain $\gamma$ for structural glasses
(see Fig. 1(B)), which only changes the boundary condition but not the
thermodynamic properties of the bulk. Indeed, the replica theory of structural
glasses predicts a hierarchy of shear moduli reflecting RSB Yoshino and Mézard
(2010); Yoshino (2012); Yoshino and Zamponi (2014). By adapting the methods
developed in spin-glasses, one can examine the aging effects, the protocol-
dependent linear responses, and the non-linear responses such as avalanches,
in structural glasses with respect to shear deformations. Our discussion
focuses on one of the simplest models of structural glasses in three
dimensions, hard spheres, where the (reduced) pressure $p$ (or the volume
fraction $\varphi$) plays the role of temperature $T$. According to the
replica theory Parisi  _et al._ (2020) that is exact in the large dimensional
limit, a Gardner transition occurs in hard spheres under both compression and
shear, which is examined by simulations at three-dimensions in the following
sections. The dynamical mean-field theory for the hard-sphere glass has also
been set up Maimbourg  _et al._ (2016); Kurchan  _et al._ (2016); Agoritsas
_et al._ (2019a, b), but a detailed theoretical analysis of the out-of
equilibrium dynamics remains challenging. Nonetheless, the analogy to the
spin-glass problem outlined above allows us to infer the implications of RSB
on the dynamics of hard spheres.

Figure 2: Experimental results on CuMn spin-glasses. (A) ZFC/FC
susceptibilities (adapted from Nagata  _et al._ (1979)), and (B) the time
evolution of $m_{\rm ZFC}(\tau,t_{\rm w})/\delta h$ in an aging experiment
(adapted from Granberg  _et al._ (1988)).

##  II Gardner transition under compression

###  II.1 Preparation of ultra-stable glasses

To study the Gardner transition, we must prepare a glass at first.
Experimentally, glasses are obtained by a slow thermal or compression
annealing, the rate of which determines the location of the glass transition.
It is found that a detailed numerical analysis of the Gardner transition
requires the preparation of extremely well-relaxed glasses (corresponding to
structural relaxation timescales challenging to simulate in standard
algorithms), in order to study vibrational motions of particles without
interference from diffusion. Such ultra-stable glasses can be numerically
generated by applying a swap Monte-Carlo scheme Kranendonk and Frenkel (1991);
Grigera and Parisi (2001) to a simple glass-forming model – a polydisperse
mixture of  $N$ hard spheres Berthier  _et al._ (2016).

The annealing procedure contains two steps Berthier  _et al._ (2016). First,
one produces equilibrated liquid configurations at various densities
$\varphi_{\rm g}$ with the help of the swap algorithm. Second, starting from
these liquid configurations, one switches to standard molecular dynamics
simulations Lubachevsky and Stillinger (1990) during which the system is
compressed out of equilibrium up to target densities $\varphi>\varphi_{\rm
g}$. In order to obtain thermal and disorder averaging, this procedure is
repeated over many samples, each corresponding to different initial
equilibrium configurations at $\varphi_{\rm g}$, and over many independent
quench realizations for each sample. The independent realizations of the same
sample have identical particle positions at $\varphi_{\rm g}$, but are
assigned to different initial velocities drawn from the Maxwell–Boltzmann
distribution.

The above numerical protocol is analogous to thermal annealing with different
cooling rates, which results in different glass transition temperatures. Each
glass transition density $\varphi_{\rm g}$ selects a particular glass state.
The value of $\varphi_{\rm g}$ ranges from the mode-coupling theory (MCT)
density (or the dynamical glass transition density) $\varphi_{\rm d}$, at
which the liquid relaxation is slow but affected by activated
$\alpha$-processes, to $\varphi_{\rm g}\gg\varphi_{\rm d}$, where particle
diffusion and vibrations are fully separated. For sufficiently large
$\varphi_{\rm g}$, the $\alpha$-relaxation time becomes larger than the
simulation time by many orders of magnitude; one thus obtains unimpeded access
to the dynamics within the glass state, i.e., the $\beta$-relaxation processes
Goldstein (2010).

Figure 3:  Phase diagram of a polydisperse hard-sphere glass in three
dimensions (adapted from Berthier  _et al._ (2016)). Solids lines represent
the CS liquid EOS and the Gardner line, and dashed lines represent glass EOSs.
The insets show typical particle motions in three phases.

The liquid equation of state (EOS) for the reduced pressure $p=\beta P/\rho$
of the model, where $\rho$ is the number density, and $P$ the system pressure,
can be well described by the Carnahan-Starling (CS) equation Boublik (1970).
The dynamical glass transition density $\varphi_{\rm d}=0.594(1)$ was
estimated following the strategy in Ref. Charbonneau  _et al._ (2014a). Note
that the dynamical glass transition is only rigorous in large dimensions; it
becomes a dynamical crossover in three dimensions  (see Chapter 16 for a
detailed discussion). The non-equilibrium glass EOSs associated with
compression terminate at inherent states (where $p\to\infty$) that correspond
to, for hard spheres, jammed configurations at $\varphi_{\rm J}$, and can be
captured by a free-volume scaling form, $p_{\rm
glass}(\varphi)\sim(\varphi_{\rm J}-\varphi)$ Donev  _et al._ (2005).  Figure
3 presents the phase diagram and EOSs of the model.

Along each glass EOS of a given $\varphi_{\rm g}$, a corresponding Gardner
transition may exist at density $\varphi_{\rm G}$ (or pressure $p_{\rm G}$),
as predicted by the mean-field theory. For $\varphi_{\rm
g}<\varphi<\varphi_{\rm G}$, the system is in a stable glass phase: each glass
state is confined in one of the structureless basins on the free-energy
landscape (see  Fig. 1(A)), and is stable in response to small mechanical
deformations. On the other hand, the regime $\varphi_{\rm
G}<\varphi<\varphi_{\rm J}$ corresponds to a marginal glass phase, where each
simple glass basin splits into a fractal hierarchy of sub-basins and the glass
becomes marginally stable to deformations. The Gardner line and the liquid EOS
merge around $\varphi_{\rm d}$, suggesting the mixing of dynamical behavior
associated to the Gardner transition and to the glass transition – this is why
one needs to focus on ultra-stable glasses in order to explore pure Gardner
physics.

###  II.2 Key observables and protocols

In the glass state, particles vibrate inside their cages (see the insets of
Fig. 3). The first approach to study the Gardner transition is based on the
direct analysis of caging order parameters, which quantify the caging
properties of particles. In the case of stable glasses, the caging order
parameter is defined as, $\Delta_{\rm
EA}=\lim_{t\to\infty}\frac{1}{N}\sum_{i=1}^{N}\langle|\vec{r}_{i}(t)-\vec{r}_{i}(0)|^{2}\rangle$,
where $\vec{r}_{i}(t)$ is the position of particle $i$ at time $t$. The
parameter $\Delta_{\rm EA}$, which decreases with the degree of annealing,
corresponds to nothing but the EA parameter $q_{\rm EA}$ in spin-glasses.

Similar to the spin-glass transition, the Gardner transition induces the split
of basins on the free-energy landscape and aging effects, which suggests that
the order parameter must be generalized: one considers (i) the mean-squared
displacement (MSD) $\Delta(\tau,t_{\rm w})$ and (ii) the distance between
pairs of independently quenched configurations $\Delta_{AB}(t)$. Here the MSD
is defined as, $\Delta(\tau,t_{\rm
w})=\frac{1}{N}\sum_{i=1}^{N}\langle|\vec{r}_{i}(\tau+t_{\rm
w})-\vec{r}_{i}(t_{\rm w})|^{2}\rangle$, averaged over both thermal
fluctuations and disorder, at the target $\varphi$ reached by compression. A
waiting time $t_{\rm w}$ is introduced in order to explicitly examine the
aging effects (the total time $t$ is the sum of the measurement time $\tau$
and $t_{\rm w}$). On the other hand,
$\Delta_{AB}(t)=\frac{1}{N}\sum_{i=1}^{N}\langle|\vec{r}_{i}^{A}(t)-\vec{r}_{i}^{B}(t)|^{2}\rangle$,
where the two copies $A$ and $B$ are independent realizations at $\varphi$,
compressed from the same initial sample at $\varphi_{\rm g}$.

The large-time limits of these quantities have important physical meanings.
The EA order parameter is defined as $\Delta_{\rm
EA}\equiv\lim_{\tau\to\infty}\lim_{t_{\rm w}\to\infty}\Delta(\tau,t_{\rm w})$.
Here the order of time limits is crucial Bouchaud  _et al._ (1998): by
reversing the order one can define another parameter,
$\Delta_{AB}\equiv\lim_{t_{\rm
w}\to\infty}\lim_{\tau\to\infty}\Delta(\tau,t_{\rm
w})=\lim_{t\to\infty}\Delta_{AB}(t)$. The RSB is signaled by $\Delta_{\rm
AB}>\Delta_{\rm EA}$ (note that $\Delta_{AB}=\Delta_{\rm EA}$ in stable
glasses). In other words, the two large-time limits cannot be interchanged in
the Gardner phase, meaning that the aging effects become persistent.

In the second approach, one studies the response of hard-sphere glasses
against a shear strain $\gamma$, analogous to observing magnetic
susceptibilities in spin-glasses. The simple strain $\gamma$ is applied to the
$x$-coordinates of all particles ($x_{i}\to x_{i}+\gamma z_{i}$) after a
waiting time $t_{\rm w}$, under the constant-volume and Lees-Edwards boundary
conditions Lees and Edwards (1972). The strain is increased slowly with a
constant shear rate  $\dot{\gamma}$, and the reduced shear stress
$\sigma=\beta\Sigma/\rho$ is measured, where $\Sigma$ is the stress (for
convenience, some data are presented with the unitless stress rescaled by
pressure, $\tilde{\sigma}=\sigma/p$).

As in the spin-glass case, one can consider two types of protocols, namely
zero field compression (ZFC) and field compression (FC) (see Fig. 1 (B)). In
the ZFC protocol, one compresses the configuration from $\varphi_{\rm g}$ to
$\varphi$, waits for time $t_{\rm w}$ before applying a shear strain
$\delta\gamma$ instantaneously, and then measures the stress $\sigma_{\rm
ZFC}(\tau,t_{\rm w})$ as a function of $\tau$. In the FC protocol, one applies
$\delta\gamma$ at the initial density $\varphi_{\rm g}$, and then measures the
stress $\sigma_{\rm FC}(t)$ once the configuration is compressed to $\varphi$
($t$ is reset to zero after compression). Similar to the caging order
parameters, two large-time limits can be considered: $\sigma_{\rm
ZFC}\equiv\lim_{\tau\to\infty}\lim_{t_{\rm w}\to\infty}\sigma_{\rm
ZFC}(\tau,t_{\rm w})$ and $\sigma_{\rm FC}\equiv\lim_{t_{\rm
w}\to\infty}\lim_{\tau\to\infty}\sigma_{\rm ZFC}(\tau,t_{\rm w})$.

Theories have demonstrated that the above two approaches (more specifically,
the caging order parameters $\Delta$ and the shear moduli
$\mu=\sigma/\delta\gamma$) are intrinsically related Yoshino and Zamponi
(2014): in the large pressure limit, $\mu_{\rm ZFC}\sim 1/\Delta_{\rm EA}$ and
$\mu_{\rm FC}/p\sim 1/\Delta_{AB}$. These relationships are the counterpart of
the duality between overlapping order parameters and magnetic susceptibilities
in spin-glasses.

###  II.3 Aging effects

Figure 4: Time evolutions of (A) caging order parameters (adapted from
Berthier  _et al._ (2016)) and (B) shear moduli (adapted from Jin and Yoshino
(2017)), in the Gardner phase of the hard-sphere glass model.

In the Gardner phase ($\varphi>\varphi_{\rm G}$), aging effects can be
observed in both MSD (without shear deformations) and shear responses. Figure
4(A) shows the simulation data of MSD. After a short time $\tau_{\rm b}\sim 1$
of ballistic motions, the evolution of $\Delta(\tau,t_{\rm w})$, as a function
of $\tau$, exhibits a plateau followed by further growth. The switch from the
former to the latter happens at longer times with increasing waiting time
$t_{\rm w}$. The height of the short-time plateau gives $\Delta_{\rm EA}$
(practically, we set $\Delta_{\rm EA}=\Delta(\tau=\tau_{\rm b},t_{\rm w}=0)$).
Figure 4(A) also displays $\Delta_{AB}(t)$, which is time-independent and
should correspond to a long-time plateau of $\Delta(\tau,t_{\rm w})$ (this
plateau is unfortunately beyond the current simulation time window). The clear
separation of the two parameters ($\Delta_{AB}>\Delta_{\rm EA}$) is the first
numerical evidence of the ergodicity breaking in the Gardner phase Charbonneau
_et al._ (2015a); Berthier  _et al._ (2016); Seoane and Zamponi (2018).

Figure 4(B) shows the time-dependent (unitless) shear moduli,
$\tilde{\mu}(\tau,t_{\rm w})$, whose behavior is similar to that of MSD. An
important feature is that $\tilde{\mu}_{\rm ZFC}(\tau,t_{\rm w})$ exhibits a
plateau suggesting the existence of $\tilde{\mu}_{\rm ZFC}$. On the other
hand, $\tilde{\mu}_{\rm FC}(t)$ is essentially a constant in time $t$ (for
$t>\tau_{\rm b}$), which shall be denoted as $\tilde{\mu}_{\rm FC}$. In the
proper order of large-time limits, one expects that $\tilde{\mu}_{\rm
ZFC}(\tau,t_{\rm w})$ decays to $\tilde{\mu}_{\rm FC}$, as $\lim_{t_{\rm
w}\to\infty}\lim_{\tau\to\infty}\tilde{\mu}_{\rm ZFC}(\tau,t_{\rm
w})=\tilde{\mu}_{\rm FC}$, but the convergence becomes slower as $t_{\rm w}$
increases. Apparently $\tilde{\mu}_{\rm ZFC}$ is larger than $\tilde{\mu}_{\rm
FC}$, which parallels $\Delta_{AB}>\Delta_{\rm EA}$.

###  II.4 Anomalous order parameters and responses

Figure 5 shows the pressure dependence of caging order parameters
($\Delta_{\rm EA}$ and $\Delta_{AB}$) and shear moduli ($\tilde{\mu}_{\rm
ZFC}$ and $\tilde{\mu}_{\rm FC}$) obtained through the above-mentioned dynamic
measurements. One finds that, in the stable glass phase ($p<p_{\rm G}$),
$\Delta_{\rm EA}=\Delta_{\rm AB}$ and $\tilde{\mu}_{\rm ZFC}=\tilde{\mu}_{\rm
FC}$, while in the Gardner phase ($p>p_{\rm G}$), $\Delta_{\rm EA}<\Delta_{\rm
AB}$ and $\tilde{\mu}_{\rm ZFC}>\tilde{\mu}_{\rm FC}$. In the large pressure
limit, mean-field theories predict that $\Delta_{\rm EA}\sim p^{-\kappa}$
Charbonneau  _et al._ (2014b) and $\mu_{\rm ZFC}\sim p^{\kappa}$ Yoshino and
Zamponi (2014), where $\kappa=1.41574$. The former is verified by three-
dimensional simulations in Ref. Charbonneau  _et al._ (2014b) and the latter
by those in Ref. Jin and Yoshino (2017) (see Fig. 5(B)). The theories also
give large-$p$ predictions $\mu_{\rm FC}/p\sim
1/\Delta_{AB}\sim\rm{constant}$, which are consistent with the simulation
results in Fig. 5.

Figure 5:  (A) Bifurcation of caging order parameters $\Delta_{\rm EA}$ and
$\Delta_{AB}$ around the Gardner transition $p_{\rm G}\approx 2.7\times
10^{2}$ (adapted from Berthier  _et al._ (2016)). (B) Protocol-dependent shear
moduli $\tilde{\mu}_{\rm ZFC}$ and $\tilde{\mu}_{\rm FC}$ (adapted from Jin
and Yoshino (2017)). The solid line indicates the scaling $\mu_{\rm ZFC}\sim
p^{1.41574}$ predicted by the mean-field theory Yoshino and Zamponi (2014).

##  III Gardner transition under shear

As predicted theoretically Rainone  _et al._ (2015), a Gardner transition at
$\gamma_{\rm G}$ could occur under shear, before the glass yields at
$\gamma_{\rm Y}$.  Figure 6(A) shows the stability map of hard sphere glasses
under shear and compression/decompression Jin  _et al._ (2018); Altieri and
Zamponi (2019). The Gardner transition and yielding give rise to three types
of behavior in a typical cyclic shear test (see  Fig. 6(B)). (i) The stress-
strain curve is reversible in the stable glass phase ($\gamma<\gamma_{\rm
G}$). (ii) If the shear strain is reversed at a maximum strain $\gamma_{\rm
max}$ between $\gamma_{\rm G}$ and $\gamma_{\rm Y}$, a hysteresis loop
emerges, which however disappears below $\gamma_{\rm G}$. This partial-
reversible phenomenon is a manifestation of the hierarchical free-energy
landscape consisting of basins within a common meta-basin. The part of the
stress-strain curve in the Gardner phase ($\gamma_{\rm G}<\gamma<\gamma_{\rm
Y}$) is jerky due to many small avalanches, reflecting the marginal stability.
(iii) If $\gamma_{\rm max}>\gamma_{\rm Y}$, the cycle becomes strongly
irreversible, suggesting the destruction of glass meta-basin after yielding.

Figure 6:  (A) Stability map of hard-sphere glasses, obtained from the initial
glass at $\varphi=\varphi_{\rm g}$ and $\gamma=0$ (square). (B) Stress-strain
curves measured in cyclic shear simulations  at a constant $\varphi=0.66$.
Black and gray lines correspond to $\gamma_{\rm G}<\gamma_{\rm
max}<\gamma_{\rm Y}$ and $\gamma_{\rm max}>\gamma_{\rm Y}$.  Adapted from Jin
_et al._ (2018)).

##  IV Discussion and outlook

As a second-order phase transition, the fluctuation of order parameters (or
the susceptibility) is expected to diverge at the Gardner transition in the
thermodynamic limit. Simulations have shown that the caging susceptibility
grows orders of magnitude approaching the Gardner transition Berthier  _et
al._ (2016). Furthermore, the spatial correlations between local caging order
parameters become long-ranged in the Gardner phase,  implying the
heterogeneity of vibrational dynamics Berthier  _et al._ (2016); Liao and
Berthier (2019). However, dynamical activations could possibly turn a mean-
field thermodynamic phase transition into a crossover in low dimensions.  It
remains inconclusive whether a sharp Gardner transition survives in three
dimensions, although a renormalization group theory based on loop expansions
Charbonneau and Yaida (2017) (see Chapter 3 for details) and a machine-
learning facilitated finite-size analysis of simulation data Li  _et al._
(2021) seem to suggest so.

The discussion so far has focused on the hard-sphere model. Hard spheres have
a well-defined singularity under compression, the jamming transition, where
quantities such as pressure and the length scale of mechanical response
diverge (see Chapter 19 for a review on the jamming transition). Because the
jamming transition lies in the Gardner phase, the full RSB predictions should
also apply to the criticality and marginality of jamming, which are quantified
by power-law scalings of weak forces, small interparticle gaps Charbonneau
_et al._ (2014b) and low-frequency vibrational modes Franz  _et al._ (2015).
Remarkably, numerical results seemingly agree with the mean-field exponents
even in low dimensions Charbonneau  _et al._ (2014b, 2015b, 2016). The
evidence of ultrametricity that characterizes the hierarchical energy
landscape, has also been demonstrated numerically in jammed packings in three
dimensions Dennis and Corwin (2020).

The Gardner transition seems to emerge as a “precursor” of certain
singularities (jamming under compression and yielding under shear) in hard
particles. The situation is more complicated in cases without such
singularities, e.g., cooling soft spheres under the constant density
condition. On the one hand, the mean-field theory universally identifies the
existence of Gardner transition in soft spheres Scalliet  _et al._ (2019), and
simulations have reported a rejuvenation-memory effect Scalliet and Berthier
(2019) similar to that found in spin-glasses. On the other hand, however,
simulations demonstrate that the Gardner transition could be interfered with
by low-dimensional effects such as localized “defects” Scalliet  _et al._
(2017). Separating the Gardner physics from strong low-dimensional effects in
soft spheres remains a challenge in simulations.

Finally, experimental efforts to detect the Gardner transition have shown
encouraging progress. The caging order parameter approach is applied to
vibrated granular discs, providing evidence of the Gardner phase Seguin and
Dauchot (2016). In the Gardner phase, one expects a logarithmic growth of the
MSD with lag time, which is verified in an experiment of glassy colloidal
suspensions Hammond and Corwin (2020). The experimental data of shear modulus
and MSD in a hard-sphere colloidal glass are consistent with the scalings
$\mu_{\rm ZFC}\sim 1/\Delta_{\rm EA}\sim p^{\kappa}$ Zargar  _et al._ (2017).
The critical scalings of weak forces and small interparticle gaps have also
been verified by precise experimental measurements of jammed photo-elastic
disks Wang  _et al._ (2022).  The evidence of a Gardner-like transition is
reported in a two-dimensional bidisperse granular crystal Kool  _et al._
(2022), suggesting that the Gardner physics could be observed with minimum
disorder Charbonneau  _et al._ (2019). Examining protocol-dependent shear
moduli and complex aging dynamics could provide future directions for the
experimental exploration of Gardner physics.

## References

  * Parisi  _et al._ (2020) Giorgio Parisi, Pierfrancesco Urbani, and Francesco Zamponi,  _Theory of Simple Glasses: Exact Solutions in Infinite Dimensions_ (Cambridge University Press, 2020).
  * Berthier  _et al._ (2019) Ludovic Berthier, Giulio Biroli, Patrick Charbonneau, Eric I Corwin, Silvio Franz, and Francesco Zamponi, “Gardner physics in amorphous solids and beyond,” The Journal of chemical physics 151, 010901 (2019).
  * Mézard  _et al._ (1987) M. Mézard, G. Parisi, and M. A. Virasoro,  _Spin glass theory and beyond_ (World Scientific, Singapore, 1987).
  * Nagata  _et al._ (1979) Shoichi Nagata, PH Keesom, and HR Harrison, “Low-dc-field susceptibility of cu mn spin glass,” Physical Review B 19, 1633 (1979).
  * Edwards and Anderson (1975) Samuel Frederick Edwards and Phil W Anderson, “Theory of spin glasses,” Journal of Physics F: Metal Physics 5, 965 (1975).
  * Castellani and Cavagna (2005) Tommaso Castellani and Andrea Cavagna, “Spin-glass theory for pedestrians,” Journal of Statistical Mechanics: Theory and Experiment 2005, P05012 (2005).
  * Granberg  _et al._ (1988) P Granberg, L Sandlund, P Nordblad, P Svedlindh, and L Lundgren, “Observation of a time-dependent spatial correlation length in a metallic spin glass,” Physical Review B 38, 7097 (1988).
  * Vincent  _et al._ (1997) Eric Vincent, Jacques Hammann, Miguel Ocio, Jean-Philippe Bouchaud, and Leticia F Cugliandolo, “Slow dynamics and aging in spin glasses,” in  _Complex Behaviour of Glassy Systems_ (Springer, 1997) pp. 184–219.
  * Nordblad and Svedlindh (1998) Per Nordblad and Peter Svedlindh, “Experiments on spin glasses,” in  _Spin Glasses and Random Fields_ (World Scientific, 1998) pp. 1–27.
  * Cugliandolo and Kurchan (1993) Leticia F Cugliandolo and Jorge Kurchan, “Analytical solution of the off-equilibrium dynamics of a long-range spin-glass model,” Physical Review Letters 71, 173 (1993).
  * Cugliandolo and Kurchan (1994) Leticia F Cugliandolo and Jorge Kurchan, “On the out-of-equilibrium relaxation of the sherrington-kirkpatrick model,” Journal of Physics A: Mathematical and General 27, 5749 (1994).
  * Cugliandolo  _et al._ (1997) Leticia F Cugliandolo, Jorge Kurchan, and Luca Peliti, “Energy flow, partial equilibration, and effective temperatures in systems with slow dynamics,” Physical Review E 55, 3898 (1997).
  * Franz  _et al._ (1998) Silvio Franz, Marc Mézard, Giorgio Parisi, and Luca Peliti, “Measuring equilibrium properties in aging systems,” Physical Review Letters 81, 1758 (1998).
  * Marinari  _et al._ (2000) Enzo Marinari, Giorgio Parisi, Federico Ricci-Tersenghi, and Juan J Ruiz-Lorenzo, “Off-equilibrium dynamics at very low temperatures in three-dimensional spin glasses,” Journal of Physics A: Mathematical and General 33, 2373 (2000).
  * Yoshino  _et al._ (2002) Hajime Yoshino, Koji Hukushima, and Hajime Takayama, “Extended droplet theory for aging in short-range spin glasses and a numerical examination,” Physical Review B 66, 064431 (2002).
  * Bray and Moore (1987) Alan J Bray and Michael A Moore, “Chaotic nature of the spin-glass phase,” Physical review letters 58, 57 (1987).
  * Fisher and Huse (1988a) Daniel S Fisher and David A Huse, “Equilibrium behavior of the spin-glass ordered phase,” Physical Review B 38, 386 (1988a).
  * Fisher and Huse (1988b) Daniel S Fisher and David A Huse, “Nonequilibrium dynamics of spin glasses,” Physical Review B 38, 373 (1988b).
  * Kondor (1989) I Kondor, “On chaos in spin glasses,” Journal of Physics A: Mathematical and General 22, L163 (1989).
  * Rizzo and Crisanti (2003) Tommaso Rizzo and Andrea Crisanti, “Chaos in temperature in the sherrington-kirkpatrick model,” Physical review letters 90, 137201 (2003).
  * Rizzo and Yoshino (2006) Tommaso Rizzo and Hajime Yoshino, “Chaos in glassy systems from a thouless-anderson-palmer perspective,” Physical Review B 73, 064416 (2006).
  * Yoshino and Rizzo (2008) Hajime Yoshino and Tommaso Rizzo, “Stepwise responses in mesoscopic glassy systems: A mean-field approach,” Physical Review B 77, 104429 (2008).
  * Parisi and Rizzo (2010) Giorgio Parisi and Tommaso Rizzo, “Chaos in temperature in diluted mean-field spin-glass,” Journal of Physics A: Mathematical and Theoretical 43, 235003 (2010).
  * Le Doussal  _et al._ (2010) Pierre Le Doussal, Markus Müller, and Kay Jörg Wiese, “Avalanches in mean-field models and the barkhausen noise in spin-glasses,” EPL (Europhysics Letters) 91, 57004 (2010).
  * Le Doussal  _et al._ (2012) Pierre Le Doussal, Markus Müller, and Kay Jörg Wiese, “Equilibrium avalanches in spin glasses,” Physical Review B 85, 214402 (2012).
  * Franz and Spigler (2017) Silvio Franz and Stefano Spigler, “Mean-field avalanches in jammed spheres,” Physical Review E 95, 022139 (2017).
  * Jonason  _et al._ (1998) K Jonason, E Vincent, J Hammann, JP Bouchaud, and P Nordblad, “Memory and chaos effects in spin glasses,” Physical Review Letters 81, 3243 (1998).
  * Yoshino  _et al._ (2001) Hajime Yoshino, Anaël Lemaıtre, and J-P Bouchaud, “Multiple domain growth and memory in the droplet model for spin-glasses,” The European Physical Journal B-Condensed Matter and Complex Systems 20, 367–395 (2001).
  * Jönsson  _et al._ (2004) PE Jönsson, R Mathieu, Per Nordblad, H Yoshino, H Aruga Katori, and A Ito, “Nonequilibrium dynamics of spin glasses: Examination of the ghost domain scenario,” Physical Review B 70, 174402 (2004).
  * Yoshino and Mézard (2010) Hajime Yoshino and Marc Mézard, “Emergence of rigidity at the structural glass transition: A first-principles computation,” Physical review letters 105, 015504 (2010).
  * Yoshino (2012) Hajime Yoshino, “Replica theory of the rigidity of structural glasses,” The Journal of Chemical Physics 136, 214108 (2012).
  * Yoshino and Zamponi (2014) Hajime Yoshino and Francesco Zamponi, “Shear modulus of glasses: Results from the full replica-symmetry-breaking solution,” Physical Review E 90, 022302 (2014).
  * Maimbourg  _et al._ (2016) Thibaud Maimbourg, Jorge Kurchan, and Francesco Zamponi, “Solution of the dynamics of liquids in the large-dimensional limit,” Physical review letters 116, 015902 (2016).
  * Kurchan  _et al._ (2016) Jorge Kurchan, Thibaud Maimbourg, and Francesco Zamponi, “Statics and dynamics of infinite-dimensional liquids and glasses: a parallel and compact derivation,” Journal of Statistical Mechanics: Theory and Experiment 2016, 033210 (2016).
  * Agoritsas  _et al._ (2019a) Elisabeth Agoritsas, Thibaud Maimbourg, and Francesco Zamponi, “Out-of-equilibrium dynamical equations of infinite-dimensional particle systems i. the isotropic case,” Journal of Physics A: Mathematical and Theoretical 52, 144002 (2019a).
  * Agoritsas  _et al._ (2019b) Elisabeth Agoritsas, Thibaud Maimbourg, and Francesco Zamponi, “Out-of-equilibrium dynamical equations of infinite-dimensional particle systems. ii. the anisotropic case under shear strain,” Journal of Physics A: Mathematical and Theoretical 52, 334001 (2019b).
  * Kranendonk and Frenkel (1991) WGT Kranendonk and D Frenkel, “Computer simulation of solid-liquid coexistence in binary hard sphere mixtures,” Molecular physics 72, 679–697 (1991).
  * Grigera and Parisi (2001) Tomás S Grigera and Giorgio Parisi, “Fast monte carlo algorithm for supercooled soft spheres,” Physical Review E 63, 045102 (2001).
  * Berthier  _et al._ (2016) Ludovic Berthier, Patrick Charbonneau, Yuliang Jin, Giorgio Parisi, Beatriz Seoane, and Francesco Zamponi, “Growing timescales and lengthscales characterizing vibrations of amorphous solids,” Proceedings of the National Academy of Sciences 113, 8397–8401 (2016).
  * Lubachevsky and Stillinger (1990) Boris D Lubachevsky and Frank H Stillinger, “Geometric properties of random disk packings,” Journal of statistical Physics 60, 561–583 (1990).
  * Goldstein (2010) Martin Goldstein, “Communications: Comparison of activation barriers for the Johari–Goldstein and alpha relaxations and its implications,” J. Chem. Phys. 132, 041104 (2010).
  * Boublik (1970) T. Boublik, “Hard sphere equation of state,” J. Chem. Phys. 53, 471 (1970).
  * Charbonneau  _et al._ (2014a) Patrick Charbonneau, Yuliang Jin, Giorgio Parisi, and Francesco Zamponi, “Hopping and the Stokes–Einstein relation breakdown in simple glass formers,” Proc. Natl. Acad. Sci. U.S.A. 111, 15025–15030 (2014a).
  * Donev  _et al._ (2005) Aleksandar Donev, Salvatore Torquato, and Frank H Stillinger, “Pair correlation function characteristics of nearly jammed disordered and ordered hard-sphere packings,” Physical Review E 71, 011105 (2005).
  * Bouchaud  _et al._ (1998) Jean-Philippe Bouchaud, Leticia F Cugliandolo, Jorge Kurchan, and Marc Mézard, “Out of equilibrium dynamics in spin-glasses and other glassy systems,” Spin glasses and random fields 12, 161 (1998).
  * Lees and Edwards (1972) AW Lees and SF Edwards, “The computer study of transport processes under extreme conditions,” J. Phys. Condens. Matter 5, 1921 (1972).
  * Jin and Yoshino (2017) Yuliang Jin and Hajime Yoshino, “Exploring the complex free-energy landscape of the simplest glass by rheology,” Nature communications 8, 1–8 (2017).
  * Charbonneau  _et al._ (2015a) Patrick Charbonneau, Yuliang Jin, Giorgio Parisi, Corrado Rainone, Beatriz Seoane, and Francesco Zamponi, “Numerical detection of the gardner transition in a mean-field glass former,” Physical Review E 92, 012316 (2015a).
  * Seoane and Zamponi (2018) Beatriz Seoane and Francesco Zamponi, “Spin-glass-like aging in colloidal and granular glasses,” Soft Matter 14, 5222–5234 (2018).
  * Charbonneau  _et al._ (2014b) Patrick Charbonneau, Jorge Kurchan, Giorgio Parisi, Pierfrancesco Urbani, and Francesco Zamponi, “Fractal free energy landscapes in structural glasses,” Nature communications 5, 1–6 (2014b).
  * Rainone  _et al._ (2015) Corrado Rainone, Pierfrancesco Urbani, Hajime Yoshino, and Francesco Zamponi, “Following the evolution of hard sphere glasses in infinite dimensions under external perturbations: Compression and shear strain,” Physical review letters 114, 015701 (2015).
  * Jin  _et al._ (2018) Yuliang Jin, Pierfrancesco Urbani, Francesco Zamponi, and Hajime Yoshino, “A stability-reversibility map unifies elasticity, plasticity, yielding, and jamming in hard sphere glasses,” Science advances 4, eaat6387 (2018).
  * Altieri and Zamponi (2019) Ada Altieri and Francesco Zamponi, “Mean-field stability map of hard-sphere glasses,” Physical Review E 100, 032140 (2019).
  * Liao and Berthier (2019) Qinyi Liao and Ludovic Berthier, “Hierarchical landscape of hard disk glasses,” Physical Review X 9, 011049 (2019).
  * Charbonneau and Yaida (2017) Patrick Charbonneau and Sho Yaida, “Nontrivial critical fixed point for replica-symmetry-breaking transitions,” Physical review letters 118, 215701 (2017).
  * Li  _et al._ (2021) Huaping Li, Yuliang Jin, Ying Jiang, and Jeff ZY Chen, “Determining the nonequilibrium criticality of a gardner transition via a hybrid study of molecular simulations and machine learning,” Proceedings of the National Academy of Sciences 118 (2021).
  * Franz  _et al._ (2015) Silvio Franz, Giorgio Parisi, Pierfrancesco Urbani, and Francesco Zamponi, “Universal spectrum of normal modes in low-temperature glasses,” Proceedings of the National Academy of Sciences 112, 14539–14544 (2015).
  * Charbonneau  _et al._ (2015b) Patrick Charbonneau, Eric I Corwin, Giorgio Parisi, and Francesco Zamponi, “Jamming criticality revealed by removing localized buckling excitations,” Physical review letters 114, 125504 (2015b).
  * Charbonneau  _et al._ (2016) Patrick Charbonneau, Eric I Corwin, Giorgio Parisi, Alexis Poncet, and Francesco Zamponi, “Universal non-debye scaling in the density of states of amorphous solids,” Physical review letters 117, 045503 (2016).
  * Dennis and Corwin (2020) RC Dennis and EI Corwin, “Jamming energy landscape is hierarchical and ultrametric,” Physical review letters 124, 078002 (2020).
  * Scalliet  _et al._ (2019) Camille Scalliet, Ludovic Berthier, and Francesco Zamponi, “Marginally stable phases in mean-field structural glasses,” Physical Review E 99, 012107 (2019).
  * Scalliet and Berthier (2019) Camille Scalliet and Ludovic Berthier, “Rejuvenation and memory effects in a structural glass,” Physical review letters 122, 255502 (2019).
  * Scalliet  _et al._ (2017) Camille Scalliet, Ludovic Berthier, and Francesco Zamponi, “Absence of marginal stability in a structural glass,” Physical review letters 119, 205501 (2017).
  * Seguin and Dauchot (2016) Antoine Seguin and Olivier Dauchot, “Experimental evidence of the gardner phase in a granular glass,” Physical review letters 117, 228001 (2016).
  * Hammond and Corwin (2020) Andrew P Hammond and Eric I Corwin, “Experimental observation of the marginal glass phase in a colloidal glass,” Proceedings of the National Academy of Sciences 117, 5714–5718 (2020).
  * Zargar  _et al._ (2017) Rojman Zargar, Eric DeGiuli, and Daniel Bonn, “Scaling for hard-sphere colloidal glasses near jamming,” EPL (Europhysics Letters) 116, 68004 (2017).
  * Wang  _et al._ (2022) Yinqiao Wang, Jin Shang, Yuliang Jin, and Jie Zhang, “Experimental observations of marginal criticality in granular materials,” Proceedings of the National Academy of Sciences 119, e2204879119 (2022).
  * Kool  _et al._ (2022) Lars Kool, Patrick Charbonneau, and Karen E Daniels, “Gardner-like transition from variable to persistent force contacts in granular crystals,” arXiv preprint arXiv:2205.06794 (2022).
  * Charbonneau  _et al._ (2019) Patrick Charbonneau, Eric I Corwin, Lin Fu, Georgios Tsekenis, and Michael van Der Naald, “Glassy, gardner-like phenomenology in minimally polydisperse crystalline systems,” Physical Review E 99, 020901 (2019).


# The structure connectivity of Data Center Networks

Lina Ba and Heping Zhang Corresponding author.

(School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu
730000, P.R. China
E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Last decade, numerous giant data center networks are built to provide
increasingly fashionable web applications. For two integers $m\geq 0$ and
$n\geq 2$, the $m$-dimensional DCell network with $n$-port switches $D_{m,n}$
and $n$-dimensional BCDC network $B_{n}$ have been proposed. Connectivity is a
basic parameter to measure fault-tolerance of networks. As generalizations of
connectivity, structure (substructure) connectivity was recently proposed. Let
$G$ and $H$ be two connected graphs. Let $\mathcal{F}$ be a set whose elements
are subgraphs of $G$, and every member of $\mathcal{F}$ is isomorphic to $H$
(resp. a connected subgraph of $H$). Then $H$-structure connectivity
$\kappa(G;H)$ (resp. $H$-substructure connectivity $\kappa^{s}(G;H)$) of $G$
is the size of a smallest set of $\mathcal{F}$ such that the rest of $G$ is
disconnected or the singleton when removing $\mathcal{F}$. Then it is
meaningful to calculate the structure connectivity of data center networks on
some common structures, such as star $K_{1,t}$, path $P_{k}$, cycle $C_{k}$,
complete graph $K_{s}$ and so on. In this paper, we obtain that
$\kappa(D_{m,n};K_{1,t})=\kappa^{s}(D_{m,n};K_{1,t})=\lceil\frac{n-1}{1+t}\rceil+m$
for $1\leq t\leq m+n-2$ and
$\kappa(D_{m,n};K_{s})=\lceil\frac{n-1}{s}\rceil+m$ for $3\leq s\leq n-1$ by
analyzing the structural properties of $D_{m,n}$. We also compute
$\kappa(B_{n};H)$ and $\kappa^{s}(B_{n};H)$ for
$H\in\\{K_{1,t},P_{k},C_{k}|1\leq t\leq 2n-3,6\leq k\leq 2n-1\\}$ and $n\geq
5$ by using $g$-extra connectivity of $B_{n}$.

Keywords: Fault-tolerance; Structure connectivity; DCell; BCDC.

##  1 Introduction

Networks are often modeled by connected graphs. A node replaces with a vertex
and a link replaces with an edge. Let $G$ be a graph. We set $V(G)$ as vertex
set of $G$ and $E(G)$ as edge set of $G$. Connectivity is a basic parameter in
measuring fault tolerance of networks. In order to more accurately measure
fault-tolerance of large-scale parallel processing systems, $\rho$-conditional
connectivity for some property $\rho$ proposed by Harary [9] referred to the
minimum cardinality of a vertex subset $S$ of $G$ such that $G-S$ is
disconnect and every component has property $\rho$. Thus, $h$-extra
connectivity $\kappa_{h}(G)$ is introduced by Fàbrega and Fiol [5], and the
definition emphasizes that the every component left behind has at least $h+1$
vertices; $h$-restricted connectivity $\kappa^{h}(G)$ is came up with by
Esfahanian and Hakimi [3], and $\kappa^{h}(G)$ requires that any one vertex of
every component left behind has at least $h$ neighborts. In the Network-on-
Chip technology, if there is a fault node on the chip, then we assume that the
whole chip is fault. Because of the facts, structure (substructure)
connectivity is defined by Lin et al. [13]. Let $\mathcal{F}$ be a set of
subgraphs of $G$. If $\mathcal{F}$ disconnects $G$ or $G-\mathcal{F}$ is a
trivial graph, then $\mathcal{F}$ is called a subgraph cut of $G$. For a
connected subgraph $H$ and a subgraph cut $\mathcal{F}$ of $G$, if
$\mathcal{F}$’s every member is isomorphic to $H$ (resp. a connected subgraph
of $H$), then $\mathcal{F}$ is called an $H$-structure cut (resp.
$H$-substructure cut). The size of the smallest $H$-structure cuts (resp.
$H$-substructure cuts) of $G$ is $H$-structure connectivity of $G$,
$\kappa(G;H)$ (resp. $H$-substructure connectivity of $G$, $\kappa^{s}(G;H)$).
Thus, $\kappa^{s}(G;H)\leqslant\kappa(G;H)$. Especially, $K_{1}$-structure
connectivity is equal to vertex connectivity. For the past few years, there
are many studies on structure connectivity for some well-known networks, such
as $HL$-networks [12], alternating group graphs [15], star graph [14], wheel
network [6] and so on.

Data center network, DCN, is a networking infrastructure inside a data center,
which connects many servers by links and switches [7]. Due to the the advances
of science and technology, DCN runs thousands of servers. For instance, Google
has over 450,000 servers operating in 30 data centers by 2006 [1, 10], and
Microsoft and Yahoo! have hundreds of millions of servers running at the same
time in their data centers [2, 18]. Then how to efficiently connect numerous
servers become a fundamental challenge in DCN. Therefore, DCell and BCDC were
proposed by Guo et al. [7] and Wang et al. [19], respectively. DCell defines
by a recursive structure. A server connects to distinct levels of DCells by
multiple links (for details see Definition 1). According to its structure,
with the increase of node degree, DCell shows a doubly exponential growth.
Then, without the use of costly core-switches or core-routers, a DCell with a
degree less than 4 can operate over thousands of servers [7]. An
$n$-dimensional BCDC, $B_{n}$, consists of an independent set and two
$(n-1)$-dimensional BCDC’s (for details see Definition 4). Then the quantity
of servers in BCDC add up fast as the dimension of BCDC grows. Such as, with
the use of 16-port switches, $B_{16}$ operates 524 288 servers at once [19].
It is easy to find that DCell and BCDC provide two ways to connect plentiful
servers efficiently. For these two networks, the best application scenarios
are large data centers, which contain end-user applications (e.g. Web search
and IM) and distributed system operations (e.g. MapReduce and GFS) [7].
Because DCell and BCDC based on complete graphs and crossed cubes,
respectively, they still have lots of good properties, such as high-capacity,
minor diameter and high fault-tolerance. There are a few primary characters of
graphs $D_{m,n}$ and $B_{n}$, such as connectivity, diameter, symmetry,
broadcasting, have been studied recently [7, 19]. As extensions of
connectivity, $h$-restricted connectivity [20, 17] and $h$-extra connectivity
[16, 17] have been studied, yet. Then, we compute the structure connectivities
of $D_{m,n}$ and $B_{n}$ on some common structures, star, complete graph, path
and cycle in this paper.

The paper has the following sections. Section 2 defines a few notations.
Sections 3 presents the star-structure (substructure) connectivity and
complete graph-structure connectivitives of DCell. Sections 4 shows the star-
structure (substructure) connectivity, path-structure (substructure)
connectivity and cycle-structure (substructure) connectivity of BCDC. Section
5 summarizes the content of this paper and indicates some unsolved questions.

##  2 Notations

In this paper, we only consider finite and simple graphs. For a graph $H$ that
satisfies the conditions $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$, we
call $H$ a subgraph of $G$. For a vertex subset $S$ of $G$, $G-S$ is a graph
obtained by deleting the vertex set $S$ and all edges incident to them from
$G$. If $H$ is a subgraph of $G$, then we set $G-H=G-V(H)$. Let $\mathcal{F}$
be a set whose members are subgraphs of $G$. Then
$G-\mathcal{F}=G-V(\mathcal{F})$, where $V(\mathcal{F})$ is the union of the
vertex set of members of $\mathcal{F}$. For a vertex subset $V^{\prime}$ of
$G$, we set $G[V^{\prime}]$ as the induced subgraph by $V^{\prime}$ of $G$,
where $V(G[V^{\prime}])=V^{\prime}$ and $E(G[V^{\prime}])=\\{(u,u^{\prime})\in
E(G)|u,u^{\prime}\in V^{\prime}\\}.$ For any one vertex $x$ of $G$,
$N_{G}(x)=\\{y|xy\in E(G)\\}$. For a vertex subset $A$ of $G$,
$N_{G}(A)=\cup_{x\in A}N_{G}(x)\setminus A$. Let $P_{k}=\langle
v_{1},v_{2},\ldots,v_{k}\rangle$ be a path. We set $P^{-1}_{k}=\langle
v_{k},v_{k-1},\ldots,v_{1}\rangle$ and $P_{k}-v_{i}\cup w=\langle
v_{1},\ldots,v_{i-1},w,v_{i+1},\ldots,v_{k}\rangle$. If $v_{1}=v_{k}$ in
$P_{k}$, $k\geq 3$, then we call it cycle $C_{k}$. Let $\\{x;x_{i}|1\leq i\leq
t\\}$ be a star $K_{1,t}$. Then we set $x$ and $x_{i}$, $1\leq i\leq t$, are
center and leaves, respectively.

##  3 The structure connectivity of DCell

Given an integer $s$, we set $\langle s\rangle=\\{0,1,\ldots,s\\}$ and
$[s]=\\{1,2,\ldots,s\\}$. Define $I_{0,n}=\langle n-1\rangle$ and
$I_{i,n}=\langle t_{i-1,n}\rangle$ for $i\in[m]$. An $m$-dimensional DCell
with $n$-port switches is denoted by $D_{m,n}$ for $m\geq 0$ and $n\geq 2$.
Let $t_{m,n}$ be the number of servers in $D_{m,n}$, where $t_{0,n}=n$ and
$t_{m,n}=t_{m-1,n}\cdot(t_{m-1,n}+1)$ for $m\geq 1$. Servers of $D_{m,n}$ can
be labeled by $\\{x_{m}x_{m-1}\ldots x_{1}x_{0}|x_{i}\in I_{i,n},i\in\langle
m\rangle\\}$.

######  Definition 1.

[7] The $m$-dimensional DCell with $n$-port switches $D_{m,n}$ is defined
recursively as follows.

  1. (1)

$D_{0,n}$ is a complete graph consisting of $n$ servers.

  2. (2)

For $m\geq 1$, $D_{m,n}$ is obtained from $t_{m-1,n}+1$ disjoint copies
$D_{m-1,n}$ by the following steps.

    1. (i)

Let $D^{i}_{m-1,n}$ be a copy of $D_{m-1,n}$ by prefixing label of each server
with $i$ for $i\in I_{m,n}.$

    2. (ii)

Server $u=u_{m}u_{m-1},\ldots,u_{0}$ in $D^{u_{m}}_{m-1,n}$ is adjacent to
server $v=v_{m}v_{m-1},\ldots,v_{0}$ in $D^{v_{m}}_{m-1,n}$ if and only if
$u_{m}=v_{0}+\sum^{m-1}_{j=1}(v_{j}\times t_{j-1,n})$ and
$v_{m}=u_{0}+\sum^{m-1}_{j=1}(u_{j}\times t_{j-1,n})+1$ for any
$u_{m},v_{m}\in I_{m,n}$ and $u_{m}<v_{m}$.

If $u$ has a neighbor $u^{\prime}\notin D^{i}_{m-1,n}$ for $u\in
D^{i}_{m-1,n}$ and $i\in I_{m,n}$, then $u^{\prime}$ is called the outside
neighbor of $u$. Figure 1(a) shows 1-dimensional DCell with 4-port switches.
Since switches are transparent in networks, the graph structure of $D_{1,4}$
is shown in Figure 1(b).

(a)

Figure 1: The 1-dimensional DCell with 4-port switches and the graph structure
of $D_{1,4}$.

######  Lemma 3.1.

_[8]_ For $m\geq 0$ and $n\geq 2$, the following statements hold:

  1. (i)

$D_{m,n}$ is $(m+n-1)$-regular and $|V_{m,n}|=t_{m,n}$,

  2. (ii)

for $m\geq 1$, $D_{m,n}$ consists of $t_{m-1,n}+1$ copies of $D_{m-1,n}$,
denoted by $D^{i}_{m-1,n}$, for each $i\in I_{m,n}$. There is only one edge
between $D^{i}_{m-1,n}$ and $D^{j}_{m-1,n}$ for any $i,j\in I_{m,n}$ and
$i\neq j$, which implies that the outside neighbors of vertices in
$D^{i}_{m-1,n}$ belong to different copies of $D^{j}_{m-1,n}$ for $i,j\in
I_{m,n}$ and $i\neq j$.

For convenience, let

$D_{m,n}=D^{0}_{m-1,n}\otimes D^{1}_{m-1,n}\otimes
D^{2}_{m-1,n}\otimes\ldots\otimes D^{t_{m-1,n}}_{m-1,n}.$ (3.1)

######  Lemma 3.2.

_[7]_ For $m\geq 0$ and $n\geq 2$, $\kappa(D_{m,n})=n+m-1$ and
$t_{m,n}\geq(n+\frac{1}{2})^{2^{m}}-\frac{1}{2}.$

######  Lemma 3.3.

$\kappa^{s}(D_{m,n};K_{1,t})\geq\lceil\frac{n-1}{1+t}\rceil+m$ for $1\leq
t\leq m+n-1.$

###### Proof.

Let’s explain this by mathematical induction on $m$. For $m=0$, $D_{0,n}\cong
K_{n}$. Assume $\kappa^{s}(D_{0,n};K_{1,t})\leq\lceil\frac{n-1}{1+t}\rceil-1$
for $1\leq t\leq n-1.$ Then $D_{0,n}$ has a $K_{1,t}$-substructure cut
$\mathcal{F^{\prime}}$ with
$|\mathcal{F^{\prime}}|\leq\lceil\frac{n-1}{1+t}\rceil-1$. We have

$|V(\mathcal{F^{\prime}})|\leq(1+t)(\lceil\frac{n-1}{1+t}\rceil-1)\leq(1+t)(\frac{n+t-1}{1+t}-1)=n-2.$

Since $\kappa(D_{0,n})=n-1$, $|V(\mathcal{F^{\prime}})|<\kappa(D_{0,n})$, a
contradiction. Then it is true for $m=0$.

Suppose $\kappa^{s}(D_{m-1,n};K_{1,t})\geq\lceil\frac{n-1}{1+t}\rceil+m-1$ for
$1\leq t\leq m+n-2.$ Now, we consider $D_{m,n}$. Let
$\mathcal{F}=\\{T_{i}|0\leq i\leq\lceil\frac{n-1}{1+t}\rceil+m-2\\}$ be a set
of connected subgraphs of $K_{1,t}$ for $1\leq t\leq n+m-1$. We need to show
that $D_{m,n}-\mathcal{F}$ is connected. Let $\mathcal{F}^{i}=\mathcal{F}\cap
D^{i}_{m-1,n}$, $\mathcal{F}^{M}=\cup_{i\in M}\mathcal{F}^{i}$ and
$D_{m-1,n}^{M}=\cup_{i\in M}D^{i}_{m-1,n}$ by Eq. (3.1). We know that each
star is in at most two $D^{i}_{m-1,n}$’s by Definition 1. Then there exist at
most $2(\lceil\frac{n-1}{1+t}\rceil+m-1)$ $D^{i}_{m-1,n}$’s such that
$\mathcal{F}^{i}\neq\emptyset.$ Let $S=\\{0,1,2,\ldots,s\\}$ be a set such
that $\mathcal{F}^{i}\neq\emptyset$ for $i\in S$. Then $|S|\leq
2(\lceil\frac{n-1}{1+t}\rceil+m-1)$. By Lemma 3.2, for $m\geq 1$ and $n\geq
2$,

$\displaystyle t_{m-1,n}+1-|S|\geq
t_{m-1,n}+1-2(\lceil\frac{n-1}{1+t}\rceil+m-1)\geq
t_{m-1,n}+1-2(\frac{n+t-1}{1+t}+m-1)$ $\displaystyle\geq
t_{m-1,n}+1-2(\frac{n}{2}+m-1)\geq(n+\frac{1}{2})^{2^{m-1}}-n-2m+\frac{5}{2}\geq(n+\frac{1}{2})-n-2+\frac{5}{2}=1,$

which implies that there exists $D^{i}_{m-1,n}$ satisfied
$\mathcal{F}^{i}=\emptyset$ for $i\in I_{m,n}\setminus S$. Then
$\mathcal{F}^{I_{m,n}\setminus S}=\emptyset$ and $D_{m-1,n}^{I_{m,n}\setminus
S}-\mathcal{F}^{I_{m,n}\setminus S}=D_{m-1,n}^{I_{m,n}\setminus S}$ is
connected. Let $S_{1}=\\{0,1,2,\ldots,s_{1}\\}$ be a subset of $S$ satisfied
that there exist star-centers in $\mathcal{F}^{i}$ for $i\in S_{1}$. Then
there only leaves of stars in $\mathcal{F}^{i}$ for $i\in S\setminus S_{1}$.

If there exist $D^{i}_{m-1,n}$ and $D^{j}_{m-1,n}$ such that both
$D^{i}_{m-1,n}-\mathcal{F}^{i}$ and $D^{j}_{m-1,n}-\mathcal{F}^{j}$ are
disconnected for $i\in S$, $j\in S$ and $i\neq j$, then
$|\mathcal{F}^{i}|\geq\lceil\frac{n-1}{1+t}\rceil+m-1$ and
$|\mathcal{F}^{j}|\geq\lceil\frac{n-1}{1+t}\rceil+m-1$ by induction
hypothesis. Since $|\mathcal{F}|=\lceil\frac{n-1}{1+t}\rceil+m-1$,
$|\mathcal{F}^{i}|\geq\lceil\frac{n-1}{1+t}\rceil+m-1$ and
$|\mathcal{F}^{j}|\geq\lceil\frac{n-1}{1+t}\rceil+m-1$ are impossible by
Definition 1. Thus there is at most one $D^{i}_{m-1,n}$ satisfied that
$D^{i}_{m-1,n}-\mathcal{F}^{i}$ is disconnected for $i\in S$.

Case 1. Each $D^{i}_{m-1,n}-\mathcal{F}^{i}$ is connected for $i\in S$.

For each $i\in S\setminus S_{1}$, $\mathcal{F}^{i}$ consists of the outside
neighbors of partical star-centers which are in $D^{S_{1}}_{m-1,n}$. Then
$D^{i}_{m-1,n}-\mathcal{F}^{i}$ has an outside neighbor of a vertex which is
in $D^{I_{m,n}\setminus S}_{m-1,n}$ for $i\in S\setminus S_{1}$. Since
$D^{i}_{m-1,n}-\mathcal{F}^{i}$ is connected, $D_{m-1,n}^{I_{m,n}\setminus
S_{1}}-\mathcal{F}^{I_{m,n}\setminus S_{1}}$ is connected. Let $p_{i}$ be the
number of star-centers in $D^{i}_{m-1,n}$ for $i\in S_{1}$. For
$p_{i}=\lceil\frac{n-1}{1+t}\rceil+m-1$, we find $S_{1}=\\{i\\}$. Then each
vertex of $D^{i}_{m-1,n}-\mathcal{F}^{i}$ has an outside neighbor in
$D_{m-1,n}^{I_{m,n}\setminus S}$. Since
$D^{I_{m,n}\setminus\\{i\\}}_{m-1,n}-\mathcal{F}^{I_{m,n}\setminus\\{i\\}}$ is
connected, $D_{m,n}-\mathcal{F}$ is connected (see Figure 2(a)). For
$p_{i}\leq\lceil\frac{n-1}{1+t}\rceil+m-2$, by Lemma 3.2, we have for $n\geq
2$ and $m\geq 2$,

$\displaystyle|V(D^{i}_{m-1,n})|-(1+t)p_{i}-(\lceil\frac{n-1}{1+t}\rceil+m-1-p_{i})=t_{m-1,n}-tp_{i}-(\lceil\frac{n-1}{1+t}\rceil+m-1)\geq$
$\displaystyle
t_{m-1,n}-t(\lceil\frac{n-1}{1+t}\rceil+m-2)-(\lceil\frac{n-1}{1+t}\rceil+m-1)=t_{m-1,n}-(1+t)(\lceil\frac{n-1}{1+t}\rceil+m-1)+t$
$\displaystyle\geq
t_{m-1,n}-(1+t)(\frac{n+t-1}{1+t}+m-1)+t\geq(n+\frac{1}{2})^{2^{m-1}}-n-m-(m-1)t+\frac{3}{2}$
$\displaystyle\geq(n+\frac{1}{2})^{2^{m-1}}-n-m-(m-1)(n+m-1)+\frac{3}{2}=(n+\frac{1}{2})^{2^{m-1}}-mn-m^{2}+m+\frac{1}{2}$
$\displaystyle\geq(2+\frac{1}{2})^{2^{m-1}}-2m-m^{2}+m+\frac{1}{2}\geq(2+\frac{1}{2})^{2}-4-4+2+\frac{1}{2}>0,$

and for $m=1$,

$\displaystyle|V(D^{i}_{0,n})|-(1+t)p_{i}-(\lceil\frac{n-1}{1+t}\rceil-
p_{i})\geq t_{0,n}-(1+t)(\frac{n+t-1}{1+t}+1-1)+t>0,$

which implies that $D^{i}_{m-1,n}-\mathcal{F}^{i}$ has a vertex that is
connected to $D_{m-1,n}^{I_{m,n}\setminus S_{1}}-\mathcal{F}^{I_{m,n}\setminus
S_{1}}$ for each $i\in S_{1}$ (see Figure 2(b)). Thus $D_{m,n}-\mathcal{F}$ is
connected.

Case 2. There is exactly one $D^{i}_{m-1,n}$ such that
$D^{i}_{m-1,n}-\mathcal{F}^{i}$ is disconnected for $i\in S$.

Since $D^{j}_{m-1,n}-\mathcal{F}^{j}$ is connected for $j\in S$ and $j\neq i$,
$D^{I_{m,n}\setminus\\{i\\}}_{m-1,n}-\mathcal{F}^{I_{m,n}\setminus\\{i\\}}$ is
connected by the similar argument as Case 1. By induction hypothesis,
$|\mathcal{F}^{i}|\geq\lceil\frac{n-1}{1+t}\rceil+m-1$. If $i\in S_{1}$, then
each $\mathcal{F}^{j}$ has exactly one star-center and exactly one of leaves
of that star in $\mathcal{F}^{i}$ for $j\in S_{1}\setminus\\{i\\}$, and each
$\mathcal{F}^{j}$ has exactly one leaf of star and its center in
$\mathcal{F}^{i}$ for $j\in S\setminus S_{1}$ (see Figure 2(c)). By Lemma
3.1$(ii)$, each vertex of $D^{i}_{m-1,n}-\mathcal{F}^{i}$ has an outside
neighbor in $D^{I_{m,n}\setminus S}_{m-1,n}$. Thus $D_{m,n}-\mathcal{F}$ is
connected. If $i\in S\setminus S_{1}$, then $S\setminus S_{1}=\\{i\\}$ and
$|S_{1}|=\lceil\frac{n-1}{1+t}\rceil+m-1$. Otherwise,
$|\mathcal{F}^{i}|<\lceil\frac{n-1}{1+t}\rceil+m-1$, a contradiction. For
$j\in S_{1}$, we have that each $\mathcal{F}^{j}$ has exactly one star-center
and one leaf of the star is in $\mathcal{F}^{i}$ (see Figure 2(d)). Thus
$\mathcal{F}^{i}$ has all outside neighbors of vertices which from different
$D^{j}_{m-1,n}$s, $j\in S\setminus\\{i\\}$. By Lemma 3.1$(ii)$, each vertex of
$D^{i}_{m-1,n}-\mathcal{F}^{i}$ has an outside neighbor in
$D^{I_{m,n}\setminus S}_{m-1,n}$. Thus $D_{m,n}-\mathcal{F}$ is connected. ∎

Figure 2: Illustration for Lemma 3.3.

######  Lemma 3.4.

$\kappa(D_{m,n};K_{1,t})\leq\lceil\frac{n-1}{1+t}\rceil+m$ for $1\leq t\leq
m+n-2.$

###### Proof.

Given two vertices $u=00\ldots 00$ and $v=11\ldots 11$ in $D_{m,n}$. Then
$N_{D_{m,n}}(u)=\\{00\ldots 0i|i\in[n-1]\\}\cup\\{10\ldots 00,01\ldots
00,\ldots,00\ldots 10\\}$. Since $D_{m,n}[\\{00\ldots 0i|i\in[n-1]\\}]$ is a
complete graph $K_{n-1}$ by Definition 1, we need
$\lceil\frac{n-1}{1+t}\rceil$ $K_{1,t}$’s to cover all vertices of
$D_{m,n}[\\{00\ldots 0i|i\in[n-1]\\}]$. Then we set

$S_{i}=\left\\{\begin{aligned} &\\{00\ldots 0[(i-1)t+i];00\ldots
0[(i-1)t+i+k]|1\leq k\leq t\\},~{}~{}for~{}~{}1\leq
i\leq\lfloor\frac{n-1}{1+t}\rfloor;\\\ &\\{00\ldots 0(n-1);00\ldots
0k|n-t-1\leq k\leq n-2\\},~{}~{}for~{}~{}i=\lceil\frac{n-1}{1+t}\rceil.\\\
\end{aligned}\right.$

Next, we will construct several stars $K_{1,t}$’s to cover the vertex subset
$\\{10\ldots 00,01\ldots 00,\ldots,00\ldots 10\\}$. For $1\leq j\leq m$, let
$S_{\lceil\frac{n-1}{1+t}\rceil+j}$ be a star with center $0\ldots 010\ldots
0$ ($u_{j}=1$) and its leaves are the neighbors of $0\ldots 010\ldots 0$
except $u$ (see Figure 3(a)).

Let $\mathcal{F}=\\{S_{i}|i\in[\lceil\frac{n-1}{1+t}\rceil+m]\\}$. Since
$N_{D_{m,n}}(u)\subseteq V(\mathcal{F})$ and $v\in V(D_{m,n}-\mathcal{F})$,
$D_{m,n}-\mathcal{F}$ has two components. Then $u$ is a singleton and $v$
belongs to the other component. Thus
$\kappa(D_{m,n};K_{1,t})\leq|\mathcal{F}|=\lceil\frac{n-1}{1+t}\rceil+m$.

∎

Lemmas 3.3 and 3.4 imply that
$\lceil\frac{n-1}{1+t}\rceil+m\leq\kappa^{s}(D_{m,n};K_{1,t})\leq\kappa(D_{m,n};K_{1,t})\leq\lceil\frac{n-1}{1+t}\rceil+m$
for $1\leq t\leq m+n-2$. Then following result holds.

######  Theorem 3.5.

$\kappa(D_{m,n};K_{1,t})=\kappa^{s}(D_{m,n};K_{1,t})=\lceil\frac{n-1}{1+t}\rceil+m$
for $1\leq t\leq m+n-2$.

######  Lemma 3.6.

$\kappa(D_{m,n};K_{s})\geq\lceil\frac{n-1}{s}\rceil+m$ for $3\leq s\leq n-1$.

###### Proof.

Induction on $m$. For $m=0$, $D_{0,n}\cong K_{n}$. Assume
$\kappa(D_{0,n};K_{s})\leq\lceil\frac{n-1}{s}\rceil-1$ for $3\leq s\leq n-1$.
Then there exists a $K_{s}$-structure cut $\mathcal{F^{\prime}}$ of $D_{0,n}$,
$|\mathcal{F^{\prime}}|\leq\lceil\frac{n-1}{s}\rceil-1.$ We have

$|V(\mathcal{F^{\prime}})|\leq s\cdot(\lceil\frac{n-1}{s}\rceil-1)\leq
s\cdot(\frac{n+s-2}{s}-1)=n-2<n-1.$

Since $\kappa(D_{0,n})=n-1$, $|V(\mathcal{F^{\prime}})|<\kappa(D_{0,n})$, a
contradiction. Then $\kappa(D_{0,n};K_{s})\geq\lceil\frac{n-1}{s}\rceil$ for
$3\leq s\leq n-1$.

Assume $\kappa(D_{m-1,n};K_{s})\geq\lceil\frac{n-1}{s}\rceil+m-1$ for $3\leq
s\leq n-1$. Now, we consider $D_{m,n}$. Let $\mathcal{F}=\\{T_{i}|1\leq
i\leq\lceil\frac{n-1}{s}\rceil+m-1\\}$ be a set such that $T_{i}\cong K_{s}$
for $1\leq i\leq\lceil\frac{n-1}{s}\rceil+m-1$. We need to show that
$D_{m,n}-\mathcal{F}$ is connected. Let $\mathcal{F}^{i}=\mathcal{F}\cap
D^{i}_{m-1,n}$, $\mathcal{F}^{T}=\cup_{i\in T}\mathcal{F}^{i}$ and
$D_{m-1,n}^{T}=\cup_{i\in T}D^{i}_{m-1,n}$ by Eq. (3.1). We know that a
complete graph $K_{s}$ for each $3\leq s\leq n-1$ is in exactly one
$D^{i}_{m-1,n}$ by Definition 1. Let $p_{i}$ be the number of $K_{s}$’s in
$D^{i}_{m-1,n}$. If $p_{i}=\lceil\frac{n-1}{s}\rceil+m-1$ for some $i\in
I_{m,n}$, then $\mathcal{F}^{I_{m,n}\setminus\\{i\\}}=\emptyset$. Thus
$D^{I_{m,n}\setminus\\{i\\}}_{m-1,n}-\mathcal{F}^{I_{m,n}\setminus\\{i\\}}$ is
connected. By Definition 1, each vertex of $D^{i}_{m-1,n}-\mathcal{F}^{i}$ has
an outside neighbor in $D^{I_{m,n}\setminus\\{i\\}}_{m-1,n}$. Then
$D_{m,n}-\mathcal{F}$ is connected.

If $p_{i}\leq\lceil\frac{n-1}{s}\rceil+m-2$ for some $i\in I_{m,n}$, then
$D^{i}_{m-1,n}-\mathcal{F}^{i}$ is connected by induction hypothesis. Since
$|\mathcal{F}|=\lceil\frac{n-1}{s}\rceil+m-1$, there are at most
$(\lceil\frac{n-1}{s}\rceil+m-1)$ $D^{i}_{m-1,n}$’s such that
$\mathcal{F}^{i}\neq\emptyset$. Let $X=\\{0,1,\ldots,x\\}$ be a set such that
$\mathcal{F}^{i}\neq\emptyset$ for $i\in X$. Then
$|X|\leq\lceil\frac{n-1}{s}\rceil+m-1$. By Lemma 3.2,

$\displaystyle t_{m-1,n}+1-|X|\geq
t_{m-1,n}+1-(\lceil\frac{n-1}{s}\rceil+m-1)\geq
t_{m-1,n}+1-(\frac{n+s-2}{s}+m-1)$
$\displaystyle\geq(n+\frac{1}{2})^{2^{m-1}}-\frac{1}{2}+1-(\frac{n+1}{3}+m-1)\geq
n+1-\frac{n+1}{3}\geq 2,$

which implies that there exist $D^{i}_{m-1,n}$’s such that
$\mathcal{F}^{i}=\emptyset$ for $i\in I_{m,n}\setminus X$. Then
$\mathcal{F}^{I_{m,n}\setminus X}=\emptyset$ and $D_{m-1,n}^{I_{m,n}\setminus
X}-\mathcal{F}^{I_{m,n}\setminus X}$ is connected. By Lemma 3.2, we find, for
$i\in X$, $m\geq 1$ and $n\geq 2$,

$\displaystyle|V(D^{i}_{m-1,n})|-sp_{i}-(\lceil\frac{n-1}{s}\rceil+m-1-p_{i})=t_{m-1,n}-(s-1)p_{i}-(\lceil\frac{n-1}{s}\rceil+m-1)$
$\displaystyle\geq
t_{m-1,n}-(s-1)(\lceil\frac{n-1}{s}\rceil+m-2)-(\lceil\frac{n-1}{s}\rceil+m-1)=t_{m-1,n}-s(\lceil\frac{n-1}{s}\rceil+m-2)-1$
$\displaystyle\geq
t_{m-1,n}-s(\frac{n+s-2}{s}+m-2)-1\geq(n+\frac{1}{2})^{2^{m-1}}-\frac{1}{2}-n-(m-1)s+1$
$\displaystyle\geq(n+\frac{1}{2})^{2^{m-1}}-n-(m-1)(n-1)+\frac{1}{2}=(n+\frac{1}{2})-n+\frac{1}{2}=1>0,$

which implies that $D^{i}_{m-1,n}-\mathcal{F}^{i}$ has a vertex that is
connected to $D_{m-1,n}^{I_{m,n}\setminus X}$ for each $i\in X$. Since
$D^{i}_{m-1,n}-\mathcal{F}^{i}$ is connected for $i\in X$,
$D_{m,n}-\mathcal{F}$ is connected. ∎

######  Lemma 3.7.

$\kappa(D_{m,n};K_{s})\leq\lceil\frac{n-1}{s}\rceil+m$ for $3\leq s\leq n-1$.

###### Proof.

Given two vertices $u=00\ldots 00$ and $v=11\ldots 11$ in $D_{m,n}$. Then
$N_{D_{m,n}}(u)=\\{00\ldots 0i|i\in[n-1]\\}\cup\\{10\ldots 00,01\ldots
00,\ldots,00\ldots 10\\}$. Let $S_{i}=\\{x_{i}|1\leq i\leq s\\}$ be a complete
graph $K_{s}$. Since $D_{m,n}[\\{00\ldots 0i|i\in[n-1]\\}]$ is a complete
graph $K_{n-1}$ by Definition 1, we need $\lceil\frac{n-1}{s}\rceil$ $K_{s}$’s
to cover all vertices of $D_{m,n}[\\{00\ldots 0i|i\in[n-1]\\}]$. Then we set

$S_{i}=\left\\{\begin{aligned} &\\{00\ldots 0[(i-1)s+k+1]|0\leq k\leq
s-1\\},~{}~{}for~{}~{}1\leq i\leq\lfloor\frac{n-1}{s}\rfloor;\\\ &\\{00\ldots
0k|n-s\leq k\leq n-1\\},~{}~{}for~{}~{}i=\lceil\frac{n-1}{s}\rceil.\\\
\end{aligned}\right.$

Next, we will construct several complete graphs $K_{s}$’s to cover the vertex
subset $\\{10\ldots 00,01\ldots 00,\ldots,00\ldots 10\\}$. For each $j\in[m]$,
let $S_{\lceil\frac{n-1}{s}\rceil+j}$ be a $K_{s}$ with vertices $0\ldots
010\ldots 0k$ ($u_{j}=1$ and $u_{0}=k$) for $0\leq k\leq s-1$. Precisely,
$S_{\lceil\frac{n-1}{s}\rceil+1}=\\{00\ldots 01k|0\leq k\leq s-1\\}$,
$S_{\lceil\frac{n-1}{s}\rceil+2}=\\{00\ldots 10k|0\leq k\leq s-1\\}$,
analogously, $S_{\lceil\frac{n-1}{s}\rceil+m}=\\{10\ldots 00k|0\leq k\leq
s-1\\}$ (see Figure 3(b)).

Let $\mathcal{F}=\\{S_{i}|i\in[\lceil\frac{n-1}{s}\rceil+m]\\}$. Since
$N_{D_{m,n}}(u)\subseteq V(\mathcal{F})$ and $v\in V(D_{m,n}-\mathcal{F})$,
$D_{m,n}-\mathcal{F}$ has two components. Then $u$ is a singleton and $v$
belongs to the other component. Thus
$\kappa(D_{m,n};K_{s})\leq|\mathcal{F}|=\lceil\frac{n-1}{s}\rceil+m$. ∎

(a) A $K_{1,4}$-structure cut of $D_{6,8}$. (b) A $K_{5}$-structure cut of
$D_{6,8}$.

Figure 3: Illustration for Lemmas 3.4 and 3.7.

On the basis of 3.6 and 3.7, the following result holds.

######  Theorem 3.8.

$\kappa(D_{m,n};K_{s})=\lceil\frac{n-1}{s}\rceil+m$ for $3\leq s\leq n-1$.

##  4 The structure connectivity of BCDC

Since $n$-dimensional BCDC consists of two $n-1$-dimensional crossed cubes and
an independent set, we introduce $n$-dimensional crossed cube first.

######  Definition 2.

[4] Two binary strings $x=x_{1}x_{0}$ and $y=y_{1}y_{0}$ are called pair
related (denoted by $x\sim y$) if and only if
$(x,y)\in\\{(00,00),(10,10),(01,11),(11,01)\\}$.

######  Definition 3.

[4] We set $CQ_{1}$ as $K_{2}$ with vertices $0$ and $1$. $CQ_{n}$ consists of
$CQ^{0}_{n-1}$ and $CQ^{1}_{n-1}$. Two vertices $u=0u_{n-2}\ldots u_{0}\in
V(CQ^{0}_{n-1})$ and $v=1v_{n-2}\ldots v_{0}\in V(CQ^{1}_{n-1})$ are joined by
an edge in $CQ_{n}$ if and only if

  1. (i)

$u_{n-2}=v_{n-2}$ if $n$ is even, and

  2. (ii)

$u_{2i+1}u_{2i}\sim v_{2i+1}v_{2i}$, for $0\leq
i<\lfloor\frac{n-1}{2}\rfloor$.

For any two vertices $u=u_{n-1}u_{n-2}\ldots u_{0}$ and
$v=v_{n-1}v_{n-2}\ldots v_{0}$, $u$ is adjacent to $v$ if and only if there is
$0\leq d\leq n-1$ satisfying the following conditions: (1) $u_{n-1}\ldots
u_{d+1}=v_{n-1}\ldots v_{d+1}$, (2) $u_{d}\neq v_{d}$, (3) $u_{d-1}=v_{d-1}$
if $d$ is odd, (4) $u_{2i+1}u_{2i}\sim v_{2i+1}v_{2i}$, for all $0\leq
i\leq\lfloor\frac{d}{2}\rfloor-1$. Then we set $v$ as $d$-dimensional neighbor
of $u$, denoted by $u^{d}$.

BCDC’s switches are vertices of $CQ_{n}$ and servers are edges of $CQ_{n}$.
Each switch is an $n$-bit binary string $x=x_{n-1}x_{n-2}\ldots x_{0}$ and
each server is a pair $[x,y]$. Then we get the original graph $A_{n}$ of the
$n$-dimensional BCDC network, $B_{n}$. Consider that switches are transparent,
the graph structure of BCDC network as follows:

######  Definition 4.

[19] We set $B_{2}$ as a $4$-cycle with vertices $[00,01],[00,10],[01,11]$ and
$[10,11].$ For $n\geq 3$, $B^{0}_{n-1}$ (resp. $B^{1}_{n-1}$) is obtained by
prefixing each vertex $[x,y]$ of $B_{n-1}$ with $0$ (resp. $1$). $B_{n}$
consists of $B^{0}_{n-1}$, $B^{1}_{n-1}$ and a vertex subset
$S_{n}=\\{[a,b]|a\in V(CQ^{0}_{n-1}),b\in V(CQ^{1}_{n-1})$ and $(a,b)\in
E(CQn)\\}$. For three vertices $u=[a,b]\in V(B^{0}_{n-1}),v=[c,d]\in S_{n}$
and $w=[e,f]\in V(B^{1}_{n-1})$,

  1. (i)

$(u,v)\in E(B_{n})$ if and only if $a=c$ or $b=c$;

  2. (ii)

$(v,w)\in E(B_{n})$ if and only if $e=d$ or $f=d$.

(a) $A_{3}$. (b) $CQ_{3}$. (c) $B_{3}$.

Figure 4:  $A_{3}$, $CQ_{3}$ and $B_{3}$.

######  Lemma 4.1.

_[11]_ $CQ_{n}$ is $n$-regular and triangle-free.

######  Lemma 4.2.

_[17]_ For $B_{n}$, we have the statements below:

  1. (i)

$B_{n}$ is $(2n-2)$-regular and has $n2^{n-1}$ vertices, $n(n-1)2^{n-1}$
edges.

  2. (ii)

$\kappa(B_{n})=2n-2$.

  3. (iii)

$B_{n}$ is the line graph of $CQ_{n}$.

######  Lemma 4.3.

_[17]_ For $n\geq 3$ and $0\leq g\leq n-3$,

$\kappa_{g}(B_{n})=\left\\{\begin{aligned} 4,~{}~{}if~{}n=3;\\\
2n+g(n-2)-2,~{}~{}if~{}n\geq 4.\\\ \end{aligned}\right.$

######  Lemma 4.4.

$B_{n}[N_{B_{n}}(u)]$ is two independent complete graphs $K_{n-1}$.

###### Proof.

Given a vertex $u=[v,w]$ in $B_{n}$, where $vw$ is an edge of $CQ_{n}$. Since
$CQ_{n}$ is $n$-regular, we set $N_{CQ_{n}}(v)=\\{w\\}\cup\\{v^{i}|0\leq i\leq
n-2\\}$ and $N_{CQ_{n}}(w)=\\{v\\}\cup\\{w^{i}|0\leq i\leq n-2\\}$. Then
$N_{B_{n}}(u)=\\{[v,v^{i}],[w,w^{i}]|0\leq i\leq n-2\\}$. According to the
Definition 4, $B_{n}[\\{[v,v^{i}]|0\leq i\leq n-2\\}]\cong K_{n-1}$ and
$B_{n}[\\{[w,w^{i}]|0\leq i\leq n-2\\}]\cong K_{n-1}$. Suppose $[v,v^{i}]$ is
adjacent to $[w,w^{j}]$ in $B_{n}$. Then $v^{i}=w^{j}$, which implies that
$v,w$ and $v^{i}$ (or $w^{j}$) induce a triangle in $CQ_{n}$, a contradiction
by Lemma 4.1. Thus $B_{n}[N_{B_{n}}(u)]$ is two independent complete graphs
$K_{n-1}.$ ∎

Figure 5:  Illustration for $B_{9}[N_{B_{9}}(u)]$.

######  Theorem 4.5.

$\kappa(B_{n};K_{1,1})=\kappa^{s}(B_{n};K_{1,1})=\left\\{\begin{aligned}
n-1,~{}~{}for~{}odd~{}n\geq 5;\\\ n,~{}~{}for~{}even~{}n\geq 4.\\\
\end{aligned}\right.$

###### Proof.

Assume $\kappa^{s}(B_{n};K_{1,1})\leq n-2$ ($\leq n-1$) for odd (even) $n$.
Then $B_{n}$ has a $K_{1,1}$-substructure cut $\mathcal{F}$. Let $C$ be a
smallest component of $B_{n}-\mathcal{F}$. For odd $n\geq 5$,
$|V(\mathcal{F})|\leq 2(n-2)<\kappa(B_{n})$ by Lemma 4.2, a contradiction.
Thus $\kappa^{s}(B_{n};K_{1,1})\geq n-1$ for odd $n\geq 5$. For even $n\geq
4$, $|V(\mathcal{F})|\leq 2(n-1)<\kappa_{1}(B_{n})$ by Lemma 4.3. Then
$|V(C)|=1$, say $u$. We have $N_{B_{n}}(u)\subseteq V(\mathcal{F})$. By Lemma
4.4, $n-1$ subgraphs of $K_{1,1}$ can not cover all vertices of
$N_{B_{n}}(u)$, a contradiction. Thus $\kappa^{s}(B_{n};K_{1,1})\geq n$ for
even $n\geq 4$.

We give a $K_{1,1}$-structure cut of $B_{n}$ for $n\geq 4$. Let $u=[v,w]$ be a
vertex of $B_{n}$ with $v=00\ldots 00$ and $w=10\ldots 00$. Then
$N_{B_{n}}(u)=\\{[v,v^{i}],[w,w^{i}]|0\leq i\leq n-2\\}$. For $0\leq
j\leq\lfloor\frac{n-2}{2}\rfloor-1$, we set
$S_{j}=\\{[v,v^{2j}];[v,v^{2j+1}]\\}$ and
$S^{\prime}_{j}=\\{[w,w^{2j}];[w,w^{2j+1}]\\}$. For odd $n$, we set

$\displaystyle
S_{\lfloor\frac{n-2}{2}\rfloor}=\\{[v,v^{n-3}];[v,v^{n-2}]\\},~{}~{}S^{\prime}_{\lfloor\frac{n-2}{2}\rfloor}=\\{[w,w^{n-3}];[w,w^{n-2}]\\}.$

For even $n$, we set

$\displaystyle
S_{\lfloor\frac{n-2}{2}\rfloor}=\\{[v,v^{n-2}];[v^{n-2},v^{n-2,n-1}]\\},~{}~{}S^{\prime}_{\lfloor\frac{n-2}{2}\rfloor}=\\{[w,w^{n-2}];[w^{n-2},w^{n-2,n-1}]\\}.$

Let $\mathcal{F}=\\{S_{j},S^{\prime}_{j}|0\leq
j\leq\lfloor\frac{n-2}{2}\rfloor\\}$. We find $N_{B_{n}}(u)\subseteq
V(\mathcal{F})$ and $[11\ldots 11,11\ldots 10]\notin V(B_{n}-\mathcal{F})$,
which implies that $B_{n}-\mathcal{F}$ has two components. Then $u$ is a
singleton and $[11\ldots 11,11\ldots 10]$ belongs to the other component. Thus
$\kappa(B_{n};K_{1,1})\leq n-1$ for odd $n\geq 5$ and
$\kappa(B_{n};K_{1,1})\leq n$ for even $n\geq 4$. ∎

######  Lemma 4.6.

For $n\geq 4$ and $2\leq t\leq 2n-3$, let $r$ be remainder of $n-1$ divided by
$1+t$. Then

$\kappa^{s}(B_{n};K_{1,t})\geq\left\\{\begin{aligned}
&\frac{2n-4}{1+t}+1,~{}~{}if~{}2\leq t\leq n-3~{}and~{}r=1,\\\
&2\lceil\frac{n-1}{1+t}\rceil,~{}~{}otherwise.\\\ \end{aligned}\right.$

###### Proof.

Suppose to the contrary that $\kappa^{s}(B_{n};K_{1,t})\leq\frac{2n-4}{1+t}$
for $2\leq t\leq n-3$ and $r=1$, and $\kappa^{s}(B_{n};K_{1,t})\leq
2\lceil\frac{n-1}{1+t}\rceil-1$ for otherwise. Then $B_{n}$ has a
$K_{1,t}$-substructure cut $\mathcal{F}$. Let $C$ be a smallest component of
$B_{n}-\mathcal{F}$. Then $|V(\mathcal{F})|\geq\kappa(B_{n})=2n-2$ by Lemma
4.2. For $2\leq t\leq n-3$, if $r=0$, then
$|V(\mathcal{F})|\leq(1+t)(2\lceil\frac{n-1}{1+t}\rceil-1)<2n-2$, a
contradiction. If $r=1$, then
$|V(\mathcal{F})|\leq(1+t)\frac{2n-4}{1+t}=2n-4<2n-2$, a contradiction.
Similarly, for $n-2\leq t\leq 2n-4$, $|V(\mathcal{F})|\leq 1+t\leq 2n-3<2n-2$,
a contradiction. Then we consider the cases $t=2n-3$, or $2\leq t\leq n-3$ and
$r\geq 2$. We find
$|V(\mathcal{F})|\leq(1+t)(2\lceil\frac{n-1}{1+t}\rceil-1)=1+t\leq 2n-2$ for
$t=2n-3$, and
$|V(\mathcal{F})|\leq(1+t)(2\lceil\frac{n-1}{1+t}\rceil-1)\leq(1+t)(2\frac{n-1+t}{1+t}-1)=2n-3+t\leq
3n-6$ for $2\leq t\leq n-3$ and $r\geq 2$. By Lemma 4.3,
$|V(\mathcal{F})|<\kappa_{1}(B_{n})$. Then $|V(C)|=1$, say $u=[v,w]$. Thus
$N_{B_{n}}(u)\subseteq V(\mathcal{F})$, which implies that
$B_{n}[N_{B_{n}}(u)]$ has a star $K_{1,2n-3}$ for $t=2n-3$, contradicting
Lemma 4.4. For $2\leq t\leq n-3$ and $r\geq 2$, $|\mathcal{F}|\leq
2\lceil\frac{n-1}{1+t}\rceil-1$. If all star-centers are in $N_{B_{n}}(u)$,
then $2\lceil\frac{n-1}{1+t}\rceil-1$ stars can not cover all vertices of
$N_{B_{n}}(u)$ by Lemma 4.4. Thus there exists a star whose center $x$ is not
in $N_{B_{n}}(u)\cup\\{u\\}$. We know that $x$ has at most two neighbors in
$N_{B_{n}}(u)$ since $[v,v^{i}]$ and $[v,v^{j}]$ ($[w,w^{i}]$ and $[w,w^{j}]$)
have no common neighbor in $V(B_{n})-N_{B_{n}}(u)-\\{u\\}$. Then
$V(\mathcal{F})\leq(1+t)\cdot 2\cdot\lfloor\frac{n-1}{1+t}\rfloor+2=(1+t)\cdot
2\cdot\frac{n-1-r}{1+t}+2=2n-2r<2n-2$ for $r\geq 2$. It is a contradiction. ∎

######  Lemma 4.7.

For $n\geq 4$ and $2\leq t\leq 2n-3$, let $r$ be remainder of $n-1$ divided by
$1+t$. Then

$\kappa(B_{n};K_{1,t})\leq\left\\{\begin{aligned}
&\frac{2n-4}{1+t}+1,~{}~{}if~{}2\leq t\leq n-3~{}and~{}r=1,\\\
&2\lceil\frac{n-1}{1+t}\rceil,~{}~{}otherwise.\end{aligned}\right.$

###### Proof.

Let $u=[v,w]$ be a vertex of $B_{n}$ with $v=00\ldots 00$ and $w=10\ldots 00$.
Then $N_{B_{n}}(u)=\\{[v,v^{i}],[w,w^{i}]|0\leq i\leq n-2\\}$.

For $n-2\leq t\leq 2n-3$, let $S_{1}$ ($S_{2}$) be a star with center
$[v,v^{0}]$ ($[w,w^{0}]$) and the leaves are neighbors of $[v,v^{0}]$
($[w,w^{0}]$). Precisely,

$\left\\{\begin{aligned} &S_{1}=\\{[v,v^{0}];[v,v^{i}],t_{j}|1\leq i\leq
n-2,n-1\leq j\leq t\\},\\\ &S_{2}=\\{[w,w^{0}];[w,w^{i}],t^{\prime}_{j}|1\leq
i\leq n-2,n-1\leq j\leq t\\},\\\ \end{aligned}\right.$

where $\\{t_{j}|n-1\leq j\leq t\\}\subseteq
N_{B_{n}}([v,v^{0}])\setminus\\{u,[v,v^{i}]|1\leq i\leq n-2\\}$ and
$\\{t^{\prime}_{j}|n-1\leq j\leq t\\}\subseteq
N_{B_{n}}([w,w^{0}])\setminus\\{u,[w,w^{i}]|1\leq i\leq n-2\\}$. Let
$\mathcal{F}=\\{S_{1},S_{2}\\}$. Since $N_{B_{n}}(u)\subseteq V(\mathcal{F})$
and $[11\ldots 11,11\ldots 10]\notin V(B_{n}-\mathcal{F})$,
$B_{n}-\mathcal{F}$ has two components. Then $u$ is a singleton and $[11\ldots
11,11\ldots 10]$ belongs to the other component.

For $2\leq t\leq n-3$ and $1\leq i\leq\lfloor\frac{n-1}{1+t}\rfloor$, we set
$S_{i}$ ($S^{\prime}_{i}$) as a star with center $[v,v^{(i-1)(t+1)}]$
($[w,w^{(i-1)(t+1)}]$) and the leaves are $[v,v^{(i-1)(t+1)+k}]$
($[w,w^{(i-1)(t+1)+k}]$) for each $1\leq k\leq t$. The more detailed
expressions are

$\left\\{\begin{aligned}
&S_{i}=\\{[v,v^{(i-1)(t+1)}];[v,v^{(i-1)(t+1)+k}]|1\leq k\leq t\\}\\\
~{}~{}&S^{\prime}_{i}=\\{[w,w^{(i-1)(t+1)}];[w,w^{(i-1)(t+1)+k}]|1\leq k\leq
t\\}~{}~{}\end{aligned}\right.$

If $r=1$, then we set
$S^{\prime\prime}=\\{[v^{n-2},w^{n-2}];[v,v^{n-2}],[w,w^{n-2}],t_{i}|1\leq
i\leq t-2\\}$ where $\\{t_{i}|1\leq i\leq t-2\\}\subseteq
N_{B_{n}}([v^{n-2},w^{n-2}])\setminus\\{[v,v^{n-2}],[w,w^{n-2}]\\}$. If $r\geq
2$, then we set

$\left\\{\begin{aligned}
&S^{\prime\prime}_{1}=\\{[v,v^{n-2}];[v,v^{i}],t_{j}|n-r-1\leq i\leq n-3,1\leq
j\leq t-r+1\\},\\\
&S^{\prime\prime}_{2}=\\{[w,w^{n-2}];[w,w^{i}],t^{\prime}_{j}|n-r-1\leq i\leq
n-3,1\leq j\leq t-r+1\\},\\\ \end{aligned}\right.$

where $\\{t_{j}|1\leq j\leq t-r\\}\subseteq
N_{B_{n}}([v,v^{n-2}])\setminus\\{u,[v,v^{i}]|0\leq i\leq n-3\\}$ and
$\\{t^{\prime}_{j}|1\leq j\leq t-r\\}\subseteq
N_{B_{n}}([w,w^{n-2}])\setminus\\{u,[w,w^{i}]|0\leq i\leq n-3\\}$. Let
$\mathcal{F}=\\{S_{i},S^{\prime}_{i}|1\leq
i\leq\lfloor\frac{n-1}{1+t}\rfloor\\}$ for $r=0$,
$\mathcal{F}=\\{S_{i},S^{\prime}_{i},S^{\prime\prime}|1\leq
i\leq\lfloor\frac{n-1}{1+t}\rfloor\\}$ for $r=1$ and
$\mathcal{F}=\\{S_{i},S^{\prime}_{i},S^{\prime\prime}_{1},S^{\prime\prime}_{2}|1\leq
i\leq\lfloor\frac{n-1}{1+t}\rfloor\\}$ for $r\geq 2$. We find
$N_{B_{n}}(u)\subseteq V(\mathcal{F})$ and $[11\ldots 11,11\ldots 10]\notin
V(B_{n}-\mathcal{F})$, which implies that $B_{n}-\mathcal{F}$ has two
components and $u$ is a singleton and $[11\ldots 11,11\ldots 10]$ belongs to
other component. ∎

By Lemmas 4.6 and 4.7, we have the following result.

######  Theorem 4.8.

For $n\geq 4$ and $2\leq t\leq 2n-3$, let $r$ be remainder of $n-1$ divided by
$1+t$. Then

$\kappa(B_{n};K_{1,t})=\kappa^{s}(B_{n};K_{1,t})=\left\\{\begin{aligned}
&\frac{2n-4}{1+t}+1,~{}~{}if~{}2\leq t\leq n-3~{}and~{}r=1,\\\
&2\lceil\frac{n-1}{1+t}\rceil,~{}~{}otherwise.\end{aligned}\right.$

######  Lemma 4.9.

For $n\geq 4$ and $4\leq k\leq 2n-1$, we have

$\kappa^{s}(B_{n};P_{k})\geq\left\\{\begin{aligned}
&\frac{2n-2}{k},~{}~{}if~{}4\leq k\leq n-1~{}and~{}k\mid n-1,\\\
&\lceil\frac{2n-1}{k}\rceil,~{}~{}otherwise.\\\ \end{aligned}\right.$

###### Proof.

Suppose $\kappa^{s}(B_{n};P_{k})\leq\frac{2n-2}{k}-1$ for $4\leq k\leq n-1$
and $k\mid n-1$, and $\kappa^{s}(B_{n};P_{k})\leq\lceil\frac{2n-1}{k}\rceil-1$
for otherwise. Then there exists a $P_{k}$-substructure cut $\mathcal{F}$. Let
$C$ be a smallest component of $B_{n}-\mathcal{F}$. Then
$|V(\mathcal{F})|\geq\kappa(B_{n})=2n-2$ by Lemma 4.2. For $4\leq k\leq n-1$
and $k\mid n-1$, $|V(\mathcal{F})|\leq k\cdot(\frac{2n-2}{k}-1)=2n-2-k<2n-2$,
a contradiction. Similarly, for $n\leq k\leq 2n-3$, $|V(\mathcal{F})|\leq
k\cdot(\lceil\frac{2n-1}{k}\rceil-1)=k\leq 2n-3<2n-2$, a contradiction.

We have $|V(C)|=1$, say $C=\\{u\\}$, for $k=2n-2$ or $4\leq k\leq n-1$ and
$k\nmid n-1$ since $|V(\mathcal{F})|\leq
k\cdot(\lceil\frac{2n-1}{k}\rceil-1)\leq
k(\frac{2n-1+k-1}{k}-1)=2n-2<\kappa_{1}(B_{n})$ by Lemma 4.3. Then
$N_{B_{n}}(u)\subseteq V(\mathcal{F})$, which implies that
$B_{n}[N_{B_{n}}(u)]$ has a hamiltonian path $P_{2n-2}$ and $\frac{2n-2}{k}$
vertex-disjoint $P_{k}$’s for $4\leq k\leq n-1$ and $k\nmid n-1$. It is
impossible by Lemma 4.4. ∎

######  Lemma 4.10.

For $n\geq 4$ and $4\leq k\leq 2n-1$, we have

$\kappa(B_{n};P_{k})\leq\left\\{\begin{aligned}
&\frac{2n-2}{k},~{}~{}if~{}4\leq k\leq n-1~{}and~{}k\mid n-1,\\\
&\lceil\frac{2n-1}{k}\rceil,~{}~{}otherwise.\\\ \end{aligned}\right.$

###### Proof.

Let $u=[v,w]$ be a vertex of $B_{n}$ with $v=00\ldots 00$ and $w=10\ldots 00$.
Then $N_{B_{n}}(u)=\\{[v,v^{i}],[w,w^{i}]|0\leq i\leq n-2\\}$. For
convenience, we set $P_{n-1}(w)=\langle[w,w^{0}],[w,w^{1}],\\\
\ldots,[w,w^{n-2}]\rangle$ as a path with $n-1$ vertices.

For $k=2n-1$, we set $\mathcal{F}=P_{2n-1}=\langle
P_{n-1}(v),[v^{n-2},w^{n-2}],P^{-1}_{n-1}(w)\rangle$. For $n\leq k\leq 2n-2$,
let $P^{1}_{2n-2}=\langle
P_{n-1}(v),P_{n-1}(v^{n-2})-[v,v^{n-2}]\cup[v^{n-2},v^{n-2,n-1}]\rangle$ and
$P^{2}_{2n-2}=\langle
P_{n-1}(w),P_{n-1}(w^{n-2})-[w,w^{n-2}]\cup[w^{n-2},w^{n-2,n-1}]\rangle$. Then
we set $\mathcal{F}=\\{P^{1}_{k},P^{2}_{k}\\}$, where $P^{1}_{k}$
($P^{2}_{k}$) along $P^{1}_{2n-2}$ ($P^{2}_{2n-2}$) with end-vertices
$[v,v^{0}]$ ($[w,w^{0}]$) and the $k$-th vertex of $P^{1}_{2n-2}$
($P^{2}_{2n-2}$).

For $4\leq k\leq n-1$ and $k\mid n-1$, we set $\mathcal{F}=\\{P^{i}_{k}|1\leq
i\leq\frac{2n-2}{k}\\}$, where $P^{1}_{k}$ along $P_{n-1}(v)$ with end-
vertices $[v,v^{0}]$ and $[v,v^{k-1}]$, $P^{2}_{k}$ along $P_{n-1}(v)$ with
end-vertices $[v,v^{k}]$ and $[v,v^{2k-1}]$, by the analogous,
$P^{\frac{n-1}{k}}_{k}$ along $P_{n-1}(v)$ with end-vertices $[v,v^{n-k-1}]$
and $[v,v^{n-2}]$. Similarly, we set $P^{\frac{n-1}{k}+1}_{k}$ along
$P_{n-1}(w)$ with end-vertices $[w,w^{0}]$ and $[w,w^{k-1}]$, by the
analogous, $P^{2\frac{n-1}{k}}_{k}$ along $P_{n-1}(v)$ with end-vertices
$[w,w^{n-k-1}]$ and $[w,w^{n-2}]$. For $4\leq k\leq n-1$ and $k\nmid n-1$, let
$P_{3n-2}=\langle
P_{2n-1},P_{n-1}(w^{0})-[w,w^{0}]\cup[w^{0},w^{0,n-1}]\rangle$ and
$\mathcal{F}=\\{P^{i}_{k}|1\leq i\leq\lceil\frac{2n-1}{k}\rceil\\}$, where
$P^{1}_{k}$ along $P_{3n-2}$ with end-vertices $[v,v^{0}]$ and $[v,v^{k-1}]$,
$P^{2}_{k}$ along $P_{3n-2}$ with end-vertices $[v,v^{k}]$ and $[v,v^{2k-1}]$,
by the analogous, $P^{\lceil\frac{2n-1}{k}\rceil}_{k}$ along $P_{3n-2}$ with
end-vertices are the $(k(\lceil\frac{2n-1}{k}\rceil-1)+1)$-th and
$k\lceil\frac{2n-1}{k}\rceil$-th vertices of $P_{3n-2}$.

We find $N_{B_{n}}(u)\subseteq V(\mathcal{F})$ and $[11\ldots 11,11\ldots
10]\notin V(B_{n}-\mathcal{F})$, which implies that $B_{n}-\mathcal{F}$ has
two components. Then $u$ is a singleton and $[11\ldots 11,11\ldots 10]$
belongs to other component. ∎

######  Theorem 4.11.

For $n\geq 4$ and $4\leq k\leq 2n-1$, we have

$\kappa(B_{n};P_{k})=\kappa^{s}(B_{n};P_{k})=\left\\{\begin{aligned}
&\frac{2n-2}{k},~{}~{}if~{}4\leq k\leq n-1~{}and~{}k\mid n-1,\\\
&\lceil\frac{2n-1}{k}\rceil,~{}~{}otherwise.\\\ \end{aligned}\right.$

We have $\kappa^{s}(B_{n};C_{k})\leq\kappa^{s}(B_{n};P_{k})$. By the similar
argument as Lemma 4.9, we obtain the following result.

######  Theorem 4.12.

For $n\geq 4$ and $4\leq k\leq 2n-1$, we have

$\kappa^{s}(B_{n};C_{k})=\left\\{\begin{aligned}
&\frac{2n-2}{k},~{}~{}if~{}4\leq k\leq n-1~{}and~{}k\mid n-1,\\\
&\lceil\frac{2n-1}{k}\rceil,~{}~{}otherwise.\\\ \end{aligned}\right.$

######  Lemma 4.13.

For $n\geq 5$ and $3\leq k\leq 2n$, let $r$ be remainder of $n-1$ divided by
$k$. Then

$\kappa(B_{n};C_{k})\geq\left\\{\begin{aligned}
&2\lceil\frac{n-1}{k}\rceil-1,~{}~{}if~{}3\leq k\leq n-1~{}and~{}1\leq
r\leq\lfloor\frac{k}{2}\rfloor-1,~{}or~{}k=2n,\\\ &3,~{}~{}if~{}k=n,\\\
&2\lceil\frac{n-1}{k}\rceil,~{}~{}otherwise.\\\ \end{aligned}\right.$

###### Proof.

Suppose to the contrary that $\kappa(B_{n};C_{k})\leq
2\lceil\frac{n-1}{k}\rceil-2$ for $3\leq k\leq n-1$ and $1\leq
r\leq\lfloor\frac{k}{2}\rfloor-1$, or $k=2n$, $\kappa(B_{n};C_{k})\leq 2$ for
$k=n$ and $\kappa(B_{n};C_{k})\leq 2\lceil\frac{n-1}{k}\rceil-1$ for
otherwise. Then there exists a $C_{k}$-structure cut $\mathcal{F}$. Let $C$ be
a smallest component. We have $|V(\mathcal{F})|\geq\kappa(B_{n})=2n-2$ by
Lemma 4.2. For $3\leq k\leq n-1$ and $1\leq r\leq\lfloor\frac{k}{2}\rfloor-1$,
or $k=2n$, $|V(\mathcal{F})|\leq k(2\lceil\frac{n-1}{k}\rceil-2)\leq
k(\frac{2(n+k-2)}{k}-2)=2n-4<2n-2$, a contradiction. We have a Similar
contradiction for $3\leq k\leq n-1$ and $r=0$ since $|V(\mathcal{F})|<2n-2$.

For $n\leq k\leq 2n-1$, it is easy to find $|V(\mathcal{F})|\leq 2n$. For
$3\leq k\leq n-1$ and $\lfloor\frac{k}{2}\rfloor\leq r\leq k-1$, we have

$\displaystyle|V(\mathcal{F})|\leq k\cdot(2\lceil\frac{n-1}{k}\rceil-1)\leq
k\cdot(2\frac{n-1+\lceil\frac{k}{2}\rceil}{k}-1)\leq
2(n-1+\frac{k+1}{2})-k=2n-1.$

Then $|V(\mathcal{F})|<\kappa_{1}(B_{n})$ for $n\geq 5$ by Lemma 4.3. Thus
$|V(C)|=1$, say $u=[v,w]$, which implies that $N_{B_{n}}(u)\subseteq
V(\mathcal{F})$ for $n\leq k\leq 2n-1$, or $3\leq k\leq n-1$ and
$\lfloor\frac{k}{2}\rfloor\leq r\leq k-1$. We find $|\mathcal{F}|\leq 1$ for
$n+1\leq k\leq 2n-1$, that is, a $C_{k}$ covers all vertices of
$N_{B_{n}}(u)$, contradicting Lemma 4.4. We find $|\mathcal{F}|\leq 2$ for
$n=k$, which implies that we need two $C_{n}$’s to cover all vertices of
$N_{B_{n}}(u)$. We know the longest cycle is $C_{n-1}$ in
$B_{n}[N_{B_{n}}(u)]$ by Lemma 4.4. Then a $C_{n}$ cover $n-1$ vertices of
$N_{B_{n}}(u)$ and these $n-1$ vertices are in a $K_{n-1}$. Let
$x=[x_{1},x_{2}]$ be a vertex of $C_{n}$ but $x\notin N_{B_{n}}(u)$. Then $x$
is adjacent to both $[v,v^{i}]$ and $[v,v^{j}]$ (or $[w,w^{i}]$ and
$[w,w^{j}]$) for $i,j\in[n]$. Thus $x_{1}=v^{i}$ (or $w^{i}$) and
$x_{2}=v^{j}$ (or $w^{j}$). It is a contradiction since $[v^{i},v^{j}]\notin
V(B_{n})$ and $[w^{i},w^{j}]\notin V(B_{n})$. For $3\leq k\leq n-1$ and
$\lfloor\frac{k}{2}\rfloor\leq r\leq k-1$, we have $2r\geq k-1$ and these $2r$
vertices induce two disjoint $P_{r}$’s. Then we know a $C_{k}$ can not cover
two disjoint $P_{r}$’s by Lemma 4.4, a contradiction. ∎

######  Lemma 4.14.

For $n\geq 5$ and $6\leq k\leq 2n$, let $r$ be remainder of $n-1$ divided by
$k$. Then

$\kappa(B_{n};C_{k})\leq\left\\{\begin{aligned}
&2\lceil\frac{n-1}{k}\rceil-1,~{}~{}if~{}6\leq k\leq n-1~{}and~{}1\leq
r\leq\lfloor\frac{k}{2}\rfloor-1,~{}or~{}k=2n,\\\ &3,~{}~{}if~{}k=n,\\\
&2\lceil\frac{n-1}{k}\rceil,~{}~{}otherwise.\\\ \end{aligned}\right.$

###### Proof.

Let $u=[v,w]$ be a vertex of $B_{n}$ with $v=00\ldots 00$ and $w=10\ldots 00$.
Then $N_{B_{n}}(u)=\\{[v,v^{i}],[w,w^{i}]|0\leq i\leq n-2\\}$. Let
$P_{n-1}(v)=\langle[v,v^{1}],[v,v^{0}],[v,v^{2}],[v,v^{3}],\ldots,[v,v^{n-2}]\rangle$
be a path with $n-1$ vertices.

For $k=2n$, we set

$\displaystyle\mathcal{F}=C_{k}=\langle[v^{1},w^{1}],P_{n-1}(v),[v^{n-2},w^{n-2}],P^{-1}_{n-1}(w)\rangle.$

For $n+1\leq k\leq 2n-1$, we set $\mathcal{F}=\\{C^{1}_{k},C^{2}_{k}\\}$ and

$\displaystyle C^{1}_{k}=\langle
P_{n-1}(v),[v^{n-2},v^{n-2,1}],[v^{n-2,1},v^{1}],t_{1},\ldots,t_{k-n-1}\rangle$

where $\\{t_{i}|1\leq i\leq k-n-1\\}\subseteq\\{[v^{1},v^{1,i}]|i=0,n-1$ and
$2\leq i\leq n-3\\}$,

$\displaystyle C^{2}_{k}=\langle
P_{n-1}(w),[w^{n-2},w^{n-2,1}],[w^{n-2,1},w^{1}],t_{1},\ldots,t_{k-n-1}\rangle$

where $\\{t_{i}|1\leq i\leq k-n-1\\}\subseteq\\{[w^{1},w^{1,i}]|i=0,n-1$ and
$2\leq i\leq n-3\\}$.

For $k=n$, we set $\mathcal{F}=\\{C^{1}_{k},C^{2}_{k},C^{3}_{k}\\}$ and

$\displaystyle C^{1}_{k}=\langle
P_{n-1}(v)-[v,v^{n-2}],[v^{n-3},v^{n-3,1}],[v^{n-3,1},v^{1}]\rangle;$
$\displaystyle C^{2}_{k}=\langle
P_{n-1}(w)-[w,w^{n-2}],[w^{n-3},w^{n-3,1}],[w^{n-3,1},w^{1}]\rangle;$
$\displaystyle
C^{3}_{k}=\langle[v,v^{n-2}],[v^{n-2},w^{n-2}],[w,w^{n-2}],[w,w^{1}],[v^{1},w^{1}],[v,v^{1}],t_{1},\ldots,t_{k-6}\rangle,$

where $\\{t_{i}|1\leq i\leq k-6\\}\subseteq\\{[v,v^{i}]|2\leq i\leq n-2\\}$.

For $6\leq k\leq n-1$ and $1\leq i\leq\lfloor\frac{n-1}{k}\rfloor$, we set

$\displaystyle
C^{i}_{k}=\langle[v,v^{(i-1)k}],[v,v^{(i-1)k+1}],\ldots,[v,v^{ik-1}]\rangle;$
$\displaystyle C^{\prime
i}_{k}=\langle[w,w^{(i-1)k}],[w,w^{(i-1)k+1}],\ldots,[w,w^{ik-1}]\rangle.$

If $r=0$, then we set $\mathcal{F}=\\{C^{i}_{k},C^{\prime i}_{k}|1\leq
i\leq\lfloor\frac{n-1}{k}\rfloor\\}$. If $1\leq
r\leq\lfloor\frac{k}{2}\rfloor-1$, then we set
$\mathcal{F}=\\{C^{\lceil\frac{n-1}{k}\rceil}_{k}\\}\cup\\{C^{i}_{k},C^{\prime
i}_{k}|1\leq i\leq\lfloor\frac{n-1}{k}\rfloor\\}$ and

$\displaystyle C^{\lceil\frac{n-1}{k}\rceil}_{k}$
$\displaystyle=\langle[w,w^{1}],[v^{1},w^{1}],[v,v^{1}],t_{1},\ldots,t_{k-2r-4},[v,v^{n-r-1}],[v,v^{n-r}],\ldots,[v,v^{n-2}],$
$\displaystyle[v^{n-2},w^{n-2}],[w,w^{n-2}],[w,w^{n-3}],\ldots,[w,w^{n-r-1}],[w,w^{1}]\rangle;$

where $\\{t_{i}|1\leq i\leq k-2r-4\\}\subseteq\\{[v,v^{i}]|2\leq i\leq
n-r-2\\}$. If $\lfloor\frac{k}{2}\rfloor\leq r<k-1$, then we set
$\mathcal{F}=\\{C^{i}_{k},C^{\prime i}_{k}|1\leq
i\leq\lceil\frac{n-1}{k}\rceil\\}$ and

$\displaystyle
C^{\lceil\frac{n-1}{k}\rceil}_{k}=\langle[v,v^{1}],[v,v^{n-r-1}],[v,v^{n-r}],\ldots,[v,v^{n-2}],t_{1},\ldots,t_{k-r-3},[v^{n-2},v^{n-2,1}],[v^{n-2,1},v^{1}]\rangle,$

where $\\{t_{i}|1\leq i\leq k-r-3\\}\subseteq\\{[v^{n-2},v^{n-2,i}]|0\leq
i\leq n-3\\}$,

$\displaystyle C^{\prime\lceil\frac{n-1}{k}\rceil}_{k}$
$\displaystyle=\langle[w,w^{1}],[w,w^{n-r-1}],[w,w^{n-r}],\ldots,[w,w^{n-2}],t_{1},\ldots,t_{k-r-3},[w^{n-2},w^{n-2,1}],$
$\displaystyle[w^{n-2,1},w^{1}]\rangle,$

where $\\{t_{i}|1\leq i\leq k-r-3\\}\subseteq\\{[w^{n-2},w^{n-2,i}]|1\leq
i\leq n-3\\}$. If $r=k-1$, then we set $\mathcal{F}=\\{C^{i}_{k},C^{\prime
i}_{k}|1\leq i\leq\lceil\frac{n-1}{k}\rceil\\}$ and

$\displaystyle
C^{\lceil\frac{n-1}{k}\rceil}_{k}=\langle[v,v^{0}],[v,v^{n-k}],[v,v^{n-k+1}],\ldots,[v,v^{n-2}]\rangle,$
$\displaystyle
C^{\prime\lceil\frac{n-1}{k}\rceil}_{k}=\langle[w,w^{0}],[w,w^{n-k}],[w,w^{n-k+1}],\ldots,[w,w^{n-2}]\rangle.$

We find $N_{B_{n}}(u)\subseteq V(\mathcal{F})$ and $[11\ldots 11,11\ldots
10]\notin V(B_{n}-\mathcal{F})$, which implies that $B_{n}-\mathcal{F}$ has
two components. Then $u$ is a singleton and $[11\ldots 11,11\ldots 10]$
belongs to the other component. ∎

By Lemmas 4.13 and 4.14, we have the following theorem.

######  Theorem 4.15.

For $n\geq 5$ and $6\leq k\leq 2n$, let $r$ be remainder of $n-1$ divided by
$k$. Then

$\kappa(B_{n};C_{k})=\left\\{\begin{aligned}
&2\lceil\frac{n-1}{k}\rceil-1,~{}~{}if~{}6\leq k\leq n-1~{}and~{}1\leq
r\leq\lfloor\frac{k}{2}\rfloor-1,~{}or~{}k=2n,\\\ &3,~{}~{}if~{}k=n,\\\
&2\lceil\frac{n-1}{k}\rceil,~{}~{}otherwise.\\\ \end{aligned}\right.$

##  5 Conclusion

In this paper, we obtained structure connectivities of two famous data center
networks DCell and BCDC on some common structures. For DCell network
$D_{m,n}$, $m\geq 0$ and $n\geq 2$, we got that
$\kappa(D_{m,n};K_{1,t})=\kappa^{s}(D_{m,n};K_{1,t})=\lceil\frac{n-1}{1+t}\rceil+m$
for $1\leq t\leq m+n-2$ and
$\kappa(D_{m,n};K_{s})=\lceil\frac{n-1}{s}\rceil+m$ for $3\leq s\leq n-1$ by
analyzing the structural properties of $D_{m,n}$. For BCDC network $B_{n}$,
$n\geq 5$, we used the existing results of $g$-extra connectivity to obtain
$\kappa(B_{n};K_{1,t})$ and $\kappa^{s}(B_{n};K_{1,t})$ for $1\leq t\leq 2n-3$
(see Theorems 4.5 and 4.8) and $\kappa(B_{n};P_{k})$ and
$\kappa^{s}(B_{n};P_{k})$ for $4\leq k\leq 2n-1$ (see Theorem 4.11);
$\kappa(B_{n};C_{k})$ and $\kappa^{s}(B_{n};C_{k})$ for $6\leq k\leq 2n$ (see
Theorem 4.15). It is easy to find that $\kappa(D_{m,n};P_{k})$
($\kappa^{s}(D_{m,n};P_{k})$) and $\kappa(D_{m,n};C_{k})$
($\kappa^{s}(D_{m,n};C_{k})$) have no relevant conclusions. Except for
$K_{1,t}$, $P_{k}$, $C_{k}$ and $K_{s}$, there are still other structure
connectivities of $D_{m,n}$ and $B_{n}$ have not been studied. So we will keep
working on structure connectivity of data center networks.

## Acknowledgement

The work is supported by NSFC (Grant No. 11871256).

## References

  * [1] S. Arnold, Google Version 2.0: The Calculating Predator, Infonortics Ltd. 2007.
  * [2] A. Carter, Do It Green: Media Interview with Michael Manos, 2007. http://edge.technet.com/Media/Doing-IT-Green/.
  * [3] A. Esfahanian, S. Hakimi, On computing a conditional edge-connectivity of a graph, Inf. Process. Lett. 27 (1988) 195-199.
  * [4] K. Efe, The crossed cube architecture for parallel computation, IEEE Trans. Parallel and Distributed Systems, 3(5) (1992) 513-524.
  * [5] J. Fàbrega, M.A. Fiod, On the extraconnectivity of graphs, Discrete Math. 155 (1-3) (1996) 49-57.
  * [6] W. Feng, S.Y. Wang, Structure connectivity and substructure connectivity of wheel networks, Theoret. Comput. Sci. 850 (2021) 20-29.
  * [7] C.X. Guo, H.T. Wu, K. Tan, L. Shi, Y.G. Zhang, S.W. Lu, DCell: A Scalable and Fault-Tolerant Network Structure for Data Centers, in Proc. SIGCOMM’08 (Seattle, WA, 2008), Vol. 38, pp. 75-86.
  * [8] C. Hao, W.H. Yang, The Generalization Connectivity of Data Center Networks, Parallel Process. Lett. 29 (2) (2019), No. 1950007, 9 pages.
  * [9] F. Harary, Conditional connectivity, Networks 13 (3) (1983) 347-357.
  * [10] T. Hoff, Google Architecture, 2007. http://highscalability.com/google-architecture.
  * [11] P.D. Kulasinghe, Connectivity of the crossed cube, Inf. Process. Lett. 61 (1997) 221-226.
  * [12] C.K. Lin, E. Cheng, L. Lipták, Structure and Substructure Connectivity of Hypercube-Like Networks, Parallel Process. Lett. 30 (3) (2020), No. 2040007, 23 pages.
  * [13] C.K. Lin, L.L. Zhang, J.X. Fan, D.J. Wang, Structure connectivity and substructure connectivity of hypercubes, Theoret. Comput. Sci. 634 (2016) 97-107.
  * [14] C.F. Li, S.W. Lin, S.J. Li, Structure connectivity and substructure connectivity of star graphs, Discrete Appl. Math. 284 (2020) 472-480.
  * [15] X.W. Li, S.M. Zhou, X.Y. Ren, X. Guo, Structure and substructure connectivity of alternating group graphs, Appl. Math. Comput. 391 (2021), No. 125639, 16 pages.
  * [16] X.Y. Li, J.X. Fan, C.K. Lin, B.L. Chen, X.H. Jia, The extra connectivity, extra conditional diagnosability and $t/k$-diagnosability of the data center network DCell, Theoret. Comput. Sci. 766 (2019) 16-29.
  * [17] M.J. Lv, B.L. Chen, J.X. Fan, X. Wang, J.Y. Zhou, J. Yu, The Conditional Reliability Evaluation of Data Center Network BCDC, Comput. J. (2020) https://doi.org/10.1093/comjnl/bxaa078.
  * [18] L. Rabbe, Powering the Yahoo! network, 2006. http://yodel.yahoo.com/2006/11/27/powering-the-yahoo-network/.
  * [19] X. Wang, J.X. Fan, C.K. Lin, J.Y. Zhou, Z. Liu, BCDC: A high-performance, server-centric data center network, J. Comput. Sci. Technol. 33(2) (2018) 400-416.
  * [20] X. Wang, J.X. Fan, J.Y. Zhou, C.K. Lin, The restricted $h$-connectivity of the data center network DCell, Discrete Appl. Math. 203 (2016) 144-157.