# Critical parameters of the synchronisation’s stability for coupled maps in
regular graphs

Juan Gancio and Nicolás Rubido  Universidad de la República, Instituto de
Física de Facultad de Ciencias, Iguá 4225, Montevideo 11400, Uruguay.
University of Aberdeen, King’s College, Institute for Complex Systems and
Mathematical Biology, AB24 3UE Aberdeen, United Kingdom.

###### Abstract

Coupled Map Lattice (CML) models are particularly suitable to study spatially
extended behaviours, such as wave-like patterns, spatio-temporal chaos, and
synchronisation. Complete synchronisation in CMLs emerges when all maps have
their state variables with equal magnitude, forming a spatially-uniform
pattern that evolves in time. Here, we derive critical values for the
parameters – coupling strength, maximum Lyapunov exponent, and link density –
that control the synchronisation-manifold’s linear stability of diffusively-
coupled, identical, chaotic maps in generic regular graphs (i.e., graphs with
uniform node degrees) and class-specific cyclic graphs (i.e., periodic
lattices with cyclical node permutation symmetries). Our derivations are based
on the Laplacian matrix eigenvalues, where we give closed-form expressions for
the smallest non-zero eigenvalue and largest eigenvalue of regular graphs and
show that these graphs can be classified into two sets according to a
topological condition (derived from the stability analysis). We also make
derivations for two classes of cyclic graph: $k$-cycles (i.e., regular
lattices of even degree $k$, which can be embedded in $T^{k}$ tori) and
$k$-Möbius ladders, which we introduce here to generalise the Möbius ladder of
degree $k=3$. Our results highlight differences in the synchronisation
manifold’s stability of these graphs – even for identical node degrees – in
the finite size and infinite size limit.

Coupled Maps, Cyclic Graphs, Synchronisation

## Introduction

Coupled Map Lattices (CMLs) were introduced as suitable models to study the
behaviour of spatially extended dynamical systems Kaneko_1984 . These systems
are defined on a discrete space-time, but with state variables that can take
continuous values. Their behaviours range from ordered wave-like patterns to
spatio-temporal chaos (i.e., turbulence) Kaneko_1989 ; Amritkar_1993 ;
Gallas_2004 ; Lakshmanan_2005 . CMLs have also been generalised to include
non-local interactions Kaneko_1990 , either by using distance-dependent
functions Viana_2003 ; Batista_2005 ; Rubido_2011  or by replacing the lattice
regularity with complex graphs Strogatz_1998 ; Sync_SW_barahona_pecora ;
Strogatz_2006 ; Boccaletti_2005 , and delayed interactions Masoller_2005 ;
Masoller_2006 ; Masoller_2009 . Overall, CMLs (and their generalisations) have
allowed to deepen our understanding of complex behaviours, such as
intermittence Kaneko_1985 ; Hilda_1996 , chimera states Omelchenko_2011 ;
Scholl_2012 ; Baptista_2020 , and synchronisation Boccaletti_1998 ; Gade_2000
; Jost_2001 ; Boccaletti_2002 .

Complete synchronisation (CS) is one of these collective behaviours emerging
in many natural systems and with broad real-world applications, such as the
design of stable power-grids Dorfler_2013 ; Nardelli_2014 ; Motter_2015 . For
CMLs, CS implies having all maps evolving such that their state variables have
identical values at any time; that is, a spatially-uniform pattern. The
evolution and stability of this pattern can be analysed, for example, by means
of Lyapunov exponents Kaneko_1986 ; Viana_2007 , which are related to the
Kaplan-Yorke dimension Yorke_1979 ; Yorke_1983  and Kolmogorov-Sinai Entropy
Kolmogorov_1958 ; Sinai_1959 ; Viana_2002  of the system. Research on
synchronisation generally focuses on understanding which dynamical properties
and topological characteristics favour – or hinder – the emergence of CS.

A major breakthrough in synchronisation research was achieved by Pecora and
Carroll MSF_pecora , whose seminal work defined the Master Stability Function
(MSF): a functional analysis of the synchronisation manifold’s stability for
generic graphs of diffusively-coupled, identical, (time-continuous or
discrete) dynamical systems. The MSF allows to decouple the dynamical
properties of the dynamical units composing the coupled system with its
topological properties (similar to the work by Fujisaka and Yamada
Fujisaka_MSF ). In spite of the MSF breakthrough, and because of the broad
range of dynamics and graphs that can be analysed, there are still plenty of
open-questions that can aid in the design of stable synchronous systems and
continue increasing our understanding of this fascinating collective
phenomenon.

Here, we derive closed-form expressions for the minimum coupling strength and
link density necessary to have a stable synchronisation – as well as an upper
limit to the chaoticity that can be synchronisable – of diffusively-coupled,
identical maps, in generic regular graphs and class-specific cyclic graphs.
Cyclic graphs are lattices having cyclical node-permutation symmetry (implying
periodic boundary conditions and identical node neighbourhoods). In
particular, we make derivations for $k$-cycles (also known as Wiley-Strogatz-
Girvan networks Strogatz_2006 ) and $k$-Möbius ladders (non-planar graphs),
which we introduce in this work to extend the classic Möbius ladder with
degree $3$ mob_lad_org ; mob_lad  to higher degrees. Our finite-size results
show striking differences between these $2$ cyclic graphs, only becoming
similar when converging to the complete (all-to-all) graph. Moreover, we show
that our expressions can change for different degrees and in the thermodynamic
limit (i.e., infinite system size). Our derivations are based on the MSF
MSF_pecora  and the graph’s Laplacian eigenvalues (focusing on the smallest
non-zero and largest eigenvalue), making our approach general. Overall, our
work complements the general understanding of synchronisation phenomena in
CMLs and provides detailed mathematical derivations leading to exact
analytical results.

## Methods and Model

### Coupled Map Lattices and the Master Stability Function

Let $N$ one-dimensional maps, $f_{i}:D\subset\mathbb{R}\to D$, where
$i=1,\ldots,N$ (corresponding to possibly different parameters), be
diffusively coupled in a symmetric graph Kaneko_1984 ,

$x_{t+1}^{(i)}=f_{i}\\!\left(x_{t}^{(i)}\right)-\frac{\epsilon}{k_{i}}\sum_{j=1}^{N}L_{ij}\,f_{j}\\!\left(x_{t}^{(j)}\right),$
(1)

where $0\leq\epsilon\leq 1$ is the coupling strength and $L_{ij}$ is $ij$-th
element of the graph’s Laplacian matrix. $\mathbf{L}=\mathbf{K}-\mathbf{A}$,
where $\mathbf{A}$ is the graph’s adjacency matrix ($A_{ij}=1=A_{ji}$ if there
is a link between nodes $i$ and $j$, and $A_{ij}=0$ otherwise) and
$k_{i}=\sum_{j=1}^{N}A_{ij}$ is the $i$-th degree (number of neighbours).
Equation (1) describes an $N$-dimensional mapping, that transforms the state
of the $N$ maps at instant $t$,
$\vec{x}_{t}=\\{x_{t}^{(1)},\dots,x_{t}^{(N)}\\}$, to the state,
$\vec{x}_{t+1}=\\{x_{t+1}^{(1)},\dots,x_{t+1}^{(N)}\\}$. This mapping can be
written in matrix form as

$\vec{x}_{t+1}=\left[\mathbf{I}-\epsilon\,\mathbf{K}^{-1}\,\mathbf{L}\right]\,\vec{f}\\!\left(\vec{x}_{t}\right),$
(2)

where
$\vec{f}\\!\left(\vec{x}_{t}\right)=\\{f_{1}(x_{t}^{(1)}),\ldots,f_{N}(x_{t}^{(N)})\\}$
represents the mapping of each of the $N$ maps at time $t$, $\mathbf{I}$ is
the $N\times N$ identity matrix, and
$\mathbf{K}^{-1}=\textnormal{diag}\\{1/k_{1},\ldots,1/k_{N}\\}$.

When the coupled system is composed of identical mappings,
$f_{i}=f\;\forall\,i$, $s_{t}=x_{t}^{(1)}=\dots=x_{t}^{(N)}$ is a solution of
Eq. (2) because of the zero-row-sum property of $\mathbf{L}$ (i.e.,
$\sum_{j}L_{ij}=0\;\forall\,i$). This solution defines the complete
synchronisation (CS) manifold, whose linear stability is determined by the
Master Stability Function (MSF) MSF_pecora . Specifically, the stability is
quantified by the Lyapunov exponents transverse to the synchronisation
manifold, which are known as Conditional Lyapunov Exponents (CLE), $\chi$,
because their validity is restricted to the diagonal of the $N$-dimensional
state-space.

In terms of the MSF, the system is able to synchronise if the transverse CLEs
are negative; meaning that perturbations to the manifold decay exponentially
fast and the manifold is linearly stable. This situation is generally possible
if $\frac{\alpha_{2}}{\alpha_{1}}=\beta>\frac{\lambda_{M}}{\lambda_{F}}$,
where $\lambda_{F}$ is the Fiedler’s eigenvalue of $\mathbf{L}$ (i.e., the
first non-zero eigenvalue), $\lambda_{M}$ is its largest eigenvalue, and
$\alpha_{1}$ and $\alpha_{2}$ are the limits defining the negative range of
CLEs Sync_SW_barahona_pecora , which depend on the system’s dynamical
characteristics and coupling strength.

In particular, the MSF is obtained by perturbing the synchronous state and
analysing the perturbation’s evolution up to the leading order. In Eq. (2),
such perturbation, $x_{t}^{(i)}=s_{t}+\xi_{t}^{(i)}$, up to the first order in
$\xi_{t}^{(i)}$, holds

$\vec{\xi}_{t+1}=\left[\mathbf{I}-\epsilon\,\mathbf{K}^{-1}\,\mathbf{L}\right]\mathbf{J}_{\\!\vec{f}}(s_{t})\,\vec{\xi}_{t},$

where $\mathbf{J}_{\\!\vec{f}}(s_{t})$ represent the Jacobian matrix of
$\vec{f}$ evaluated in the synchronous state $s_{t}$. In our case,
$\mathbf{J}$ is a diagonal matrix – even for non-synchronous solutions.
Specifically,
$\mathbf{J}_{\vec{f}}(\vec{x}_{t})=\textnormal{diag}\\{\partial_{1}f_{1}(x_{t}^{(1)}),\ldots,\partial_{N}f_{N}(x_{t}^{(N)})\\}$,
with $\partial_{i}f_{i}=d\,f_{i}/d\,x^{(i)}$ being the derivatives of the
flow-vector components with respect to each independent variable. Thus, when
$f_{i}=f\;\forall\,i$, the synchronisation manifold Jacobian matrix is given
by $\mathbf{J}_{\vec{f}}(s_{t})=f^{\prime}(s_{t})\,\mathbf{I}$, which lead to

$\vec{\xi}_{t+1}=f^{\prime}(s_{t})\left[\mathbf{I}-\epsilon\,\mathbf{K}^{-1}\,\mathbf{L}\right]\,\vec{\xi}_{t}.$
(3)

This is a linear mapping done by a constant matrix,
$\mathbf{I}-\epsilon\,\mathbf{K}^{-1}\,\mathbf{L}$, to the perturbations at
time $t$, $\vec{\xi}_{t}$, modulated by the map’s derivative at the
synchronisation manifold, $f^{\prime}(s_{t})$.

### Synchronisation Stability in Regular and Cyclic Graphs

We restrict our analysis of Eq. (3) to coupled-maps in regular graphs, such
that $\mathbf{K}^{-1}=\frac{1}{k}\mathbf{I}$, which commutes with any matrix.
We note that for symmetric graphs, $\mathbf{L}$ is Hermitian, meaning that it
can be diagonalised and that it holds real eigenvalues. Thus, we write
$\mathbf{L}=\mathbf{P}\mathbf{\Lambda}\mathbf{P}^{-1}$, where
$\mathbf{\Lambda}=\textnormal{diag}\\{\lambda_{0},\ldots,\lambda_{N-1}\\}$ is
the ordered eigenvalue spectra (with
$\lambda_{0}=0<\lambda_{1}\leq\cdots\leq\lambda_{N-1}$) and
$\mathbf{P}=\\{\vec{\psi}_{0},\ldots,\vec{\psi}_{N-1}\\}$ holds their
respective orthonormal (column) eigenvectors, such that
$\mathbf{L}\,\vec{\psi}_{n}=\lambda_{n}\,\vec{\psi}_{n}\;\forall\,n$.
Consequently, changing variables in Eq. (3) to
$\vec{\zeta}_{t}=\mathbf{P}^{-1}\vec{\xi}_{t}$, the perturbations to the
synchronisation state become decoupled in the eigenmodes ($n=0,1,\ldots,N-1$)
according to

$\zeta^{(n)}_{t+1}=\left(1-\epsilon\,\frac{\lambda_{n}}{k}\right)f^{\prime}(s_{t})\,\zeta^{(n)}_{t}.$
(4)

Equation (4) gives the system’s CLEs, $\\{\chi_{n}\\}_{n=0}^{N-1}$ when
iterated; that is Hilda_1996 ; Viana_2003 ; Jost_2001 ,
$\chi_{n}=\log\left|1-\epsilon\,\frac{\lambda_{n}}{k}\right|+\lim\limits_{T\to\infty}\sum_{t=1}^{T}\frac{\log\left|f^{\prime}(x_{t})\right|}{T}=\chi_{top}(\epsilon\lambda_{n}/k)+\chi_{dyn}$,
where $\chi_{0}=\chi_{dyn}$ (because $\lambda_{0}=0$ always) is the exponent
parallel to the synchronisation manifold, i.e., the isolated map’s (constant)
Lyapunov exponent, and the remaining $N-1$ exponents determine the stability
of the manifold (transversal directions), being stable if $\chi_{n}<0$
$\forall\,n>0$. This means that a stable manifold necessary has transversal
modes fulfilling

$\chi_{top}(\epsilon\lambda_{n}/k)=\log\left|1-\epsilon\,\frac{\lambda_{n}}{k}\right|<-\chi_{dyn},\;\forall\,n>0.$
(5)

We note that when $\chi_{dyn}\leq 0$, Eq. (5) is always satisfied, meaning
that periodic dynamics have linearly-stable synchronisations. On the other
hand, when the map is sufficiently chaotic, $\chi_{dyn}\gg 0$, the negative
well of the MSF can be narrowed down to the point of disappearing. Hence, the
system’s ability to synchronise depends on the competition between the map’s
chaoticity and the network’s topology, which we explore in detail in this work
focusing on chaotic maps, i.e., $\chi_{dyn}>0$.

Cyclic graphs are a particular class of regular graphs: they preserve their
topology when transformed by a group of symmetries which cyclically takes any
one node and maps it into another. Namely, a cyclic permutation is such that
$\pi[\\{1,2,\ldots,N-1,N\\}]=\\{2,\ldots,N-1,N,1\\}$ (hence,
$\pi\circ\pi\circ\cdots\circ\pi=\pi^{N}=\mathbf{I}$), and cyclic graphs are
graphs that preserve their local and global topological properties under
groups of permutations, $\\{\pi,\pi^{2},\ldots,\pi^{N}\\}$. This implies that
cyclic graphs contain all their connectivity information in any given row of
$\mathbf{L}$ (or $\mathbf{A}$) and have analytical expressions for their
eigenvalues and eigenvectors based on a Fourier basis CGraphs ; GraphSpectra ;
FanChung . Hence, we will focus on the first row of $\mathbf{L}$,
$\\{L_{1,j}\\}_{j=1}^{N}=\\{k,\,-A_{1,2},\dots,-A_{1,N}\\}$, and the
eigenvalues can be expressed in terms of $\\{L_{1,j}\\}$ as

$\lambda_{n}=\sum_{j=1}^{N}L_{1,j}\cos\\!\left[\frac{2\pi
n}{N}(j-1)\right]=k-\sum_{j=2}^{N}A_{1,j}\cos\\!\left[\frac{2\pi
n}{N}(j-1)\right].$ (6)

We note that from Eq. (6) the eigenvalue-magnitudes are symmetric due to the
cosine function, implying that $\lambda_{n}=\lambda_{N-n+1}\;\forall\,n>0$ and
$\lambda_{0}=0$ for any cyclic graph. This implies that almost every
eigenvalue is (at least) doubly degenerate, except for $\lambda_{0}=0$. Also,
we note that the smallest non-zero eigenvalue, $\lambda_{F}$ (known as Fiedler
eigenvalue Fiedler_1973  or algebraic connectivity), or the maximum
eigenvalue, $\lambda_{M}$, of a given cyclic graph, can be different than
$\lambda_{1}$ or $\lambda_{N/2}$ from Eq. (6), respectively.

## Results

We analyse diffusively-coupled, identical, chaotic maps in generic – and
specific – regular graphs to find the necessary conditions to have a linearly
stable synchronisation manifold. Our main contributions are the derivation of
critical parameters, including eigenvalue magnitudes, minimum coupling
strengths, map’s maximum Lyapunov exponent (i.e., maximum synchronisable
chaoticity), and link-density. In particular, we derive closed-form
expressions for these critical parameters in $2$ specific classes of cyclic
graphs for the finite and infinite size limits: $k$-cycles – ring-like graphs
connecting an even number of $k$ neighbours – and $k$-Möbius ladders – which
we introduce to generalise the Möbius ladder (of degree $k=3$) to $3\leq k\leq
N-1$.

### Synchronisation-Manifold’s Stability for Generic Regular Graphs

The stability condition set by Eq. (5) depends on the map’s Lyapunov exponent,
$\chi_{dyn}$, Laplacian matrix’s eigenvalues, $\\{\lambda_{n}\\}_{n=1}^{N-1}$,
graph’s degree, $k$, and coupling strength, $\epsilon$. Laplacian eigenvalues
are such that
$\\{\lambda_{n}\\}_{n=0}^{N-1}=\\{\lambda_{0}=0<\lambda_{F}\leq\cdots\leq\lambda_{M}\\}$,
where $\lambda_{F}$ is the Fiedler eigenvalue Fiedler_1973 , i.e., smallest
non-zero eigenvalue (also known as algebraic connectivity), and $\lambda_{M}$
is the largest eigenvalue. These $2$ are the relevant eigenvalues to analyse
the synchronisation-manifold’s stability MSF_pecora . Hence, we rewrite the
condition set by Eq. (5) in terms of bounds to $\lambda_{F}$ and $\lambda_{M}$
Jost_2001  by

$\mathcal{S}_{F}(\chi_{dyn},\,\epsilon)<\frac{\lambda_{F}}{k}\leq\frac{\lambda_{M}}{k}<\mathcal{S}_{M}(\chi_{dyn},\,\epsilon),$
(7)

where
$\mathcal{S}_{F}(\chi_{dyn},\,\epsilon)\equiv[1-\exp(\chi_{dyn})]/\epsilon$
and
$\mathcal{S}_{M}(\chi_{dyn},\,\epsilon)\equiv[1+\exp(\chi_{dyn})]/\epsilon$
define $2$ non-intersecting surfaces, with
$\mathcal{S}_{M}(\chi_{dyn},\,\epsilon)>1,\;\forall\,\chi_{dyn}>0$ and
$\epsilon\in(0,\,1]$. The inequalities in Eq. (7) determine a lower and an
upper bound for $\lambda_{F}/k$ and $\lambda_{M}/k$ as a function of
$\epsilon$ and $\chi_{dyn}$, such that when fulfilled, all transversal
directions to the synchronisation manifold are attractive and the system has a
linearly stable synchronisation.

We note that, from the Gershgorin’s Circle theorem Gershgorin_1931 , all
Laplacian eigenvalues are bounded to the interval $[0,\,2k_{M}]$, where
$k_{M}=\max\\{k_{i}\\}_{i=1}^{N}$. For regular graphs, this implies that
$\lambda_{n}/k\in(0,\,2]\;\forall\,n>0$, meaning that Eq. (7) restricts the
interval $[\lambda_{F},\lambda_{M}]\subset(0,2]$ between the surfaces –
stability is lost whenever this eigenvalue interval intersects a surface. In
what follows, we use Eq. (7) to determine the critical parameter values where
stability is lost in one or more transversal directions when changing
$\epsilon$, $\chi_{dyn}$, or the regular graph’s properties, such as its
cyclic symmetry, size $N$, or degree $k$.

Figure 1:  Stability criteria for the synchronisation of identical, chaotic
maps, coupled diffusively in generic regular graphs. Linearly stable
synchronisation happens as long as the graph’s normalised minimum non-zero and
maximum Laplacian eigenvalues, $\lambda_{F}/k$ and $\lambda_{M}/k$ (vertical
interval at the $\epsilon=1$ plane), fit between $\mathcal{S}_{F}$ (bottom)
and $\mathcal{S}_{M}$ (top) surfaces. The minimum coupling strength needed to
synchronise the maps, $\epsilon^{(c)}$, is defined by the intersection of
$\lambda_{F}/k$ with $\mathcal{S}_{F}$ and depends on the map’s Lyapunov
exponent, $\chi_{dyn}$ (continuous curve in both panels). As $\epsilon$
increases, $\lambda_{M}/k$ can intersect $\mathcal{S}_{M}$ (dashed curve in
left panel), defining a maximum Lyapunov exponent, $\chi_{dyn}^{max}$ (filled
symbols), where the synchronisation manifold then looses stability if
$\chi_{dyn}$ or $\epsilon$ are increased.

The $2$ bounding surfaces in Eq. (7) –
$\mathcal{S}_{F}(\chi_{dyn},\,\epsilon)$ and
$\mathcal{S}_{M}(\chi_{dyn},\,\epsilon)$ – create $2$ scenarios depending on
the regular graph’s $\lambda_{F}/k$ and $\lambda_{M}/k$ possibility to
intersect the surfaces as $\epsilon$ or $\chi_{dyn}$ change, which we
illustrate in Fig. 1. A critical curve is defined in the lower bounding
surface at the height where $\lambda_{F}/k$ intersects
$\mathcal{S}_{F}(\chi_{dyn},\,\epsilon)$. Similarly, a critical curve for the
upper bounding surface is defined at the intersection of $\lambda_{M}/k$ with
$\mathcal{S}_{M}(\chi_{dyn},\,\epsilon)$.

The case shown on the left panel in Fig. 1 corresponds to regular graphs where
the critical curves share a common crossing
$(\epsilon^{(c)},\,\chi_{dyn}^{max})$ at $\epsilon^{(c)}\in(0,\,1]$;
highlighted by filled symbols in the panel. This crossing happens when
$[1-\exp(\chi_{dyn}^{max})]/(\lambda_{F}/k)=\epsilon^{(c)}=[1+\exp(\chi_{dyn}^{max})]/(\lambda_{M}/k)$,
where a $\chi_{dyn}>\chi_{dyn}^{max}$ or $\epsilon>\epsilon^{(c)}$
destabilises synchronisation. This crossing allows us to derive the _maximum
chaoticity that can be stably synchronised_ in these cyclic graphs,

$\chi_{dyn}^{max}\equiv-\log\left[\frac{1-(\lambda_{F}/\lambda_{M})}{1+(\lambda_{F}/\lambda_{M})}\right]=2\tanh^{-1}\left(\frac{\lambda_{F}}{\lambda_{M}}\right).$
(8)

It is worth noting that this upper limit for the Lyapunov exponent,
$\chi_{dyn}^{max}$, is sometimes missed in synchronisation research.

The case shown on the right panel in Fig. 1 corresponds to regular graphs
where the crossing is absent (happens outside the $\epsilon\in[0,\,1]$ range).
In this case, as $\epsilon$ is increased from $0$ to $1$ and $\chi_{dyn}$ is
increased according to the lower bounding surface critical curve,
$[1-\exp(\chi_{dyn}^{F})]/\epsilon_{F}=\lambda_{F}/k$, the upper bounding
surface is not crossed by $\lambda_{M}$. Consequently, the _maximum chaoticity
that can be stably synchronised_ is

$\chi_{dyn}^{max}\equiv\chi_{dyn}^{F}=-\log\left[1-\frac{\lambda_{F}}{k}\right],$
(9)

which is highlighted by a filled circle in the right panel at the $\epsilon=1$
plane.

We can now define a _set of critical regular graphs dividing these $2$ classes
of regular graphs_. We do this by matching Eqs. (8) and (9) to find a
relationship between $\lambda_{F}/k$ and $\lambda_{M}/k$; that is,
$(1-\lambda_{F}^{(c)}/\lambda_{M}^{(c)})/(1+\lambda_{F}^{(c)}/\lambda_{M}^{(c)})=(1-\lambda_{F}^{(c)}/k)$,

$\frac{\lambda_{F}^{(c)}}{k}+\frac{\lambda_{M}^{(c)}}{k}=2.$ (10)

This general distinction shows that the left panel in Fig. 1 corresponds to
regular graphs that hold $\lambda_{F}/k+\lambda_{M}/k>2$ [and stability
follows Eq. (8)] and the right panel in Fig. 1 corresponds to regular graphs
that hold $\lambda_{F}/k+\lambda_{F}/k<2$ [and stability follows Eq. (9)]. The
critical set of regular graphs – those fulfilling Eq. (10) – can be analysed
by either Eq. (8) or (9).

We note that for any graph, $\lambda_{F}/k\in(0,\,N/(N-1)]$ and
$\lambda_{M}/k\in[N/(N-1),\,2]$ Hahn_1997 ; Das_2012 . This means that
$N/(N-1)<\lambda_{F}/k+\lambda_{M}/k\leq N/(N-1)+2=(3N-1)/(N-1)$ always. For
example, a complete graph, $\mathcal{C}_{N}(k=N-1)$ (i.e., a cyclic graph with
$k=N-1$ defining an all-to-all coupling) has
$\lambda_{F}/k=\lambda_{M}/k=N/(N-1)$, hence,
$\lambda_{F}/k+\lambda_{M}/k=2N/(N-1)>2$. This means that complete graphs
belong to the case from our left panel in Fig. 1, and according to Eq. (8),
$\chi_{dyn}^{max}[\mathcal{C}_{N}(k=N-1)]=\infty$, which means that they can
stably synchronise any chaotic map.

In both classes of regular graphs, the _minimum coupling strengths needed to
maintain a linearly stable synchronisation_ for different Lyapunov exponents,
is given by the critical curve
$\mathcal{S}_{F}(\epsilon^{(c)},\chi_{dyn})=[1-\exp(\chi_{dyn})]/\epsilon^{(c)}=\lambda_{F}/k$,
and is valid up to $\chi_{dyn}^{max}$ – depending on the regular graph, either
from Eq. (8) or Eq. (9). Namely,

$\epsilon^{(c)}=\left[1-\exp(-\chi_{dyn})\right]\left(\frac{\lambda_{F}}{k}\right)^{-1}\;\forall\,\chi_{dyn}\in(0,\,\chi_{dyn}^{max}].$
(11)

This curve is shown in both panels of Fig. 1 by a thick continuous line.

### Synchronisation-Manifold’s Stability for Specific Cyclic Graphs

In what follows, we derive closed-form expressions for the critical points of
the synchronisation-manifold’s stability [Eqs. (8)-(11)] in $2$ specific
cyclic graphs, including their critical link densities, $\rho_{c}=k/(N-1)$. We
focus on $k$-cycle graphs, $\mathcal{C}_{N}(k)$, and $k$-Möbius ladders,
$\mathcal{M}_{N}(k)$. $\mathcal{C}_{N}(k)$ are cyclic graphs with even degrees
where connections span $k$ neighbours per node in ring-like structure (also
known as Wiley-Strogatz-Girvan networks Strogatz_2006 ). $\mathcal{M}_{N}(k)$
are our generalisation of the Möbius ladder mob_lad_org ; mob_lad , which has
$k=3$. We introduce $\mathcal{M}_{N}(k)$ graphs to increase the degree to
$3\leq k\leq N-1$, but keeping their overall ladder-like topology. Our
derivations for $\mathcal{C}_{N}(k)$ and $\mathcal{M}_{N}(k)$ include finite
size critical points and thermodynamic limits.

#### Results for $k$-cycles.

These graphs have degrees $k=2q$, with $q\in\mathbb{N}>0$, and can be
represented by a Laplacian matrix, $\mathbf{L}[\mathcal{C}_{N}(k=2q)]$, whose
first row is given by

$L_{1j}=\left\\{\begin{array}[]{ll}k&\textnormal{if}\;\;j=1,\\\
-1&\textnormal{if}\;\;j=2,\dots,\frac{k}{2}+1,\\\
-1&\textnormal{if}\;\;j=N,\dots,N-(\frac{k}{2}-1),\\\
0&\textnormal{otherwise}.\end{array}\right.$ (12)

Figure 2: $10$-node $k$-cycle graphs with normalised Laplacian eigenvalues.
From left to right, top panels show a $2$-cycle ($k=2$), a $4$-cycle ($k=4$),
and a $6$-cycle graph ($k=6$), where a node’s neighbourhood is highlighted by
thick lines. Bottom panels show the respective normalised Laplacian
eigenvalues, where the minimum non-zero (Fiedler) and maximum eigenvalues are
highlighted by stars and circles, respectively.

Because of the cyclic property and the cosine symmetry in Eq. (6), we find
that the eigenvalues for $\mathcal{C}_{N}(k)$ (see Appendix: $k$-cycles) are
given by

$\lambda_{n}[\mathcal{C}_{N}(k)]=k-2\sum_{s=1}^{k/2}\cos\left(\frac{2\pi
n}{N}s\right)=k+1-\left[\frac{\sin\left(\frac{n\,\pi(k+1)}{N}\right)}{\sin\left(\frac{n\,\pi}{N}\right)}\right]\\!.$
(13)

Equation (13) is valid for $n=0,\ldots,N-1$, since it can be shown by
trigonometric identities that $\sin\left[\pi n(k+1)/N\right]/\sin\left(\pi
n/N\right)=k+1$ when $n=0$. For example, Fig. 2 shows three examples of
$k$-cycles and their respective eigenvalue spectra – from left to right,
$\mathcal{C}_{10}(2)$, $\mathcal{C}_{10}(4)$, and $\mathcal{C}_{10}(6)$ –
where we highlight (by stars) that the first non-zero eigenvalues is doubly
degenerated.

In order to find the critical points for the local stability of the
synchronisation manifold, we need the smallest and largest eigenvalues from
Eq. (13), $\lambda_{F}$ and $\lambda_{M}$, respectively. For any degree
$k=2q$, we find that (see Eqs. (35) and (36) in Appendix: $k$-cycles) these
eigenvalues correspond to

$\displaystyle\lambda_{F}[\mathcal{C}_{N}(k)]=\min_{n>0}\\{\lambda_{n}\\}=\lambda_{1}=k+1-\frac{\sin\left(\pi(k+1)/N\right)}{\sin\left(\pi/N\right)},$
(14)
$\displaystyle\lambda_{M}[\mathcal{C}_{N}(k)]=\max_{n>0}\\{\lambda_{n}\\}=\max\\{\lambda_{\lfloor
3N/2(k+1)\rfloor},\,\lambda_{\lceil 3N/2(k+1)\rceil}\\}=k+1-$
$\displaystyle\min\left\\{\frac{\sin\left(\lfloor\frac{3N}{2(k+1)}\rfloor\frac{\pi(k+1)}{N}\right)}{\sin\left(\lfloor\frac{3N}{2(k+1)}\rfloor\frac{\pi}{N}\right)},\,\frac{\sin\left(\lceil\frac{3N}{2(k+1)}\rceil\frac{\pi(k+1)}{N}\right)}{\sin\left(\lceil\frac{3N}{2(k+1)}\rceil\frac{\pi}{N}\right)}\right\\},$
(15)

where $\lfloor\cdot\rfloor$ rounds the argument down to the next smaller
integer and $\lceil\cdot\rceil$ rounds the argument up to the next larger
integer.

We note that for large $k$-cycles with non-vanishing link densities, $\rho$,
Eq. (14) can be approximated to $\lambda_{F}/k\simeq
1-\textnormal{sinc}\left[\pi(k+1)/N\right]$, where
$\textnormal{sinc(x)}=\sin(x)/x$ and $(k+1)/k\to 1$. This implies that in the
limit of $N\to\infty$ and $\rho=k/(N-1)$ finite, $\lambda_{F}/k\to
1-\textnormal{sinc}(\pi\,\rho)<1$. On the other hand, Eq. (15) approximates to
$\lambda_{M}/k\simeq 1-\sin(3\pi/2)/(k+1)\sin[3\pi/2(k+1)]$ for large
$k$-cycles with non-vanishing $\rho$, and $\lambda_{M}/k\to 1+2/3\pi>1$ when
$N\to\infty$.

More importantly, according to Eqs. (14) and (15), $k$-cycles with
$2<k<k_{\mathcal{C}}$ are such that $\lambda_{M}/k+\lambda_{F}/k<2$,
$k_{\mathcal{C}}$ being the _critical $k$-cycle degree_ that makes
$\lambda_{M}/k_{\mathcal{C}}+\lambda_{F}/k_{\mathcal{C}}=2$ (see Eq. (38) in
Appendix $k$-cycles). This implies that most $k$-cycles belong to the class of
cyclic graphs with a $\chi_{dyn}^{max}[\mathcal{C}_{N}(k)]$ given by Eq. (9) –
with the exception of the ring graph, $\mathcal{C}_{N}(2)$, and the nearly
complete $k$-cycles, $\mathcal{C}_{N}(k\geq k_{\mathcal{C}})$. Hence, the
_maximum chaoticity that can be stably synchronised in a $k$-cycle_ with
$2<k<k_{\mathcal{C}}$ is

$\chi_{dyn}^{max}[\mathcal{C}_{N}(k)]=-\log\left[\frac{\sin\\!\left[\pi(k+1)/N\right]}{k\sin(\pi/N)}-\frac{1}{k}\right],$
(16)

which is determined from Eq. (9) by substituting $\lambda_{F}$ from Eq. (14).

We note that for a fixed size, $N$, the maximum Lyapunov exponent in Eq. (16)
grows as a function of the degrees as power law with exponent $2$, i.e.,
$\chi_{dyn}^{max}[\mathcal{C}_{N}(k)]\sim k^{2}$. In terms of $\rho$, Eq. (16)
holds in the thermodynamic limit ($N\to\infty$ while $\rho$ finite)

$\chi_{dyn}^{max}[\mathcal{C}_{\infty}(\rho)]=-\log\left[\\!\textnormal{
sinc}\\!\left(\pi\,\rho\right)\right].$ (17)

The $k$-cycles falling outside this degree range, i.e., with $k=2$ or
$k>k_{\mathcal{C}}$, have a $\chi_{dyn}^{max}[\mathcal{C}_{N}(k)]$ determined
by Eq. (8), which requires both $\lambda_{F}$ and $\lambda_{M}$ expressions.
This set of $k$-cycles becomes vanishingly small on the infinite limit size
because $k_{\mathcal{C}}\to N-1$.

We can now derive an explicit expression for the _minimum coupling strength,
$\epsilon^{(c)}[\mathcal{C}_{N}(k),\,\chi_{dyn}]$, necessary to sustain a
locally-stable complete synchronisation in $k$-cycles_ by substituting Eq.
(14) into Eq. (11). That is,

$\epsilon^{(c)}[\mathcal{C}_{N}(k),\,\chi_{dyn}]=\frac{k\,\left[1-\exp(-\chi_{dyn})\right]}{k+1-\sin\\!\left(\pi(k+1)/N\right)/\sin(\pi/N)},$
(18)

which is valid if $\chi_{dyn}<\chi_{dyn}^{max}[\mathcal{C}_{N}(k)]$. In the
thermodynamic limit and if
$\chi_{dyn}<\chi_{dyn}^{max}[\mathcal{C}_{\infty}(\rho)]$, then

$\epsilon^{(c)}[\mathcal{C}_{\infty}(\rho),\,\chi_{dyn}]=\frac{1-\exp(-\chi_{dyn})}{1-\textnormal{sinc}\\!\left(\pi\,\rho\right)}.$
(19)

We note that Eq. (19) would hold $\epsilon_{\infty}^{(c)}>1$ whenever
$\textnormal{sinc}(\pi\,\rho)>\exp(-\chi_{dyn})$; but this is an unstable
state that happens when the map’s Lyapunov exponent is such that
$\chi_{dyn}>\chi_{dyn}^{max}[\mathcal{C}_{\infty}(\rho)]$ for a given
infinite-sized $k$-cycle.
$\epsilon^{(c)}[\mathcal{C}_{\infty}(\rho),\,\chi_{dyn}]$ can be seen on the
left panel of Fig. 3 in logarithmic scale and in colour code, where
$\chi_{dyn}^{max}[\mathcal{C}_{\infty}(\rho)]$ is signaled by a thick dashed
(diagonal) line. Below this line, the synchronisation becomes linearly
unstable, which corresponds to $k$-cycles with sparse connections and maps
with Lyapunov exponent greater than
$\chi_{dyn}^{max}[\mathcal{C}_{\infty}(\rho)]$.

Figure 3: Critical stability points of the synchronisation manifold for
infinitely large $k$-cycles of identical maps. Left panel shows in colour
code, the minimum coupling strength, $\epsilon^{(c)}$ [Eq. (19)], needed to
sustain a linearly-stable synchronisation as a function of the link density,
$\rho$, and map’s Lyapunov exponents, $\chi_{dyn}$. The line signals the
maximum chaoticity, $\chi_{dyn}^{max}$ [Eq. (17)], that can be stably
synchronised in such a $k$-cycle. Right panel shows a numerical example for
logistic maps, coupled in $k$-cycles. Filled (red) circles are the isolated
map’s Lyapunov exponent, $\chi_{dyn}(r)$, as a function of the map’s
parameter, $r$, and filled (blue) squares show our thermodynamic-limit
prediction for the critical (minimum) link-density, $\rho_{c}$ (non-chaotic
solutions, i.e., $\chi_{dyn}\leq 0$, are excluded).

Using the thermodynamic limit from Eq. (17), we can derive the _minimum link
density needed to sustain a linearly-stable synchronisation_ in infinite-sized
$k$-cycles of chaotic maps, which is given by

$\rho_{c}=\frac{1}{\pi}\textnormal{sinc}^{-1}(\exp(-\chi_{dyn})),\;\;\textnormal{for}\;0<\chi_{dyn}<\chi_{dyn}^{max}[\mathcal{C}_{\infty}(\rho)].$
(20)

This implies that it is necessary that $\rho\geq\rho_{c}$ in order to sustain
a locally-stable synchronisation for an infinite number of coupled maps with
Lyapunov exponent $\chi_{dyn}$. For example, if we take $\chi_{dyn}=\log(2)$
(as in a fully chaotic logistic, tent, or shift map), Eq. (20) results in
$\rho_{c}=\textnormal{sinc}^{-1}(2)/\pi\simeq 0.60335$, which is a dense
$k$-cycle. In practical situations, we can use Eq. (20) to find $\rho_{c}$ as
a function, for example, of the logistic map’s control parameter, $r$, as it
is shown on the right panel of Fig. 3. In this way, we can compare the changes
in $\chi_{dyn}(r)$ with the changes in $\rho_{c}(r)$ as we decrease $r$. As
expected, we find that the $k$-cycle can be less densely connected and still
maintain a linearly-stable synchronisation manifold, i.e.,
$\rho_{c}(r<4)<\rho_{c}(r=4)$.

#### Results for $k$-Möbius ladders.

These cyclic graphs are a generalisation of the Möbius ladder. Möbius ladders
are cyclic graphs with either $k=3$ or $4$ neighbours mob_lad_org ; mob_lad ,
making them equivalent to the Möbius strip – a two-dimensional, non-
orientable, manifold. A Möbius ladder with $k=3$ can be constructed, for
example, by adding $N/2$ new links (with $N>3$ and even) connecting opposite
nodes of a $2$-cycle known as _rungs_ ; as it can be seen on the left panel in
Fig. 4. However, Möbius ladders have a vanishing link density, $\rho$, when
$N\to\infty$. We introduce here a way to construct $k$-Möbius ladders,
$\mathcal{M}_{N}(k)$, with arbitrary $k$, keeping $\rho$ finite when
$N\to\infty$.

We generalise _rungs_ by adding $k-2$ edges to each node of a $2$-cycle (i.e.,
a ring, $\mathcal{C}_{N}(2)$), making these edges connect each node to its
$k-2$ furthest nodes in a $2$-cycle. Our construction is restricted to have
$N$ odd [even] if $k$ is even [odd], which is fulfilled whenever $N+5-k=2q$,
with $q\in\mathbb{N}>2$ and $k\leq N-1$ (the left panel in Fig. 4 has
$N(k=3,\,q=6)=3-5+2\times 6=10$). The first row of
$\mathbf{L}[\mathcal{M}_{N}(k)]$ is then given by

$L_{1j}=\left\\{\begin{array}[]{ll}k&\textnormal{if}\;\;j=1,\\\
-1&\textnormal{if}\;\;j=2,N-1\;\;\textnormal{($2$-cycle edges)},\\\
-1&\textnormal{if}\;\;j=(N+5-k)/2,\ldots,(N-1+k)/2,\\\
0&\textnormal{otherwise}.\end{array}\right.$ (21)

Figure 4: $10$-node $k$-Möbius ladders with normalised Laplacian eigenvalues.
From left to right, the top panels show a Möbius ladder ($k=3$), and $2$
generalisations, the $5$-Möbius ladder ($k=5$) and the $7$-Möbius ladder
($k=7$). Bottom panels show their respective normalised Laplacian eigenvalues
(stars signal the Fiedler eigenvalue and circles the maximum eigenvalue) as in
Fig. 2.

We find a compact expression for the Laplacian eigenvalues for $k$-Möbius
ladders by substituting Eq. (21) in Eq. (6) (see Appendix: $k$-Möbius
ladders),

$\displaystyle\lambda_{n}[\mathcal{M}_{N}(k)]=k-2\cos\left(\frac{2\pi
n}{N}\right)-\sum_{j=(N-k+5)/2}^{(N-1+k)/2}\cos\left(\frac{2\pi
n(j-1)}{N}\right)=$ $\displaystyle
k+1-\left[\frac{\sin\left(3\pi\,n/N\right)+(-1)^{n}\sin\left(\pi\,n(k-2)/N\right)}{\sin\left(n\,\pi/N\right)}\right].$
(22)

From Eq. (22), it can be shown that
$\lambda_{M}[\mathcal{M}_{N}(k)]=\max_{n}\\{\lambda_{n}\\}=\lambda_{1}$ if
$7\leq k\leq N-1$, and that
$\lambda_{F}[\mathcal{M}_{N}(k)]=\min_{n}\\{\lambda_{n}>0\\}=\lambda_{2}$ if
$3\leq k\leq k_{c}\simeq(2N+8)/5$ (see Appendix: $k$-Möbius ladders). Outside
these ranges, $\lambda_{F}$ and $\lambda_{M}$ change to other modes. Focusing
on these ranges, when $\lambda_{M}[\mathcal{M}_{N}(k)]=\lambda_{1}$ we have

$\lambda_{M}[\mathcal{M}_{N}(k)]=\lambda_{1}=k+1-\left[\frac{\sin\left(3\pi/N\right)-\sin\left(\pi\,(k-2)/N\right)}{\sin\left(\pi/N\right)}\right]\\!,$
(23)

which for $N\to\infty$ and $\rho$ non-diluted (i.e., avoiding small $\rho$
such that $k\geq 7$)

$\frac{\lambda_{1}[\mathcal{M}_{N}(k)]}{k}\simeq
1-\frac{3}{2\rho(N-1)}+\frac{\sin(\pi\rho)}{\pi\rho}\to
1+\textnormal{sinc}(\pi\rho).$ (24)

On the other hand, when $3\leq k\leq k_{c}\simeq(2N+8)/5$ and
$\lambda_{F}[\mathcal{M}_{N}(k)]=\lambda_{2}$,

$\lambda_{F}[\mathcal{M}_{N}(k)]=k+1-\left[\frac{\sin\left(6\pi/N\right)+\sin\left(2\pi\,(k-2)/N\right)}{\sin\left(2\pi/N\right)}\right]\\!,$
(25)

which for $N\to\infty$ and $\rho<\rho_{c}\simeq 2/5$ (i.e., diluted or
avoiding large $\rho$)

$\frac{\lambda_{2}[\mathcal{M}_{N}(k)]}{k}\simeq
1-\frac{3}{\rho(N-1)}-\frac{\sin(2\pi\rho)}{2\pi\rho}\to
1-\textnormal{sinc}(2\pi\rho).$ (26)

According to Eqs. (23) and (25), $k$-Möbius ladders are such that
$\lambda_{M}/k+\lambda_{F}/k<2$ (as in the $k$-cycles) when $7\leq
k<k_{\mathcal{M}}$, or $\lambda_{M}/k+\lambda_{F}/k>2$ when
$k_{\mathcal{M}}<k\leq k_{c}\simeq(2N+8)/5$; $k_{\mathcal{M}}$ being the
_critical Möbius ladder degree_ that makes
$\lambda_{M}/k_{\mathcal{M}}+\lambda_{F}/k_{\mathcal{M}}=\lambda_{1}/k_{\mathcal{M}}+\lambda_{2}/k_{\mathcal{M}}=2$.
Specifically, $k_{\mathcal{M}}$ is determined from (see Eq. (45) in Appendix:
$k$-Möbius ladders)

$\alpha_{N}=\frac{\sin\left(2\pi\,(k_{\mathcal{M}}-2)/N\right)}{\sin(2\pi/N)}-\frac{\sin\left(\pi\,(k_{\mathcal{M}}-2)/N\right)}{\sin(\pi/N)},$

where
$\alpha_{N}=2-\sin\left(3\pi/N\right)/\sin(\pi/N)-\sin\left(6\pi/N\right)/\sin(2\pi/N)$.
For example, when $N=505$, as in Fig. 5, we obtain (numerically) that
$k_{\mathcal{M}}\simeq 62$. The maximum and Fiedler eigenvalues for $k$-Möbius
ladders with $\lambda_{M}/k+\lambda_{F}/k>2$ are contained within the shaded
area in the right panel of Fig. 5. The remaining cases (in both panels) show
the eigenvalues when $\lambda_{M}/k+\lambda_{F}/k<2$.

Figure 5: Maximum and minimum normalised eigenvalues for $k$-cylces (left) and
$k$-Möbius ladders (right) with $505$ nodes. The blue [green] line corresponds
to the maximum [minimum] normalised eigenvalue $\lambda_{M}/k$
[$\lambda_{F}/k$]. Grey dashed lines show $2-\lambda_{M}/k$. As long as this
distance (dashed lines) is larger than $\lambda_{F}/k$, $\lambda_{M}$ plays no
role in the synchronisation manifold’s stability. However, this distance
becomes smaller than $\lambda_{F}/k$ in the shaded areas on both panels, where
the stability is then determined by $\lambda_{M}/k$.

Consequently, the critical points of the synchronisation manifold’s stability
in $k$-Möbius ladders – maximum Lyapunov exponent that can be synchronised,
$\chi_{dyn}^{max}[\mathcal{M}_{N}(k)]$, and minimum coupling strength,
$\epsilon^{(c)}[\mathcal{M}_{N}(k)]$ – depend on the degree being smaller or
bigger than $k_{\mathcal{M}}$. For $7\leq k<k_{\mathcal{M}}$, the _maximum
chaoticity that can be synchronised in $k$-Möbius ladders_ is determined by
substituting $\lambda_{F}[\mathcal{M}_{N}(k)]$ from Eq. (25) in Eq. (9). That
is,

$\chi_{dyn}^{max}[\mathcal{M}_{N}(k)]=-\log\left(\frac{\sin\left(6\pi/N\right)+\sin\left(2\pi\,(k-2)/N\right)}{k\sin\left(2\pi/N\right)}-\frac{1}{k}\right)\\!.$
(27)

For large $N$, $\lambda_{2}[\mathcal{M}_{\infty}(\rho)]/k\simeq
1-\textnormal{sinc}(2\pi\rho)$ [Eq. (26)]. Hence, the maximum Lyapunov
exponent that can be synchronised transforms to

$\chi_{dyn}^{max}[\mathcal{M}_{\infty}(\rho)]\simeq-\log\left[\\!\textnormal{
sinc}\\!\left(2\pi\,\rho\right)\right],$ (28)

which is valid if $0<\rho\lesssim k_{\mathcal{M}}/(N-1)$. However, we note
that $k_{\mathcal{M}}\to 0$, meaning that $\chi_{dyn}^{max}$ is only valid for
finite-sized $k$-Möbius ladders. We also note that this expression for
$\chi_{dyn}^{max}$ is different from the expression for infinite $k$-cycles
[Eq. (17)] solely because of the $2$ in the argument of the sinc function.

For $k_{\mathcal{M}}<k\leq k_{c}\simeq(2N+8)/5$,
$\chi_{dyn}^{max}[\mathcal{M}_{N}(k)]$ is determined by substituting
$\lambda_{F}[\mathcal{M}_{N}(k)]$ and $\lambda_{M}[\mathcal{M}_{N}(k)]$ from
Eqs. (23) and (25) in Eq. (8),

$\chi_{dyn}^{max}[\mathcal{M}_{N}(k)]=-\log\left[\frac{\lambda_{1}[\mathcal{M}_{N}(k)]-\lambda_{2}[\mathcal{M}_{N}(k)]}{\lambda_{1}[\mathcal{M}_{N}(k)]+\lambda_{2}[\mathcal{M}_{N}(k)]}\right].$
(29)

Similarly to $k$-cycles, in the thermodynamic limit ($N\to\infty$) we can
define a _critical link density_ , $\rho_{\mathcal{M}}$, for infinite-sized
$k$-Möbius ladders such that
$\lambda_{1}[\mathcal{M}_{\infty}(\rho)]/k+\lambda_{2}[\mathcal{M}_{\infty}(\rho)]/k=2$,
finding that $\rho_{\mathcal{M}}=0$ or $1$ (see Appendix: $k$-Möbius ladders),
meaning that Eq. (29) is valid in the range of $k\in(6,N-1]$. Furthermore,
$\lambda_{1}[\mathcal{M}_{\infty}(\rho)]/k=1+\textnormal{sinc}(\pi\rho)$ [Eq.
(24)] and
$\lambda_{2}[\mathcal{M}_{\infty}(\rho)]/k=1-\textnormal{sinc}(2\pi\rho)$ [Eq.
(26)], meaning that

$\chi_{dyn}^{max}[\mathcal{M}_{\infty}(\rho)]=-\log\left[\frac{\textnormal{sinc}(\pi\rho)+\textnormal{sinc}(2\pi\rho)}{2+\textnormal{sinc}(\pi\rho)-\textnormal{sinc}(2\pi\rho)}\right].$
(30)

We can now derive a closed-form expression for the _critical coupling strength
necessary to sustain a locally-stable complete-synchronisation in $k$-Möbius
ladders_ with $7\leq k\leq k_{c}\simeq(2N+8)/5$ by substituting
$\lambda_{2}[\mathcal{M}_{N}(k)]$ into Eq. (11). This results in

$\epsilon^{(c)}[\mathcal{M}_{N}(k),\,\chi_{dyn}]=\frac{k\,\left[1-\exp(-\chi_{dyn})\right]}{(k+1)-\left[\frac{\sin\left(6\pi/N\right)+\sin\left(2\pi\,(k-2)/N\right)}{\sin(2\pi/N)}\right]},$
(31)

which is valid for $\chi_{dyn}\in(0,\chi_{dyn}^{max}]$, where
$\chi_{dyn}^{max}[\mathcal{M}_{N}(k)]$ is determined from Eq. (27) when $7\leq
k<k_{\mathcal{M}}$ and is determined from Eq. (29) when $k_{\mathcal{M}}<k\leq
k_{c}\simeq(2N+8)/5$. In the thermodynamic limit and if
$chi_{dyn}<\chi_{dyn}^{max}[\mathcal{M}_{\infty}(\rho)]$, Eq. (31) transforms
to

$\epsilon^{(c)}[\mathcal{M}_{\infty}(\rho),\,\chi_{dyn}]=\frac{1-\exp(-\chi_{dyn})}{1-\textnormal{sinc}\\!\left(2\pi\,\rho\right)},$
(32)

which is similar to the expression for the infinite-sized $k$-cycles from Eq.
(19).

## Conclusions

In this work, we derive closed-form expressions for the parameters controlling
the stability of the synchronisation manifold of identical maps, diffusively
coupled in regular graphs – graphs were all the nodes have the same degree –
and cyclic graphs – regular graphs with cyclical permutation symmetries. Our
detailed derivations are based on the Master Stability Function (MSF)
MSF_pecora ; Fujisaka_MSF  and the spectral properties of the graph’s
Laplacian matrix CGraphs ; GraphSpectra ; FanChung  (giving expressions for
its eigenvalues), complementing the broad literature of synchronisation in
coupled map lattices Kaneko_1989 ; Amritkar_1993 ; Gallas_2004 ;
Lakshmanan_2005 ; Strogatz_1998 ; Sync_SW_barahona_pecora ; Strogatz_2006
with specific parameter expressions that can be applied straightforwardly.

From the MSF, we study the conditions needed to sustain a stable
synchronisation manifold, which require having negative transversal exponents
[Eq. (5)]. We show that these _stability conditions classify regular graphs
into two sets_ [Fig. 1]: those that fulfill $\lambda_{M}/k+\lambda_{F}/k>2$ or
those that fulfill $\lambda_{M}/k+\lambda_{F}/k<2$, where $\lambda_{M}$ is the
maximum Laplacian eigenvalue, $\lambda_{F}$ is the minimum non-zero eigenvalue
(also known as algebraic connectivity or Fiedler eigenvalue), and $k$ is the
graph’s degree. The critical set of graphs separating these two sets fulfill
$\lambda_{M}/k+\lambda_{F}/k=2$ [Eq. (10)].

Because of this classification and the MSF conditions, we define critical
parameter values. These are the _maximum Lyapunov exponent of the maps_ ,
$\chi_{dyn}^{max}$ [Eqs. (8) and (9)] _that can be synchronised holding a
linearly stable manifold_ , and the _minimum coupling strength_ ,
$\epsilon^{(c)}$ [Eq. (11)] _required in generic regular graphs of coupled
chaotic maps to synchronise_. Specifically, when
$\lambda_{F}/k+\lambda_{M}/k<2$ (as in the non-shaded areas of Fig. 5), the
synchronisation’s stability and these critical parameters depend solely on
$\lambda_{F}/k$. On the other hand, when $\lambda_{F}/k+\lambda_{M}/k>2$ (as
in the shaded areas of Fig. 5) the stability and critical parameters depend on
both, $\lambda_{F}/k$ and $\lambda_{M}/k$.

We then derive closed-form expressions for the eigenvalues of two specific
classes of cyclic graphs: $k$-cycles (i.e., regular lattices with even degree
and cyclic symmetry) [Eq. (13)] and $k$-Möbius ladders [Eq. (22)], which we
introduce to extend the classic Möbius ladder (which has $k=3$). From the
eigenvalue expressions, we find that $\lambda_{F}=\lambda_{1}$ and
$\lambda_{M}=\max\left\\{\lambda_{\lfloor 3N/2(k+1)\rfloor},\lambda_{\lceil
3N/2(k+1)\rceil}\right\\}$ for any finite-sized $k$-cycle [Eqs. (14) and (15),
respectively]. However, in $k$-Möbius ladders, we find that
$\lambda_{F}=\lambda_{2}$ if $k\in[3,\,k_{c}]$ (changing to greater modes as
$k$ is increased beyond $k_{c}\simeq(2N+8)/5$) and $\lambda_{M}=\lambda_{1}$
if $k\in(6,\,N-1)$ [Eqs. (25) and (23), respectively]. From these results, we
show that _when the link density is small, both topologies fall into the class
of regular graphs where $\lambda_{M}/k+\lambda_{F}/k<2$, but as their density
increases, they belong to the other class of regular graphs, where
$\lambda_{M}/k+\lambda_{F}/k>2$_. The limits between the sparse and dense
regimes, $k_{\mathcal{C}}$ and $k_{\mathcal{M}}$ (for $k$-cycles and
$k$-Möbius ladders, respectively), are numerically derived from transcendental
equations [Eqs. (38) and (45)]. We also show that for infinite-sized graphs
the dependence on the network’s degree to determine the stability class
disappears.

Having $\lambda_{F}/k$ and $\lambda_{M}/k$ in $k$-cycles and $k$-Möbius
ladders, we derive explicit expressions for their critical parameter values in
the finite-size and infinite-size limit. Specifically, we determine
$\chi_{dyn}^{max}$ for $k$-cycles [Eqs. (16) and Eq. (17), respectively] and
$\epsilon^{(c)}$, as a function of the $k$-cycle properties (i.e., $k$ and $N$
for finite sizes and $\rho$ for infinite sizes) and Lyapunov exponent,
$\chi_{dyn}$ [Eqs. (18) and (19), respectively]. Also, we show that these two
parameters determine a minimum link density for the synchronisation stability
in $k$-cycle [Fig. 3 and Eq. (46)]. Analogously, we carry derivations for
$k$-Möbius ladders [Eqs. (27), (28), (29), and (30) for $\chi_{dyn}^{max}$ and
Eqs. (31) and (32) for $\epsilon^{(c)}$].

We note that other works have derived different properties of the
synchronisation manifold of coupled maps and analysed networks with
heterogeneity in the node degrees. For example, it has been derived that
piece-wise linear, chaotic maps, coupled in a ring lattice, increase their
entropy for strong coupling Viana_2002  (having an overall well-like shape for
the coupling strength range). If random connections are added to the lattice
(i.e., a Watts-Strogatz model Watts_1998 ; Newman_1999 ; Watts_1999 ;
Newman_2000 ), then, the chaoticity of the system decreases with increasing
number of random connections Viana_2007 , which corresponds to the emergence
of synchronisation. Instead, if long-range interactions are added, then, the
necessary critical coupling-strength for a stable synchronous manifold is
known Viana_2003  (even for non-linear maps), as well as its transient times
Batista_2005 . Similar stability analyses have also been carried out by
previous works, describing critical conditions that allow synchronization in
coupled map networks Sync_SW_barahona_pecora ; Jost_2001 .

Overall, our work is restricted to regular graphs, which means homogeneous
degrees. Because of this restriction, we are able to obtain closed-form
expressions for the relevant parameters of the synchronisation-manifold’s
stability. In spite of this limitation, our results can help in deriving
closed-form expressions for other graphs by means of perturbation theory,
which would allow to include degree heterogeneity. For example, our $k$-cycle
derivations can help when doing perturbation theory on small-world graphs
Watts_1998 ; Newman_1999 ; Watts_1999 ; Newman_2000 .

## Appendix

###  $k$-cycles – Minimum and Maximum Laplacian Eigenvalues

These graphs, $\mathcal{C}_{N}(k)$, only allow connections between $k$ of the
closest neighbours to each node, where $k$ must be an even number. Thus, we
write the Laplacian eigenvalues, $\lambda_{n}[\mathcal{C}_{N}(k)]$
($n=0,\ldots,N-1$), from Eq. (6) as

$\lambda_{n}[\mathcal{C}_{N}(k)]=\sum_{j=1}^{N}L_{1,j}\cos\\!\left(\frac{2\pi
n}{N}(j-1)\right)=k-2\sum_{s=1}^{k/2}\cos\left(\frac{2\pi n}{N}s\right)\\!.$
(33)

Here we derive an closed-form expression for the sum on the right-hand-side
($r.h.s.$) of Eq. (33) by expressing the cosine using its complex exponential
form. That is

$r.h.s.=2\sum_{s=1}^{k/2}\cos\left(\frac{2\pi
n}{N}s\right)=\sum_{s=0}^{k/2}\exp\left[i\frac{2\pi
n}{N}s\right]+\sum_{s=0}^{k/2}\exp\left[-i\frac{2\pi n}{N}s\right]-2,$

where we replace the $2$ geometric sums by their corresponding results.
Namely,

$r.h.s.=\frac{1-\exp\left[i\,2\pi\,n(1+k/2)/N\right]}{1-\exp\left[i\,2\pi\,n/N\right]}+\frac{1-\exp\left[-i\,2\pi\,n(1+k/2)/N\right]}{1-\exp\left[-i\,2\pi\,n/N\right]}-2=\;$
$\;\;=\frac{1-\exp\left[i\,\pi\,n(k+2)/N\right]}{1-\exp\left[i\,2\pi\,n/N\right]}+\frac{1-\exp\left[-i\,\pi\,n(k+2)/N\right]}{1-\exp\left[-i\,2\pi\,n/N\right]}-2,$

which we can transform using the fact that $1-\exp[\pm\,i\,\phi]=\pm
2i\,\sin(\phi/2)\exp[\pm\,i\,\phi/2]$ for an arbitrary phase variable $\phi$.
As a result,

$r.h.s.=\frac{2i\,\sin\left(\pi\,n(k+2)/2N\right)\,\exp\left[i\,\pi\,n(k+2)/2N\right]}{2i\,\sin\left(\pi\,n/N\right)\,\exp\left[i\,\pi\,n/N\right]}+\;\;$
$+\frac{(-2i)\,\sin\left(\pi\,n(k+2)/2N\right)\,\exp\left[-i\,\pi\,n(k+2)/2N\right]}{(-2i)\,\sin\left(\pi\,n/N\right)\,\exp\left[-i\,\pi\,n/N\right]}-2=\;$
$\;=\frac{\sin\left(\pi\,n(k+2)/2N\right)}{\sin\left(\pi\,n/N\right)}\exp\left[i\,\frac{\pi\,n}{2N}k\right]+\frac{\sin\left(\pi\,n(k+2)/2N\right)}{\sin\left(\pi\,n/N\right)}\exp\left[-i\,\frac{\pi\,n}{2N}k\right]-2\;\Rightarrow$
$\Rightarrow\;\;r.h.s.=2\cos\left(\frac{\pi\,n}{2N}k\right)\frac{\sin\left(\pi\,n(k+2)/2N\right)}{\sin\left(\pi\,n/N\right)}-2.$

Now, using that
$2\cos(\beta)\sin(\alpha)=\sin(\alpha+\beta)+\sin(\alpha-\beta)$ on the
$r.h.s.$,

$r.h.s.=\frac{\sin\left(\pi\,n(2k+2)/2N\right)+\sin\left(\frac{\pi\,n}{N}\right)}{\sin\left(\pi\,n/N\right)}-2=\frac{\sin\left(\pi\,n(k+1)/N\right)}{\sin\left(\pi\,n/N\right)}-1.$

Finally, our explicit expression for Eq. (33) is

$\lambda_{n}[\mathcal{C}_{N}(k)]=k-r.h.s.=k+1-\frac{\sin\left(\pi\,n(k+1)/N\right)}{\sin\left(\pi\,n/N\right)}.$
(34)

We note that $\lambda_{0}[\mathcal{C}_{N}(k)]=0$ for any $\mathcal{C}_{N}(k)$,
which can be verified by Eq. (33), and that
$\lambda_{n}[\mathcal{C}_{N}(k=N-1)]=N,\;\forall\,n>0$ for a complete graph.
Also, we observe that $\frac{n}{N}\in[0,\,1),\;\forall\,n$, but because of the
cosine in Eq. (33), only the first (non-zero) modes $\frac{n}{N}\in(0,\,1/2]$
are relevant; the remaining $n$ contribute to the eigenvalue degeneracy. As
$n$ increases from $1$ up to $\left\lfloor N/2\right\rfloor$, the denominator
in Eq. (34) decreases monotonously (without sign changes), making the fraction
increasingly larger. Consequently, the smallest non-zero eigenvalue,
$\lambda_{F}$, of any $\mathcal{C}_{N}(k)$ is its first eigenmode; that is,

$\lambda_{F}[\mathcal{C}_{N}(k)]\equiv\min_{n\in[1,N/2]}\\{\lambda_{n}[\mathcal{C}_{N}(k)]\\}=\lambda_{1}.$
(35)

On the other hand, in order to maximise Eq. (34) and find the largest
eigenvalue, $\lambda_{M}$, we can restrict the modes to those that make
$\sin\left(n\,\pi(k+1)/N\right)=-1$. The first possible solution is when
$n\,\pi(k+1)/N=3\pi/2$, which is fulfilled when $n=\lfloor 3N/2(k+1)\rceil$
(rounding the argument $3N/2(k+1)$ to the nearest integer). Since
$k\in\left[2,N-1\right]$ for any $k$-cycle (implying that
$(k+1)\in\left[3,N\right]$), this is a valid solution for the largest
Laplacian eigenvalue, $\lambda_{M}$. Specifically,

$\lambda_{M}[\mathcal{C}_{N}(k)]=\max\left\\{\lambda_{\lfloor
3N/2(k+1)\rfloor},\lambda_{\lceil 3N/2(k+1)\rceil}\right\\}.$ (36)

Adding the normalised eigenvalues from Eqs. (35) and (36), we get

$\frac{\lambda_{F}}{k}+\frac{\lambda_{M}}{k}=\frac{\lambda_{1}}{k}+\frac{\max\left\\{\lambda_{\lfloor
3N/2(k+1)\rfloor},\lambda_{\lceil 3N/2(k+1)\rceil}\right\\}}{k},$ (37)

where $\lambda_{F}/k+\lambda_{M}/k<2$ for $2<k<k_{\mathcal{C}}$, and
$\lambda_{F}/k+\lambda_{M}/k>2$ for $k>k_{\mathcal{C}}$ (or $k=2$), being
$k_{\mathcal{C}}$ the critical degree determined by the case when
$\lambda_{F}/k_{\mathcal{C}}+\lambda_{M}/k_{\mathcal{C}}=2$, which explicitly
corresponds to

$\frac{2}{k_{\mathcal{C}}}-\frac{1}{k_{\mathcal{C}}}\left[\frac{\sin\left(\pi(k_{\mathcal{C}}+1)/N\right)}{\sin\left(\pi/N\right)}\right]$
$-\frac{1}{k_{\mathcal{C}}}\min\left\\{\frac{\sin\left(\lfloor\frac{3N}{2(k_{\mathcal{C}}+1)}\rfloor\frac{\pi(k_{\mathcal{C}}+1)}{N}\right)}{\sin\left(\lfloor\frac{3N}{2(k_{\mathcal{C}}+1)}\rfloor\frac{\pi}{N}\right)},\,\frac{\sin\left(\lceil\frac{3N}{2(k_{\mathcal{C}}+1)}\rceil\frac{\pi(k_{\mathcal{C}}+1)}{N}\right)}{\sin\left(\lceil\frac{3N}{2(k_{\mathcal{C}}+1)}\rceil\frac{\pi}{N}\right)}\right\\}=0.$

In numerical experiments we observe that this equation is fulfilled in a
region where
$\min\\{\cdots\\}=\sin\left(2\pi(k_{\mathcal{C}}+1)/N\right)/\sin\left(2\pi/N\right)$,
when $N>11$. Thus, for $N>11$, the critical degree is given by the equation

$2-\frac{\sin\left(\pi(k_{\mathcal{C}}+1)/N\right)}{\sin\left(\pi/N\right)}-\frac{\sin\left(2\pi(k_{\mathcal{C}}+1)/N\right)}{\sin\left(2\pi/N\right)}=0,$
(38)

which in the thermodynamic limit holds

$\frac{\lambda_{F}[\mathcal{C}_{N}(k)]}{k}+\frac{\lambda_{M}[\mathcal{C}_{N}(k)]}{k}\to
2-\textnormal{sinc}(\pi\,\rho_{\mathcal{C}})-\textnormal{sinc}(2\pi\,\rho_{\mathcal{C}})=0.$

Consequently, a solution for
$\lambda_{F}/k_{\mathcal{C}}+\lambda_{M}/k_{\mathcal{C}}=2$ in the
thermodynamic limit is $\rho_{\mathcal{C}}=1$, making
$\lambda_{F}/k+\lambda_{M}/k<2,\;\forall\,\rho\in(0,1)$, for infinite sized
$k$-cycles.

###  $k$-Möbius ladders – Minimum and Maximum Laplacian Eigenvalues

These graphs are defined by the Laplacian given in Eq. (21), implying that the
eigenvalues $\lambda_{n}[\mathcal{M}_{N}(k)]$ (with $n=0,\ldots,N-1$) from Eq.
(6) are

$\lambda_{n}[\mathcal{M}_{N}(k)]=k-2\cos\left(\frac{2\pi
n}{N}\right)-\sum_{j=(N+5-k)/2}^{(N-1+k)/2}\cos\left(\frac{2\pi\,n}{N}(j-1)\right)\\!.$
(39)

Here we derive an explicit expression for the sum on the right-hand-side
($r.h.s.$) of Eq. (39) by using complex exponentials and shifting the $j-1$
index to $j$. That is,

$r.h.s.=\sum_{j=(N+5-k)/2}^{(N-1+k)/2}\cos\left(\frac{2\pi\,n}{N}(j-1)\right)=\sum_{j=(N+3-k)/2}^{(N-3+k)/2}\cos\left(\frac{2\pi\,n}{N}j\right)=$
$=\frac{1}{2}\sum_{j=(N+3-k)/2}^{(N-3+k)/2}\left\\{\exp\left[i\frac{2\pi\,n}{N}j\right]+\exp\left[-i\frac{2\pi\,n}{N}j\right]\right\\},$

where we shift $j$ again, such that $j^{\prime}=j-(N+3-k)/2$; namely,

$r.h.s.=\frac{1}{2}\exp{\left[i\frac{\pi\,n}{N}\left(N-k+3\right)\right]}\sum_{j^{\prime}=0}^{k-3}\exp{\left[i\frac{2\pi\,n}{N}j^{\prime}\right]}+$
$+\frac{1}{2}\exp{\left[-i\frac{\pi\,n}{N}\left(N-k+3\right)\right]}\sum_{j^{\prime}=0}^{k-3}\exp{\left[-i\frac{2\pi
n}{N}j^{\prime}\right]}.$

We then substitute the resultant geometric sums of $j^{\prime}$ into $r.h.s.$,

$r.h.s.=\frac{1}{2}\exp{\left[i\frac{\pi\,n}{N}\left(N-k+3\right)\right]}\left(\frac{1-\exp\left[i\frac{2\pi\,n}{N}\left(k-2\right)\right]}{1-\exp\left[i\frac{2\pi\,n}{N}\right]}\right)+$
$+\frac{1}{2}\exp{\left[-i\frac{\pi\,n}{N}\left(N-k+3\right)\right]}\left(\frac{1-\exp{\left[-i\frac{2\pi\,n}{N}\left(k-2\right)\right]}}{1-\exp{\left[-i\frac{2\pi
n}{N}\right]}}\right),$

which we can transform using the fact that $1-\exp[\pm\,i\,\phi]=\pm
2i\,\sin(\phi/2)\exp[\pm\,i\,\phi/2]$ for an arbitrary phase variable $\phi$.
Starting by transforming the denominator and then the numerator of the
geometric sums, we have

$r.h.s.=\frac{1}{4i}\exp{\left[i\frac{\pi\,n}{N}\left(N-(k-3)\right)\right]}\exp{\left[-i\frac{\pi\,n}{N}\right]}\left(\frac{1-\exp\left[i\frac{2\pi
n}{N}\left(k-2\right)\right]}{\sin(n\,\pi/N)}\right)$
$-\frac{1}{4i}\exp{\left[-i\frac{\pi\,n}{N}\left(N-(k-3)\right)\right]}\exp{\left[i\frac{\pi\,n}{N}\right]}\left(\frac{1-\exp\left[-i\frac{2\pi\,n}{N}\left(k-2\right)\right]}{\sin(n\,\pi/N)}\right)=$
$=\frac{2i}{4i}\exp{\left[i\frac{\pi\,n}{N}\left(N-(k-2)\right)\right]}\exp{\left[i\frac{\pi\,n}{N}\left(k-2\right)\right]}\frac{\sin\left(n\,\pi\,(k-2)/N\right)}{\sin(n\,\pi/N)}+$
$+\frac{2i}{4i}\exp{\left[-i\frac{\pi\,n}{N}\left(N-(k-2)\right)\right]}\exp{\left[-i\frac{\pi\,n}{N}\left(k-2\right)\right]}\frac{\sin\left(n\,\pi\,(k-2)/N\right)}{\sin(n\,\pi/N)}=$
$=\frac{1}{2}\exp{\left[i\frac{\pi\,n}{N}N\right]}\frac{\sin\left(n\,\pi\,(k-2)/N\right)}{\sin(n\,\pi/N)}+\frac{1}{2}\exp{\left[-i\frac{\pi\,n}{N}N\right]}\frac{\sin\left(n\,\pi\,(k-2)/N\right)}{\sin(n\,\pi/N)}\;\Rightarrow$
$\Rightarrow\;r.h.s.=\cos\left(n\,\pi\right)\frac{\sin\left(n\,\pi\,(k-2)/N\right)}{\sin(n\,\pi/N)}=(-1)^{n}\frac{\sin\left(n\,\pi\,(k-2)/N\right)}{\sin(n\,\pi/N)}.$

Consequently, our explicit expression for Eq. (39) is

$\lambda_{n}[\mathcal{M}_{N}(k)]=k-2\cos\left(\frac{2\pi\,n}{N}\right)-(-1)^{n}\frac{\sin\left(n\,\pi\,(k-2)/N\right)}{\sin(n\,\pi/N)},$
(40)

which shows the ring contribution (first two terms) and the rungs (last term).
In particular, using that
$2\cos(\beta)\sin(\alpha)=\sin(\alpha+\beta)+\sin(\alpha-\beta)$, we get

$\lambda_{n}[\mathcal{M}_{N}(k)]=k+1-\left[\frac{\sin\left(3\pi\,n/N\right)+(-1)^{n}\sin\left(n\,\pi\,(k-2)/N\right)}{\sin(n\,\pi/N)}\right]\\!,$
(41)

where we note similarities (the term $k+1$, the facts that
$\lambda_{n}[\mathcal{M}_{N}(k)]=0$ for $n=0$ and
$\lambda_{n}[\mathcal{M}_{N}(N-1)]=N-1$ for $n>0$, and the symmetry in $n$
around $N/2$) and differences (terms withing brackets) to Eq. (34) for
$k$-cycles.

Here, $\lambda_{1}[\mathcal{M}_{N}(k)]$ is no longer the Fiedler eigenvalue –
as in Eq. (35) for $k$-cycles – but the maximum eigenvalue, for almost any
$k$. In order to show this, we note that the denominator in the bracketed
expression is a monotonically increasing function of $n\in(0,N/2]$, meaning
that the bracketed term becomes more significant the smaller the $n$. A
negative numerator always tends to maximise the eigenvalue, which happens when
$n$ is odd as long as both sines in the numerator do not change sign. In
particular, the numerator is negative for $n=1$,
$\sin\left(3\pi/N\right)-\sin\left(\pi\,(k-2)/N\right)<0$, as long as
$k\in(5,N-1)$. However, as $n$ is increased, the denominator increases as
well, decreasing the contribution from the bracketed term. As a result,

$\lambda_{M}[\mathcal{M}_{N}(k)]\equiv\max_{n\in[1,N/2]}\\{\lambda_{n}[\mathcal{M}_{N}(k)]\\}=\lambda_{1}\;\;\textnormal{if}\;k\in(6,N-1).$
(42)

For $k\leq 6$, numerical experiments can be performed to find the eigenmode
that maximises the Laplacian eigenvalue in Eq. (41). For example, when $k=6$,
we find that $k$-Möbius ladders with $N$ even have a maximum eigenvalue that
is approximately the mode $n/N\simeq 0.412$; and when $k=3$, the maximum
eigenvalue is given by $n/N=0.5$, which means that
$\lambda_{M}[\mathcal{M}_{N}(3)]=\lambda_{N/2}$. This shows that the mode of
the maximum eigenvalue for $k$-Möbius ladders changes according to the network
size and degree when $k\leq 6$.

Now, we argue that the Fiedler eigenvalue $\lambda_{F}[\mathcal{M}_{N}(k)]$
corresponds to the next lower eigenmodes. In particular, we find that

$\lambda_{F}[\mathcal{M}_{N}(k)]\equiv\min_{n\in[1,N/2]}\\{\lambda_{n}[\mathcal{M}_{N}(k)]\\}=\lambda_{2}\;\;\textnormal{if}\;k\in[3,k_{c}],$
(43)

where $k_{c}<N/2$ is derived from the transcendental identity
$\lambda_{2}=\lambda_{3}$, which is when the Fiedler becomes the third
eigenmode instead of the second. Explicitly,

$\left[\frac{\sin\left(6\pi/N\right)+\sin\left(2\pi\,(k_{c}-2)/N\right)}{\sin(2\pi/N)}\right]=\left[\frac{\sin\left(9\pi/N\right)-\sin\left(3\pi\,(k_{c}-2)/N\right)}{\sin(3\pi/N)}\right],$

which approximately holds $k_{c}\simeq(2N+8)/5$. Similarly, we find that

$\lambda_{F}[\mathcal{M}_{N}(k)]\equiv\min_{n\in[1,N/2]}\\{\lambda_{n}[\mathcal{M}_{N}(k)]\\}=\lambda_{3}\;\;\textnormal{if}\;k\in(k_{c},k_{c}^{\prime}],$
(44)

where $k_{c}^{\prime}$ is derived from the transcendental identity
$\lambda_{3}=\lambda_{4}$, which reads

$\left[\frac{\sin\left(9\pi/N\right)-\sin\left(3\pi\,(k_{c}-2)/N\right)}{\sin(3\pi/N)}\right]=\left[\frac{\sin\left(12\pi/N\right)+\sin\left(4\pi\,(k_{c}-2)/N\right)}{\sin(4\pi/N)}\right].$

Other critical degrees follow, progressively increasing the eigenmode that
corresponds to the Fidler eigenvalue until converging to the complete graph,
where $k=N-1$ and all eigenvalues are the same and hold
$\lambda_{n}[\mathcal{M}_{N}(k=N-1)]=N,\;\forall\,n>0$.

Considering Eqs. (42) and (43), we have that, for $k\in(6,k_{c}]$,

$\frac{\lambda_{M}}{k}+\frac{\lambda_{F}}{k}=\frac{\lambda_{1}[\mathcal{M}_{N}(k)]}{k}+\frac{\lambda_{2}[\mathcal{M}_{N}(k)]}{k}=2\frac{(k+1)}{k},$
$-\frac{1}{k}\left[\frac{\sin\left(3\pi/N\right)-\sin\left(\pi\,(k-2)/N\right)}{\sin(\pi/N)}\right]-\frac{1}{k}\left[\frac{\sin\left(6\pi/N\right)+\sin\left(2\pi\,(k-2)/N\right)}{\sin(2\pi/N)}\right].$

This equation has two solutions: $\lambda_{2}/k+\lambda_{1}/k<2$ when $7\leq
k<k_{\mathcal{M}}$ and $\lambda_{2}/k+\lambda_{1}/k>2$ when
$k_{\mathcal{M}}<k\leq k_{c}\simeq(2N+8)/5$, $k_{\mathcal{M}}$ being the
critical degree determined by the case when
$\lambda_{F}/k_{\mathcal{M}}+\lambda_{M}/k_{\mathcal{M}}=2$. That is,

$\frac{(k_{\mathcal{M}}+1)}{k_{\mathcal{M}}}-1=\frac{\sin\left(3\pi/N\right)-\sin\left(\pi\,(k_{\mathcal{M}}-2)/N\right)}{2k_{\mathcal{M}}\sin(\pi/N)}+\frac{\sin\left(6\pi/N\right)+\sin\left(2\pi\,(k_{\mathcal{M}}-2)/N\right)}{2k_{\mathcal{M}}\sin(2\pi/N)},$
$1=\left[\frac{\sin\left(2\pi\,(k_{\mathcal{M}}-2)/N\right)}{2\sin(2\pi/N)}-\frac{\sin\left(\pi\,(k_{\mathcal{M}}-2)/N\right)}{2\sin(\pi/N)}\right]+\frac{\sin\left(3\pi/N\right)}{2\sin(\pi/N)}+\frac{\sin\left(6\pi/N\right)}{2\sin(2\pi/N)},$
$\alpha_{N}=\frac{\sin\left(2\pi\,(k_{\mathcal{M}}-2)/N\right)}{\sin(2\pi/N)}-\frac{\sin\left(\pi\,(k_{\mathcal{M}}-2)/N\right)}{\sin(\pi/N)},$
(45)

where we define a constant, $\alpha_{N}\equiv
2-\sin\left(3\pi/N\right)/\sin(\pi/N)-\sin\left(6\pi/N\right)/\sin(2\pi/N)$,
which solely depends on $N$. Thus, Eq. (45) is a transcendental equation that
allows to determines the critical degree that differentiates between $2$
classes of $k$-Möbius ladders: those such that
$\lambda_{F}/k_{\mathcal{M}}+\lambda_{M}/k_{\mathcal{M}}<2$ and those that
$\lambda_{F}/k_{\mathcal{M}}+\lambda_{M}/k_{\mathcal{M}}>2$.

We note that when $N\to\infty$, we can use Eqs. (24) and (26) in the
thermodynamic limit of $\lambda_{1}[\mathcal{M}_{N}(k)]$ and
$\lambda_{2}[\mathcal{M}_{N}(k)]$. As a result, we get

$\frac{\lambda_{1}[\mathcal{M}_{N}(k)]}{k}+\frac{\lambda_{2}[\mathcal{M}_{N}(k)]}{k}\to
2+\textnormal{sinc}(\pi\,\rho)-\textnormal{sinc}(2\pi\,\rho).$ (46)

Consequently, there is a critical link density for infinite-sized $k$-Möbius
ladders, $\rho_{\mathcal{M}}$, when
$\textnormal{sinc}(\pi\,\rho_{\mathcal{M}})-\textnormal{sinc}(2\pi\,\rho_{\mathcal{M}})=0$,
with the solutions $\rho_{\mathcal{M}}=0$ and $\rho_{\mathcal{M}}=1$. This
means that infinite-sized $k$-Möbius ladders fulfill
$\lambda_{2}[\mathcal{M}_{\infty}(\rho)]/k+\lambda_{1}[\mathcal{M}_{\infty}(\rho)]/k>2$,
valid for $\rho\in(0,1)$, and coincide with the $k$-cycles on the complete
graphs for $\rho=1$.

## Acknowledgements

J.G. acknowledges funds from the Agencia Nacional de Investigación e
Innonvación (ANII), Uruguay, POS$\\_$NAC$\\_$2018$\\_$1$\\_$151185, and the
Comisión Academica de Posgrado (CAP), Universidad de la República, Uruguay.
Both authors acknowledge funds from the Comision Sectorial de Investigación
Cientifíca (CSIC), Uruguay, group grant “CSIC2018 - FID13 - grupo ID 722”.

## Author Contributions

Juan Gancio: Formal analysis, Visualization, Writing - Original Draft. Nicolás
Rubido: Conceptualization, Visualization, Writing - Review & Editing,
Supervision.

## References

  * (1) Kaneko, K. (1984). Period-doubling of kink-antikink patterns, quasiperiodicity in antiferro-like structures and spatial intermittency in coupled logistic lattice: Towards a prelude of a “field theory of chaos”. Progress of Theoretical Physics, 72(3), 480-486.
  * (2) Kaneko, K. (1989). Spatiotemporal chaos in one-and two-dimensional coupled map lattices. Physica D: Nonlinear Phenomena, 37(1-3), 60-82.
  * (3) Amritkar, R. E., & Gade, P. M. (1993). Wavelength doubling bifurcations in coupled map lattices. Physical Review Letters, 70(22), 3408.
  * (4) Lind, P. G., Corte-Real, J., & Gallas, J. A. (2004). Pattern formation in diffusive-advective coupled map lattices. Physical Review E, 69(6), 066206.
  * (5) Palaniyandi, P., Muruganandam, P., & Lakshmanan, M. (2005). Desynchronized wave patterns in synchronized chaotic regions of coupled map lattices. Physical Review E, 72(3), 037205.
  * (6) K. Kaneko (1990). Clustering, coding, switching, hierarchical ordering, and control in a network of chaotic elements. Physica D: Nonlinear phenomena, 41(2), 137-172.
  * (7) Anteneodo, C., Pinto, S. E. D. S., Batista, A. M., & Viana, R. L. (2003). Analytical results for coupled-map lattices with long-range interactions. Physical Review E, 68(4), 045202.
  * (8) de Souza Pinto, S. E., Lunardi, J. T., Saleh, A. M., & Batista, A. M. (2005). Some aspects of the synchronization in coupled maps. Physical Review E, 72(3), 037206.
  * (9) Rubido, N., Cabeza, C., Kahan, S., Ávila, G. R., & Martí, A. C. (2011). Synchronization regions of two pulse-coupled electronic piecewise linear oscillators. The European Physical Journal D, 62(1), 51-56.
  * (10) Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ’small-world’ networks. Nature, 393(6684), 440-442.
  * (11) Barahona, M., & Pecora, L. M. (2002). Synchronization in small-world systems. Physical Review Letters, 89(5), 054101.
  * (12) Wiley, D. A., Strogatz, S. H., & Girvan, M. (2006). The size of the sync basin. Chaos: An Interdisciplinary Journal of Nonlinear Science, 16(1), 015103.
  * (13) Chavez, M., Hwang, D. U., Amann, A., Hentschel, H. G. E., & Boccaletti, S. (2005). Synchronization is enhanced in weighted complex networks. Physical Review Letters, 94(21), 218701.
  * (14) Masoller, C., & Marti, A. C. (2005). Random delays and the synchronization of chaotic maps. Physical Review Letters, 94(13), 134102.
  * (15) Martí, A. C., Ponce, M., & Masoller, C. (2006). Chaotic maps coupled with random delays: Connectivity, topology, and network propensity for synchronization. Physica A: Statistical Mechanics and its Applications, 371(1), 104-107.
  * (16) Ponce C., M., Masoller, C. & Martí, A. C. (2009). Synchronizability of chaotic logistic maps in delayed complex networks. The European Physical Journal B, 67(1), 83-93.
  * (17) Kaneko, K. (1985). Spatiotemporal intermittency in coupled map lattices. Progress of Theoretical Physics, 74(5), 1033-1044.
  * (18) Xie, F., & Cerdeira, H. A. (1996). Coherent-ordered transition in chaotic globally coupled maps. Physical Review E, 54(4), 3235.
  * (19) Wolfrum, M., & Omel’chenko, E. (2011). Chimera states are chaotic transients. Physical Review E, 84(1), 015201.
  * (20) Hagerstrom, A. M., Murphy, T. E., Roy, R., Hövel, P., Omelchenko, I., & Schöll, E. (2012). Experimental observation of chimeras in coupled-map lattices. Nature Physics, 8(9), 658-661.
  * (21) dos Santos V., Borges F. S., Iarosz, K. C., Caldas, I. L, Szezech, J. D, Viana, R. L., Baptista, M. S, & Batista, A. M. (2020). Basin of attraction for chimera states in a network of Rössler oscillators. Chaos, 30, 083115.
  * (22) de San Roman, F. S., Boccaletti, S., Maza, D., & Mancini, H. (1998). Weak synchronization of chaotic coupled map lattices. Physical review letters, 81(17), 3639.
  * (23) Gade, P. M., & Hu, C. K. (2000). Synchronous chaos in coupled map lattices with small-world interactions. Physical Review E, 62(5), 6409.
  * (24) Jost, J., & Joy, M. P. (2001). Spectral properties and synchronization in coupled map lattices. Physical Review E, 65(1), 016201.
  * (25) Boccaletti, S., Kurths, J., Osipov, G., Valladares, D. L., & Zhou, C. S. (2002). The synchronization of chaotic systems. Physics Reports, 366(1-2), 1-101.
  * (26) Dörfler, F., Chertkov, M., & Bullo, F. (2013). Synchronization in complex oscillator networks and smart grids. Proc. Natl. Acad. Sci., 110(6), 2005-2010.
  * (27) Nardelli, P. H., Rubido, N., Wang, C., Baptista, M. S., Pomalaza-Raez, C., Cardieri, P., & Latva-aho, M. (2014). Models for the modern power grid. The European Physical Journal Special Topics, 223(12), 2423-2437.
  * (28) Nishikawa, T., & Motter, A. E. (2015). Comparative analysis of existing models for power-grid synchronization. New J. Physics, 17(1), 015012.
  * (29) Kaneko, K. (1986). Lyapunov analysis and information flow in coupled map lattices. Physica D: Nonlinear Phenomena, 23(1-3), 436-447.
  * (30) dos Santos, A. M., Woellner, C. F., Lopes, S. R., Batista, A. M., & Viana, R. L. (2007). Lyapunov spectrum of a lattice of chaotic systems with local and non-local couplings. Chaos, Solitons & Fractals, 32(2), 702-710.
  * (31) Kaplan J.L., Yorke J.A. (1979) Chaotic behavior of multidimensional difference equations. In: Peitgen HO., Walther HO. (eds) Functional Differential Equations and Approximation of Fixed Points. Lecture Notes in Mathematics, vol 730.
  * (32) Frederickson, P., Kaplan, J. L., Yorke, E. D., & Yorke, J. A. (1983). The Liapunov dimension of strange attractors. Journal of differential equations, 49(2), 185-207.
  * (33) Kolmogorov, A. N. (1958). A new invariant of transitive dynamical systems. Dokl. Akad. NauL. SSSR, 119,861.
  * (34) Sinai, A. G. (1959). On the concept of entropy of a dynamical system. Dokl Akad. Nauk. SSSR, 124, 768.
  * (35) Batista, A. M., & Viana, R. L. (2002). Kolmogorov-Sinai entropy for locally coupled piecewise linear maps. Physica A: Statistical Mechanics and its Applications, 308(1-4), 125-134.
  * (36) Pecora, L. M., & Carroll, T. L. (1998). Master stability functions for synchronized coupled systems. Physical Review Letters, 80(10), 2109.
  * (37) Fujisaka, H., & Yamada, T. (1983). Stability theory of synchronized motion in coupled-oscillator systems. Progress of Theoretical Physics, 69(1), 32-47.
  * (38) Zhang, H., & Yang, Y. (2007). Resistance distance and Kirchhoff index in circulant graphs. International Journal of Quantum Chemistry, 107(2), 330-339.
  * (39) Van Mieghem, P. (2010). Graph spectra for complex networks (Cap. 3, pp. 43-46). Cambridge University Press.
  * (40) Chung, F. R., & Graham, F. C. (1997). Spectral graph theory (No. 92). American Mathematical Society.
  * (41) Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23(2), 298-305.
  * (42) Gershgorin, S. A. (1931). Uber die abgrenzung der eigenwerte einer matrix. zv. Akad. Nauk SSSR Ser. Mat. , (6), 749-754.
  * (43) Eds. G. Hahn and G. Sabidussi, NATO ASI Ser. C497, Kluwer, 225-275 (1997).
  * (44) K. Ch. Das, A. Dilek Güngör, and A. Sinan Cevic, MATCH Commun. Math. Comput. Chem. 67, 541-556(2012).
  * (45) Guy, R. K., & Harary, F. (1967). On the Möbius ladders. Canadian Mathematical Bulletin, 10(4), 493-496.
  * (46) Pasotti, A. (2010). Constructions for cyclic Möbius ladder systems. Discrete mathematics, 310(22), 3080-3087.
  * (47) Rojas, A., & Diaz, K. (2013). Distance Labellings of Möbius Ladders. disertation Worcester Polytechnic Institute.
  * (48) Idrees, M., Hongbin, M., Nizami, A. R., & Muneer, M. (2017). Generalized Möbius Ladder and Its Metric Dimension. arXiv preprint arXiv:1708.05199.
  * (49) Hussain, Z., Khan, J. A., Munir, M., Saleem, M. S., & Iqbal, Z. (2018). Sharp bounds for partition dimension of generalized Möbius ladders. Open Mathematics, 16(1), 1283-1290.
  * (50) Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’networks. Nature, 393(6684), 440-442.
  * (51) Newman, M. E., & Watts, D. J. (1999). Scaling and percolation in the small-world network model. Physical Review E, 60(6), 7332.
  * (52) Newman, M. E., & Watts, D. J. (1999). Renormalization group analysis of the small-world network model. Physics Letters A, 263(4-6), 341-346.
  * (53) Newman, M. E. (2000). Models of the small world. Journal of Statistical Physics, 101(3), 819-841.