# Maximum size of a triangle-free graph with bounded maximum degree and
matching number††thanks: M. Ahajideh and T. Ekim were supported by TÜBİTAK
grant number 118F397. M.A. Yıldız was supported by a Marie Skłodowska-Curie
Action from the EC (COFUND grant no. 945045) and by the NWO Gravitation
project NETWORKS (grant no. 024.002.003).
e-mail addresses<EMAIL_ADDRESS>(M. Ahanjideh), tinaz.ekim@boun.edu.tr(T.
Ekim<EMAIL_ADDRESS>(M. A. Yıldız).

Milad Ahanjideh†, Tınaz Ekim† and Mehmet Akif Yıldız ‡
† Department of Industrial Engineering, Boğaziçi University,
34342, Bebek, Istanbul,Turkey.
‡ Korteweg de Vries Instituut voor Wiskunde, Universiteit van Amsterdam,
Postbus 94248 1090 GE Amsterdam, The Netherlands.

###### Abstract

Determining the maximum number of edges under degree and matching number
constraints have been solved for general graphs in [7] and [2]. It follows
from the structure of those extremal graphs that deciding whether this maximum
number decreases or not when restricted to claw-free graphs, to $C_{4}$-free
graphs or to triangle-free graphs are separately interesting research
questions. The first two cases being already settled in [8] and [4], in this
paper we focus on triangle-free graphs. We show that unlike most cases for
claw-free graphs and $C_{4}$-free graphs, forbidding triangles from extremal
graphs causes a strict decrease in the number of edges and adds to the
hardness of the problem. We provide a formula giving the maximum number of
edges in a triangle-free graph with degree at most $d$ and matching number at
most $m$ for all cases where $d\geq m$, and for the cases where $d<m$ with
either $d\leq 6$ or $Z(d)\leq m<2d$ where $Z(d)$ is a function of $d$ which is
roughly $5d/4$. We also provide an integer programming formulation for the
remaining cases and as a result of further discussion on this formulation, we
conjecture that our formula giving the size of triangle-free extremal graphs
is also valid for these open cases.

Key words: Extremal graphs; triangle-free graphs; Erdős-Stone’s Theorem;
Turan’s Theorem; integer programming

2010 Mathematics Subject Classification: 05C35, 05C55

##  1 Introduction

In extremal graph theory, an important series of problems, including the
celebrated Turán’s graphs [14], investigate the maximization or the
minimization of the number of edges in a graph under a given set of
constraints. A question of this kind is to determine the maximum number of
edges of a graph when its maximum degree is at most $d$ and its matching
number is at most $m$ for two given integers $d$ and $m$. This is a special
case of a more general problem posed by Erdős and Rado in 1960 [10]. It is
worth mentioning that this problem is equivalent to determining Ramsey numbers
for line graphs [3]. This question has been first solved in 1974 by Chvátal
and Hanson [7] using some optimization techniques. A proof constructing an
“extremal” graph with maximum number of edges under given degree and matching
number constraints has only came out much later in 2009 by Balachandran and
Khare [2]. Balachandran and Khare [2] exhibit an extremal graph whose
connected components consist of stars, complete graphs and in some cases
“almost complete graphs” that contain $C_{4}$’s (cycles of length 4), but do
not inform us on the unicity of these extremal graphs. This gives rise to a
natural question: what happens if we restrict the structure of extremal
graphs? Can the same upper bound be still achieved? The structure of extremal
graphs given in [2] makes this question especially interesting for three
classes of graphs obtained by restricting the above-mentioned types of
components: claw-free graphs obtained by forbidding the smallest star (which
is not an edge), triangle-free graphs obtained by forbidding the smallest
complete graph (which is not an edge), and $C_{4}$-free graphs (since
$C_{4}$’s occur in “almost complete graphs”).

Among these directions, the situation of claw-free graphs has been settled by
Dibek et al. in [8]. The authors exhibit cases where the maximum number of
edges remains the same as for general graphs, and other cases where it is
strictly less. More recently, Blair et al. [4] investigated chordal graphs
which are much more restricted than $C_{4}$-free graphs, the class of graphs
that would exclude the “almost complete graph” components occurring in the
extremal graphs provided in [2]. The authors showed that replacing the “almost
complete graph” components by chordal graphs having the same size, the bound
for general graphs is also achieved by chordal graphs. In the same spirit,
Måland addressed the restriction to bipartite graphs, split graphs, disjoint
unions of split graphs and unit interval graphs in [13].

In this paper, we investigate the direction that remained open and consider
triangle-free graphs from the same perspective. We start with same
preliminaries in Section 2. In Section 3, we first determine the maximum
number of edges of a triangle-free graph when its maximum degree is at most
$d$ and its matching number is at most $m$ for two given integers $d$ and $m$
such that $d>m$ or $d=m$. Besides, for $m>d$, we derive some structural
properties for the connected components of an edge-extremal graph, which
allows us to identify the desired extremal value in further sections. Using
these structural properties, in Section 4, we solve the problem for $m>d$ with
either $d\leq 6$ or $Z(d)\leq m<2d$ where $Z(d)$ is roughly $5d/4$. For claw-
free graphs and chordal graphs, the size of edge-extremal graphs are the same
as the general upper bound in most of the cases. Clearly, this guarantees the
optimality of the size once a graph with desired properties is constructed.
Unlike these cases, the size of edge-extremal triangle-free graphs that we
find in this paper is, in most of the time, strictly less than the general
case. This adds to the difficulty of proving the optimality in our results. In
Section 5, we present all our findings as a unique formula providing the size
of the extremal graphs (in Theorem 5.1) and compare it with the size of
general extremal graphs. Last but not least, in Section 6, we investigate the
remaining cases, namely for natural numbers $m$ and $d$ such that $7\leq d<m$
with either $m<Z(d)$ or $m\geq 2d$. For these open cases, we suggest an
integer programming formulation based on our earlier observations. With
further discussion on this formulation, we conjecture that the formula we
provide in Theorem 5.1 is valid in general, with no condition on $d$ and $m$.
Lastly, again based on our former structural results, we reformulate our
problem as a variant of the extremal problem addressed in Turan’s Theorem [14]
with an additional constraint on the maximum degree; or in Erdős-Stone’s
Theorem which has been described as a fundamental theorem of extremal graph
theory (see [6]). Indeed, the problem of finding the maximum number of edges
in a $K_{r}$-free graph with given number of vertices and maximum degree at
most $d$ is an interesting problem for itself.

##  2 Notation and Preliminaries

Throughout this paper, $G=(V(G),E(G))$ is a simple undirected graph. We call
$|V(G)|$ and $|E(G)|$ the order and the size of $G$, respectively. For any
vertex $v\in V(G)$, the number of vertices adjacent to $v$ is said to be the
degree of $v$, denoted by $d(v)$. We say a graph $G$ is $d$-regular if
$d(v)=d$ for all $v\in V(G)$. Moreover, if $d(w)=d-1$ for some $w\in V(G)$ and
$d(v)=d$ for all $v\in V(G)-w$, then $G$ is said to be almost $d$-regular. We
denote the maximum degree of $G$ by $\Delta(G)$, and the minimum degree of $G$
by $\delta(G)$. The minimum number of colors to color all edges of a graph $G$
in such a way that two adjacent edges receive different colors is called the
chromatic index of $G$, and denoted by $\chi^{\prime}(G)$. According to
Vizing’s Theorem, we have $\Delta(G)\leq\chi^{\prime}(G)\leq\Delta(G)+1$ for
any graph $G$ [15]. Given a graph, a set of edges having pairwise no common
end vertex is called a matching. The size of a maximum matching of $G$ is
called the matching number and denoted by $\nu(G)$. We say that $G$ has a
perfect matching if $\nu(G)=n/2$, where $n=|V(G)|$. The complete graph of
order $n$ and the complete bipartite graph with sets of sizes $m$ and $n$ are
denoted by $K_{n}$ and $K_{m,n}$, respectively. The graph $K_{1,d}$ is called
a $d$-star. A graph is triangle-free if it does not contain $K_{3}$ as an
induced subgraph.

For a given graph class $\mathbf{C}$ and two given positive integers $d$ and
$m$, we define $\mathbb{M}_{\mathbf{C}}(d,m)$ to be the set of all graphs $G$
in $\mathbf{C}$ satisfying $\Delta(G)\leq d$ and $\nu(G)\leq m$. A graph in
$\mathbb{M}_{\mathbf{C}}(d,m)$ with the maximum number of edges is called
edge-extremal, and the number of edges of an edge-extremal graph in
$\mathbb{M}_{\mathbf{C}}(d,m)$ is denoted by $f_{\mathbf{C}}(d,m)$. Let
$\vartriangle$ be the class of triangle-free graphs. In this paper, we assume
that edge-extremal graphs have no isolated vertices since adding isolated
vertices to a graph does not increase the number of edges.

We note that in general, if one of the two parameters $\Delta(G)$ and $\nu(G)$
is not bounded, then the size of $G$ is not bounded neither (for general
graphs). Indeed, a star has matching number one no matter how large its
degree, thus its size. Likewise, the graph consisting of an unbounded number
of independent $K_{2}$’s (that is, sharing no common vertex) is an example
where the maximum degree is bounded (by one) but the matching number is not,
neither the size. It follows from this discussion that, in general, one should
bound both the matching number and the degree of a graph so that its size is
also bounded. In this case, Vizing’s Theorem provides us with a natural upper
bound on the size of a graph. For any graph $G$, since the set of edges having
the same color in an edge-coloring of $G$ forms a matching whose size is at
most $\nu(G)$, and we have $\chi^{\prime}(G)\leq\Delta(G)+1$ by Vizing’s
Theorem; we obtain $|E(G)|\leq(\Delta(G)+1)\nu(G)$. For given bounds
$\Delta(G)\leq d$ and $\nu(G)\leq m$, an edge-extremal graph can thus have at
most $dm+m$ edges. The maximum size of a general graph with $\Delta(G)\leq d$
and $\nu(G)\leq m$ obtained in [7] and [2] shows that this upper bound is
actually met when some divisibility conditions hold, and we are “pretty close”
to it otherwise. The following theorem gives not only the formula for the
maximum size of a (general) graph with $\Delta(G)\leq d$ and $\nu(G)\leq m$,
but also describes an edge-extremal graph. Let $\mathcal{GEN}$ denote the
class of general graphs.

######  Theorem 2.1 ([2]).

With the preceding notation, we have,

$f_{\mathcal{GEN}}(d,m)=dm+\left\lfloor\frac{d}{2}\right\rfloor\left\lfloor\frac{m}{\lceil\frac{d}{2}\rceil}\right\rfloor.$

Moreover, a graph with $f_{\mathcal{GEN}}(d,m)$ edges is obtained by taking
the disjoint union of $r$ copies of $d$-star and $q$ copies of

$\begin{cases}K_{d+1}&$if d+1 is odd$\\\ K^{\prime}_{d+1}&$if d+1 is
even$,\end{cases}$

where $q$ is the largest integer such that
$m=q\left\lceil\frac{d}{2}\right\rceil+r$ and $r\geq 0$; and where
$K^{\prime}_{d+1}$ is the graph obtained by removing a perfect matching from
the complete graph $K_{d+1}$ on $d+1$ vertices, adding a new vertex $v$, and
making $v$ adjacent to $d$ of the other vertices.

In this paper, we find the size of triangle-free extremal graphs in most
cases; apart from two simple cases, namely $d=1$ and $m<\lfloor d/2\rfloor$,
none of them achieves the general upper bound given in Theorem 2.1.

Let us now introduce a key lemma that describes the structure of edge-extremal
graphs. A graph $G$ is said to be  factor-critical if $G\setminus v$ has a
perfect matching for all $v\in V(G)$. By definition, being factor-critical for
a graph $G$ directly implies that $|V(G)|=2\nu(G)+1$. We will use the
following well-known result which is a sufficient condition for a graph to be
factor-critical.

######  Lemma 2.2.

(Gallai’s Lemma, [11]) If $G$ is a connected graph such that for all $v\in
V(G)$, $\nu(G\setminus v)=\nu(G)$, then $G$ is factor-critical and hence
$|V(G)|=2\nu(G)+1$.

The following lemma has been first given in [2] for general graphs, and then
restated slightly differently in [4]. It establishes a connection between
edge-extremal graphs and factor-critical graphs for a wide range of graph
classes, including triangle-free graphs. For the sake of completeness, we also
provide a short proof. Let us introduce a special class of extremal graphs
that will be our main focus in the rest of the paper.

######  Definition 2.3.

$\mathcal{G}_{\mathbf{C}}(d,m)$ is the subclass of the set of edge-extremal
graphs in $\mathbb{M}_{\mathbf{C}}(d,m)$ which consists of the graphs having
maximum number of connected components isomorphic to a $d$-star.

######  Lemma 2.4.

[2, 4] Let $d,m$ be natural numbers, and let $\mathbf{C}$ be a graph class
that is closed under vertex deletion and closed under taking disjoint union
with stars. Take a graph $G\in\mathcal{G}_{\mathbf{C}}(d,m)$. Then, every
connected component of $G$ that is not a $d$-star is factor-critical.

###### Proof.

Suppose on the contrary that $W$ is a connected component of $G$ which is
neither a $d$-star nor factor-critical. By Lemma 2.2, there is a vertex $v$ in
$W$ such that $\nu(W\setminus v)<\nu(W)$. Now we construct a new graph
$G^{\prime}$ whose components are the components of $G$ except $W$,
$W\setminus v$ and a $d$-star. One can observe that
$G^{\prime}\in\mathbb{M}_{\mathbf{C}}(d,m)$ and $|E(G^{\prime})|=|E(G\setminus
v)|+d\geq|E(G)|$. So $G^{\prime}$ is an edge-extremal graph in
$\mathbb{M}_{\mathbf{C}}(d,m)$ with more star components than in $G$, a
contradiction with the assumptions on $G$. ∎

Lastly, we derive a result that will be useful in Section 4. Let $\chi(G)$
denote the minimum number of colors needed to color all vertices of $G$ in
such a way that two adjacent vertices get different colors.

######  Lemma 2.5.

[1] Let $r\geq 3$. For any graph $G$ on $n$ vertices, at most two of the
following properties can hold:

  1. 1.

$G$ does not contain $K_{r}$ as an induced subgraph,

  2. 2.

$\delta(G)>\dfrac{3r-7}{3r-4}n$,

  3. 3.

$\chi(G)\geq r$.

The following corollary states that for $r=3$, if properties 1 and 2 of Lemma
2.5 hold, then property 3 is not satisfied.

######  Corollary 2.6.

Any triangle-free graph of order $n$ with minimum degree greater than
$\dfrac{2n}{5}$ is bipartite.

##  3 Edge-extremal triangle-free graphs with $d\geq m$

In this section, we find the maximum number of edges in a triangle-free graph
with matching number at most $m$ and degree at most $d$ and where $d>m$.
Besides, we also solve the case where $d=m$. Solving these cases allows us to
further strengthen our assumption in Lemma 2.4 on the structure of an edge-
extremal triangle-free graph. Stated in Corollary 3.5, this structural
property will play a key role to obtain our main results for $d<m$ in Sections
4 and 5. First, let us bound the number of edges in a factor-critical
triangle-free graph in terms of the matching number.

######  Lemma 3.1.

Let $H$ be a factor-critical triangle-free graph. Then, we have $|E(H)|\leq
1+\nu(H)^{2}$.

###### Proof.

Since $H$ is factor-critical, we have $|V(H)|=2h+1$ where $h:=\nu(H)$.
Bipartite graphs are not factor-critical, therefore $H$ has an odd cycle. Let
us take the smallest (induced) odd cycle $C_{2s+1}$ in $H$. Notice that $s\geq
2$ since $H$ is triangle-free. Moreover, there is at most $(h-s)^{2}$ edges
within $H-C_{2s+1}$ by Turan’s theorem since $H-C_{2s+1}$ has $2h-2s$
vertices. On the other hand, any vertex in $H-C_{2s+1}$ can have at most $s$
neighbors in $C_{2s+1}$ because otherwise there would be a triangle. As a
result, we get

$\displaystyle|E(G)|$ $\displaystyle\leq$
$\displaystyle(2s+1)+(h-s)^{2}+(2h-2s)s$ $\displaystyle\leq$
$\displaystyle(s^{2}+1)+(h-s)^{2}+(2h-2s)s=1+h^{2},$

which completes the proof. ∎

By using Lemma 3.1, we can derive the following structural property for the
graphs in $\mathcal{G}_{\vartriangle}(d,m)$.

######  Lemma 3.2.

Let $G\in\mathcal{G}_{\vartriangle}(d,m)$. Then, for any connected component
$H$ of $G$ that is not a $d$-star, we have

  * (i)

$|E(H)|\leq 1+\nu(H)^{2}$, and

  * (ii)

$\nu(H)\geq d$.

###### Proof.

Since $H$ is not a star, by Lemma 2.4, $H$ is factor-critical. Then, part (i)
follows from Lemma 3.1. Now, suppose $\nu(H)<d$. Since $H$ is triangle-free
and non-bipartite, we have $\nu(H)\geq 2$. Thus, we get $|E(H)|\leq
1+\nu(H)^{2}<d\cdot\nu(H)$. Then, take $\nu(H)$ copies of $d$-stars instead of
$H$; this increases the number of edges while keeping $\nu(G)$ and $\Delta(G)$
the same. This contradicts with $G\in\mathcal{G}_{\vartriangle}(d,m)$.
Therefore, we get $\nu(H)\geq d$, so the result follows. ∎

Lemma 3.2 allows us to answer the cases $d>m\geq 1$ (in Theorem 3.3) and $d=m$
(in Theorem 3.4).

######  Theorem 3.3.

With the preceding notation, $f_{\vartriangle}(d,m)=dm$ for $d>m\geq 1$.

###### Proof.

Assume $d>m$, and take $G\in\mathcal{G}_{\vartriangle}(d,m)$. If $G$ has a
component $G_{1}$ that is not a $d$-star, then by Lemma 3.2 (ii), we would get
$m\geq\nu(G_{1})\geq d$, which is a contradiction. Hence, all the components
of $G$ are $d$-stars, so we get $|E(G)|=dm$. ∎

######  Theorem 3.4.

With the preceding notation, $f_{\vartriangle}(1,1)=1$ and
$f_{\vartriangle}(d,d)=d^{2}+1$ for $d\geq 2$.

###### Proof.

Firstly, any graph $G$ with $\Delta(G)=\nu(G)=1$ can contain only one edge, so
$f_{\vartriangle}(1,1)=1$ follows. Now, consider the graph $A_{d}$ shown in
Figure 1. It can be easily seen that $A_{d}\in\mathbb{M}_{\vartriangle}(d,d)$
and $|E(A_{d})|=d^{2}+1$. Then, let us take
$G\in\mathcal{G}_{\vartriangle}(d,m)$. By definition of $G$, we have
$|E(G)|\geq|E(A_{d})|$ giving $|E(G)|\geq d^{2}+1$. If all the components of
$G$ are $d$-stars, then we would get $|E(G)|\leq d^{2}$, which is a
contradiction. Hence, $G$ has at least one component which is not a $d$-star;
let us denote it by $G_{1}$. By Lemma 3.2 (ii), we have $\nu(G_{1})\geq d$.
Since $d=\nu(G)\geq\nu(G_{1})$ we obtain $G_{1}=G$. Now, by Lemma 3.2 (i), we
have $|E(G)|\leq d^{2}+1$, which completes the proof.

∎

Figure 1: $A_{d}$ is a graph on $2d+1$ vertices which is a blow-up of a cycle
of length five. A circle and the number inside it represent an independent set
of that size, and straight lines between two circles or between a vertex and a
circle indicate that all possible edges are present.

We close this section with a corollary of Lemmas 2.4 and 3.2, which states
that for any edge-extremal graph in $\mathcal{G}_{\vartriangle}(d,m)$ (whose
number of $d$-star components is maximum), every component $H$ of it which is
not a $d$-star is a factor-critical and edge-extremal graph in
$\mathbb{M}_{\vartriangle}(d,\nu(H))$ with matching number $\nu(H)\geq d$. An
extremal graph with these properties will be useful to prove our results in
Section 4.

######  Corollary 3.5.

Let $d$ and $m$ be natural numbers, and let
$G\in\mathcal{G}_{\vartriangle}(d,m)$. Then, for every connected component $H$
of $G$, one of the following is true:

  * (i)

$H$ is a $d$-star.

  * (ii)

$|E(H)|=f_{\vartriangle}(d,\nu(H))$ and $|V(H)|=2\cdot\nu(H)+1$ where
$\nu(H)\geq d$.

###### Proof.

Let $H$ be a connected component of $G$ that is not a $d$-star. First of all,
we know $\nu(H)\geq d$ by Lemma 3.2. Also, from Lemma 2.4, we know that $H$ is
factor-critical, thus $|V(H)|=2\cdot\nu(H)+1$. Hence, we have
$H\in\mathbb{M}_{\vartriangle}(d,\nu(H))$ since $\Delta(H)\leq d$, which
implies $|E(H)|\leq f_{\vartriangle}(d,\nu(H))$. On the other hand, if
$|E(H)|<f_{\vartriangle}(d,\nu(H))$, we would get $|E(G)|<|E(G_{1})|$ by
taking $G_{1}$ as the disjoint union of $G-H$ and $H_{1}$ for some
$H_{1}\in\mathbb{M}_{\vartriangle}(d,\nu(H))$, which leads to a contradiction.
As a result, we get $|E(H)|=f_{\vartriangle}(d,\nu(H))$. ∎

##  4 Edge-extremal triangle-free graphs with $m>d$

We start this section with the trivial case $d=1$. Then, we will investigate a
deeper study on the structure of extremal graphs to settle two cases with
$m>d$, namely $Z(d)\leq m<2d$ for some function $Z(d)$ introduced in
Definition 4.2, and $d\leq 6$.

######  Theorem 4.1.

With the preceding notation, we have $f_{\vartriangle}(1,m)=m$ for all $m\geq
1$.

###### Proof.

If $\Delta(G)=1$ for a graph $G$, then $G$ is the disjoint union of $\nu(G)$
edges, so the result follows. ∎

In the rest of this section, we assume $d\geq 2$. Our results will be based on
the following key property. We will show that if $H$ is a connected component
of a graph $G\in\mathcal{G}_{\vartriangle}(d,m)$ and if it is not a $d$-star
then in addition to the assumption $\nu(H)\geq d$ given in Corollary 3.5 ii),
we can also bound $\nu(H)$ from above by $Z(d)$ (see Lemma 4.5) where $Z(d)$
is defined below and described in Lemma 4.7.

######  Definition 4.2.

For any $d\geq 2$, let $Z(d)$ be the smallest natural number $n$ such that
there exists a $d$-regular (if $d$ is even) or almost $d$-regular (if $d$ is
odd) triangle-free and factor-critical graph $G$ with $\nu(G)=n$.

Let us introduce the graph $B_{d}$ given in Figure 2; it is a (almost)
$d$-regular triangle-free and factor-critical graph, which shows the existence
of $Z(d)$. The blow-up of a graph is obtained by replacing every vertex with a
finite collection of copies so that the copies of two vertices are adjacent if
and only if the originals are. In particular, the copies of the same vertex
form an independent set in the blow-up graph. Let us emphasize some properties
of the graph $B_{d}$ in Proposition 4.3.

Figure 2:  The graph $B_{d}$ for $d\geq 2$ depending on $d\pmod{4}$. Each
graph is obtained from a blow-up of a cycle of length 5 by removing some
perfect matchings. For simplicity, edges of the blow-up graph are not shown
although they are all present. The copies of the same vertex in the blow-up
graph are divided into bags shown by dotted or continuous circles, each one
containing as many copies as the number indicated in it. The lines between
different bags represent perfect matchings between the corresponding sets of
vertices that are removed from the graph.

######  Proposition 4.3.

The graph $B_{d}$ in Figure 2 is (almost) $d$-regular, triangle-free, and
factor-critical. Moreover, we have $|V(B_{d})|=2\nu(B_{d})+1$ and
$|E(B_{d})|=d\nu(B_{d})+\lfloor d/2\rfloor$ where

$\nu(B_{d})=\begin{cases}\lfloor 5d/4\rfloor,&\text{ if }d\text{ is even,}\\\
\lfloor 5(d+1)/4\rfloor,&\text{ if }d\text{ is odd.}\end{cases}$

###### Proof.

Firstly, it can be easily checked that $B_{d}$ is $d$-regular when $d$ is
even. For odd values of $d$, all the vertices except the vertex in $A_{11}$
have degree $d$, and the vertex in $A_{11}$ has degree $d-1$. Therefore,
$B_{d}$ is almost $d$-regular when $d$ is odd. Moreover, each $B_{d}$ is a
(partial) subgraph of a graph that is a blow-up of a cycle of length five,
which implies that each $B_{d}$ is triangle-free. Therefore, we only need to
show that $B_{d}$ is factor-critical. We note that $B_{4k+1}$ and $B_{4k+3}$
can be obtained from $B_{4k+2}$ and $B_{4k+4}$, respectively, by deleting some
edges. Thus, it suffices to show that $B_{4k+1}$ and $B_{4k+3}$ are factor-
critical. For every vertex $v$ in $B_{d}$, we will show that $B_{d}-v$ has a
perfect matching. Due to symmetry, it is enough to examine the cases $v\in
A_{1}\cup A_{2}\cup A_{4}$. Since all the examinations are quite similar and
straight-forward, we will only show the case $v\in A_{1}$ and leave the rest
to the reader. It is well-known that any regular bipartite graph has a perfect
matching. We will show that the vertices in $B_{d}-v$ can be partitioned into
some pairs of subsets so that each pair induces a regular bipartite graph and
thus admits a perfect matching. If $v\in A_{11}$, then we can partition the
vertices into pairs of subsets as $(A_{22},A_{13})$, $(A_{12},A_{32})$,
$(A_{21}\cup A_{23},A_{42})$, $(A_{31}\cup A_{33},A_{52})$ and
$(A_{41},A_{51})$. If $v\in A_{12}\cup A_{13}$, without loss of generality we
can assume $v\in A_{12}$. Similarly, we can partition the vertices into pairs
of subsets $(A_{11}\cup(A_{12}-v),A_{32})$, $(A_{13},A_{22})$, $(A_{21}\cup
A_{23},A_{42})$, $(A_{31}\cup A_{33},A_{52})$ and $(A_{41},A_{51})$. Since
$B_{d}$ is factor-critical, we have $|V(B_{d})|=2\nu(B_{d})+1$, and a maximum
matching saturates all vertices but one; expressing the number of vertices as
a function of $k$ in each one of the four cases, it can be checked that we
have $\nu(B_{d})=\lfloor 5d/4\rfloor$ if $d$ is even, and $\nu(B_{d})=\lfloor
5(d+1)/4\rfloor$ if $d$ is odd. Lastly, $|E(B_{d})|=d\nu(B_{d})+\lfloor
d/2\rfloor$ follows from the fact that $B_{d}$ is factor-critical and (almost)
$d$-regular. ∎

For any $d\geq 2$, let $C_{d}$ be a (almost) $d$-regular triangle-free factor-
critical graph with matching number $Z(d)$. An important consequence of the
properties of the graphs $B_{d}$ shown in Proposition 4.3 is the following:

######  Corollary 4.4.

For every $d\geq 2$, the value $Z(d)$ and a triangle-free factor-critical
(almost) $d$-regular graph $C_{d}$ with matching number $Z(d)$ exist.

Now, we are ready to show that the matching number of each connected component
of a graph $G\in\mathcal{G}_{\vartriangle}(d,m)$ is bounded above by $Z(d)$.
Indeed, this additional information on the structure of connected components
in an extremal graph will be very useful in both calculating
$f_{\vartriangle}(d,m)$ in the rest of this section, and guiding us for future
research to complete the remaining open cases.

######  Lemma 4.5.

Let $d$ and $m$ be natural numbers with $d\geq 2$, and let
$G\in\mathcal{G}_{\vartriangle}(d,m)$. Then, for every connected component $H$
of $G$, we have $\nu(H)\leq Z(d)$.

###### Proof.

For a contradiction, let $G\in\mathcal{G}_{\vartriangle}(d,m)$ and $H$ be a
connected component of $G$ with $\nu(H)=Z(d)+t$ for some $t\geq 1$. By
Corollary 3.5 (ii), we know that $|V(H)|=2\nu(H)+1$. Since $\Delta(H)\leq d$,
we have

$|E(H)|\leq\lfloor(2\nu(H)+1)d/2\rfloor=\nu(H)d+\lfloor d/2\rfloor.$

On the other hand, let $G_{1}$ be the graph obtained by taking the disjoint
union of $G-H$, the graph $C_{d}$, and $t$ many $d$-stars. Notice that $G_{1}$
has more $d$-stars than $G$, so we have $|E(G_{1})|<|E(G)|$ by definition of
$\mathcal{G}_{\vartriangle}(d,m)$. However, we can write

$\displaystyle|E(G_{1})|$ $\displaystyle=$
$\displaystyle|E(G-H)|+(dZ(d)+\lfloor d/2\rfloor)+dt$ $\displaystyle=$
$\displaystyle|E(G-H)|+\nu(H)d+\lfloor d/2\rfloor$ $\displaystyle\geq$
$\displaystyle|E(G-H)|+|E(H)|=|E(G)|,$

which is a contradiction. ∎

We can use Lemma 3.1 to find the exact value of $Z(d)$ for small values of
$d$. These values, on one hand, will allow us to show that $Z(d)\geq d$, thus
we can address the case $Z(d)\leq m\leq 2d$ within the case $m>d$, on the
other hand, they will be useful while solving the case $d\leq 6$.

######  Lemma 4.6.

We have $Z(d)=d$ for $d\in\\{2,3\\}$, and $Z(d)=d+1$ for $d\in\\{4,5\\}$.
Moreover, $Z(d)\geq d+1$ holds for all $d\geq 4$.

###### Proof.

By Lemma 3.1, we have $|E(C_{d})|\leq 1+Z(d)^{2}$ since $C_{d}$ is factor-
critical and triangle-free. Since $C_{d}$ is (almost) $d$-regular, we get

$|E(C_{d})|=\lfloor(2Z(d)+1)d/2\rfloor=dZ(d)+\lfloor d/2\rfloor.$

Hence, we obtain $\lfloor d/2\rfloor-1\leq Z(d)(Z(d)-d)$. Since $\lfloor
d/2\rfloor-1\geq 0$ for all $d\geq 2$, and $\lfloor d/2\rfloor-1\geq 1$ for
all $d\geq 4$, we get $Z(d)\geq d$ for all $d\geq 2$ and $Z(d)\geq d+1$ for
all $d\geq 4$. By Proposition 4.3, $B_{2}$ and $B_{4}$ are factor-critical and
triangle-free graphs with $\nu(B_{2})=2$ and $\nu(B_{4})=5$, respectively.
Also, $B_{2}$ is $2$-regular and $B_{4}$ is $4$-regular. Therefore, we get
$Z(2)=2$ and $Z(4)=5$. Besides, $A_{3}$ (see Figure 1) is an almost
$3$-regular triangle-free and factor-critical graph with $\nu(A_{3})=3$, which
shows $Z(3)=3$. Finally, we identified using a computer search the graph
$M_{5}$ given in Figure 3 as the unique triangle-free graph which is both
factor-critical with $\nu(M_{5})=6$ and almost $5$-regular; this shows
$Z(5)=6$. ∎

Figure 3: The graph $M_{5}$.

As for larger $d$, Corollary 2.6 allows us to obtain the exact value of $Z(d)$
for even values of $d$, and to identify a very restricted interval for $Z(d)$
if $d$ is odd.

######  Lemma 4.7.

For $d\geq 2$, if $d$ is even then we have $Z(d)=\lfloor 5d/4\rfloor$; if $d$
is odd then we have $\lfloor 5(d-1)/4\rfloor\leq Z(d)\leq\lfloor
5(d+1)/4\rfloor$.

###### Proof.

Since factor-critical graphs are non-bipartite, $|V(C_{d})|=2Z(d)+1$ and
$\delta(C_{d})=2\lfloor d/2\rfloor$, we get $2\lfloor
d/2\rfloor\leq\dfrac{2(2Z(d)+1)}{5}$ by Corollary 2.6, which gives
$Z(d)\geq\lfloor 5d/4\rfloor$ when $d$ is even and $Z(d)\geq\lfloor
5(d-1)/4\rfloor$ when $d$ is odd. On the other hand, we have
$\nu(B_{d})=\lfloor 5d/4\rfloor$ when $d$ is even and $\nu(B_{d})=\lfloor
5(d+1)/4\rfloor$ when $d$ is odd. Since $Z(d)\leq\nu(B_{d})$, the result
follows. ∎

Now, by Lemmas 4.6 and 4.7, it is clear that $d\leq Z(d)<2d$ for any $d\geq
2$. Now we have the necessary ingredients to give the exact value of
$f_{\vartriangle}(d,m)$ for $Z(d)\leq m<2d$.

######  Theorem 4.8.

With the preceding notation, for $d\geq 2$ and $Z(d)\leq m<2d$, we have
$f_{\vartriangle}(d,m)=dm+\lfloor d/2\rfloor$.

###### Proof.

Let $T$ be the disjoint union of $C_{d}$ and $m-Z(d)$ many $d$-stars. Clearly
we have $\Delta(T)=d$, $\nu(T)=m$ and

$|E(T)|=dZ(d)+\lfloor d/2\rfloor+d(m-Z(d))=dm+\lfloor d/2\rfloor,$

which shows $f_{\vartriangle}(d,m)\geq dm+\lfloor d/2\rfloor$. Then, let us
take $G\in\mathcal{G}_{\vartriangle}(d,Z(d))$. Hence, we have
$|E(G)|=f_{\vartriangle}(d,Z(d))\geq dm+\lfloor d/2\rfloor$, so it suffices to
show that $|E(G)|\leq dm+\lfloor d/2\rfloor$. Assume $G$ has at least two
connected components $H_{1}$ and $H_{2}$ that are not $d$-stars. Then, by part
(ii) of Corollary 3.5, we get $2d\leq\nu(H_{1})+\nu(H_{2})\leq m$, however
$m<2d$ by assumption, which is a contradiction. Moreover, if all the connected
components of $G$ are $d$-stars, then we would get $|E(G)|=dm$, which
contradicts with $|E(G)|\geq dm+\lfloor d/2\rfloor$. Therefore, $G$ has
exactly one connected component that is not a $d$-star. Suppose $G$ has $t$
many connected components that are $d$-stars, and let $H$ be the connected
component of $G$ that is not a $d$-star. Again, by part (ii) of Corollary 3.5,
we know $|V(H)|=2\nu(H)+1$. On the other hand, since $\Delta(H)\leq d$, we
have

$|E(H)|\leq\lfloor(2\nu(H)+1)d/2\rfloor=\nu(H)d+\lfloor d/2\rfloor.$

Hence, by using $m=t+\nu(H)$, we get

$|E(G)|\leq dt+(\nu(H)d+\lfloor d/2\rfloor)=dm+\lfloor d/2\rfloor,$

which completes the proof. ∎

In the sequel, we will reformulate our problem in a slightly different way to
calculate $f_{\vartriangle}(d,m)$ for the case where $m>d$ and $d\leq 6$. This
reformulation will be revisited in Section 6 to suggest an integer programming
formulation and discuss future research directions for the remaining open
cases in Section 6.

Let us take a graph $G\in\mathcal{G}_{\vartriangle}(d,m)$ for some natural
numbers $1\leq d\leq m$. For any connected component of $G$ that is not a
$d$-star, say $H$, we know $d\leq\nu(H)\leq Z(d)$ and
$|E(H)|=f_{\vartriangle}(d,\nu(H))$ by Corollary 3.5 and Lemma 4.5. Then, let
$x_{i}$ be the number of connected components of $G$ whose matching number is
$i$ where $d\leq i\leq Z(d)$. Clearly, we have
$\displaystyle{\sum_{i=d}^{Z(d)}ix_{i}\leq m}$, and $G$ has
$\displaystyle{m-\sum_{i=d}^{Z(d)}ix_{i}}$ many connected components that are
$d$-stars. Therefore, we can write the number of edges in $G$ in terms of
$x_{i}$’s as follows:

$\displaystyle f_{\vartriangle}(d,m)=|E(G)|$ $\displaystyle=$ $\displaystyle
d\Big{(}m-\sum_{i=d}^{Z(d)}ix_{i}\Big{)}+\sum_{i=d}^{Z(d)}f_{\vartriangle}(d,i)x_{i}$
$\displaystyle=$ $\displaystyle
dm-\sum_{i=d}^{Z(d)}dix_{i}+\sum_{i=d}^{Z(d)}f_{\vartriangle}(d,i)x_{i}$
$\displaystyle=$ $\displaystyle
dm+\sum_{i=d}^{Z(d)}(f_{\vartriangle}(d,i)-di)x_{i}.$

As a result, for a fixed $d$, we can determine the value of
$f_{\vartriangle}(d,m)$ for all natural numbers $m$ by finding the values of
$f_{\vartriangle}(d,i)$ and corresponding $x_{i}$ values only for $d\leq i\leq
Z(d)$. For a simpler notation, let us define

$\displaystyle\mathcal{F}(d,m)$ $\displaystyle:=$
$\displaystyle\Big{\\{}\big{(}x_{d},x_{d+1},\ldots,x_{Z(d)}\big{)}:x_{i}\in\mathbb{Z}_{\geq
0}\text{ for }d\leq i\leq Z(d),\sum_{i=d}^{Z(d)}ix_{i}\leq m\Big{\\}},$
$\displaystyle g_{\vartriangle}(d,i)$ $\displaystyle:=$ $\displaystyle
f_{\vartriangle}(d,i)-di\text{ for any }i.$

Observe that we have $g_{\vartriangle}(d,d)=1$ for $d\geq 2$ by Theorem 3.4.
Also, we get $g_{\vartriangle}(d,Z(d))=\lfloor d/2\rfloor$ for $d\geq 2$ by
Theorem 4.8. Now, we state the discussion above as a lemma since it will be
used in the calculations for the cases $2\leq d\leq 6$.

######  Lemma 4.9.

For all natural numbers $1\leq d\leq m$, we have

$g_{\vartriangle}(d,m)=\max_{(x_{d},\ldots,x_{Z(d)})\in\mathcal{F}(d,m)}\sum_{i=d}^{Z(d)}g_{\vartriangle}(d,i)x_{i}.$

Notice that we have $Z(d)=d$ for $d\in\\{2,3\\}$ and $Z(d)=d+1$ for
$d\in\\{4,5,6\\}$ by Lemmas 4.6 and 4.7. Therefore, we have a simple
expression for $\mathcal{F}(d,m)$ for $2\leq d\leq 6$, which helps to find the
exact value of $f_{\vartriangle}(d,m)$.

######  Theorem 4.10.

With the preceding notation, for $m>d$ and $d\in\\{2,3\\}$,

$f_{\vartriangle}(d,m)=dm+\lfloor m/d\rfloor\lfloor d/2\rfloor.$

###### Proof.

Since $d=Z(d)$ for $d\in\\{2,3\\}$ by Lemma 4.6, $\mathcal{F}(d,m)$ contains
only $1$-dimensional elements, so we get
$\mathcal{F}(d,m)=\\{x_{d}\in\mathbb{Z}_{\geq 0}:dx_{d}\leq
m\\}=\\{x_{d}\in\mathbb{Z}_{\geq 0}:x_{d}\leq\lfloor m/d\rfloor\\}.$ Then, we
have

$g_{\vartriangle}(d,m)=\max_{x_{d}\in\mathcal{F}(d,m)}g_{\vartriangle}(d,d)x_{d}=g_{\vartriangle}(d,d)\lfloor
m/d\rfloor$

by Lemma 4.9. As we have already inferred from Theorem 4.8 that
$g_{\vartriangle}(d,d)=g_{\vartriangle}(d,Z(d))=\lfloor d/2\rfloor$, we get

$f_{\vartriangle}(d,m)-dm=g_{\vartriangle}(d,m)=\lfloor d/2\rfloor\lfloor
m/d\rfloor,$

and the result follows. ∎

######  Theorem 4.11.

With the preceding notation, for $m>d$ and $d\in\\{4,5,6\\}$ we have,

$f_{\vartriangle}(d,m)=\begin{cases}1+dm+\lfloor d/2\rfloor\lfloor
m/(d+1)\rfloor,&\text{if }m+1\text{ is divisible by }d+1,\\\ dm+\lfloor
d/2\rfloor\lfloor m/(d+1)\rfloor,&\text{otherwise}.\\\ \end{cases}$

###### Proof.

Let $d\in\\{4,5,6\\}$. Since $Z(d)=d+1$ by Lemmas 4.6 and 4.7,
$\mathcal{F}(d,m)$ contains 2-dimensional elements, and we get

$\mathcal{F}(d,m)=\\{(x_{d},x_{d+1})\in\mathbb{Z}_{\geq
0}^{2}:x_{d}\leq(m-(d+1)x_{d+1})/d\\}.$

On the other hand, we have

$g_{\vartriangle}(d,m)=\max_{(x_{d},x_{d+1})\in\mathcal{F}(d,m)}g_{\vartriangle}(d,d)x_{d}+g_{\vartriangle}(d,d+1)x_{d+1}$

by Lemma 4.9. Since $g(d,d)=1$ and $g(d,d+1)=g(d,Z(d))=\lfloor d/2\rfloor$, we
can write

$\displaystyle g_{\vartriangle}(d,m)$ $\displaystyle=$
$\displaystyle\max_{(x_{d},x_{d+1})\in\mathcal{F}(d,m)}(x_{d}+\lfloor
d/2\rfloor x_{d+1})$ $\displaystyle=$ $\displaystyle\max_{0\leq x_{d+1}\leq
m/(d+1)}\lfloor(m-(d+1)x_{d+1})/d\rfloor+\lfloor d/2\rfloor x_{d+1}$
$\displaystyle=$ $\displaystyle\max_{0\leq x_{d+1}\leq
m/(d+1)}\lfloor(m-x_{d+1})/d\rfloor+\lfloor(d-2)/2\rfloor x_{d+1}.$

Since $\lfloor(d-2)/2\rfloor\geq 1$, the quantity
$\lfloor(m-x_{d+1})/d\rfloor+\lfloor(d-2)/2\rfloor x_{d+1}$ increases with
respect to $x_{d+1}$. Therefore, $g_{\vartriangle}(d,m)$ is obtained by
assigning $x_{d+1}=\lfloor m/(d+1)\rfloor$ which is the maximum possible value
for $x_{d+1}$. Then, by writing $m=(d+1)k+r$ for some $k,r\in\mathbb{Z}$ where
$k=\lfloor m/(d+1)\rfloor$ and $0\leq r\leq d$, we see that
$(x_{d},k)\in\mathcal{F}(d,m)$ implies $x_{d}\leq 1$ if $r=d$ and $x_{d}\leq
0$ otherwise as $x_{d}\leq(m-(d+1)x_{d+1})/d$. Note that $r=d$ is equivalent
to the case that $m+1$ is divisible by $d+1$. Therefore, the value
$g_{\vartriangle}(d,m)$ is attained at $x_{d}=1$, $x_{d+1}=k$ if $m+1$ is
divisible by $d+1$, and it is attained at $x_{d}=0$, $x_{d+1}=k$ otherwise. As
a result, we find

$g_{\vartriangle}(d,m)=\begin{cases}1+\lfloor d/2\rfloor\lfloor
m/(d+1)\rfloor,&\text{if }m+1\text{ is divisible by }d+1,\\\ \lfloor
d/2\rfloor\lfloor m/(d+1)\rfloor,&\text{otherwise},\\\ \end{cases}$

so the result follows. ∎

##  5 Main Result

We determined the value of $f_{\vartriangle}(d,m)$ for all the cases with
$d\geq m$ (Theorems 3.3 and 3.4), and for the cases $d<m$ with either
$Z(d)\leq m<2d$ (Theorem 4.8) or $d\leq 6$ (Theorems 4.10 and 4.11). It is
possible to summarize those findings in a single formula that we state as our
main result. Recall that $C_{d}$ is a (almost) $d$-regular triangle-free
factor-critical graph with matching number $Z(d)$ whose existence is
guaranteed by Proposition 4.3 and Corollary 4.4.

######  Theorem 5.1.

Let $d$ and $m$ be natural numbers with $d\geq 2$, and let $k$ and $r$ be non-
negative integers such that $m=kZ(d)+r$ with $0\leq r<Z(d)$. Then, for all the
cases with $d\geq m$, and for the cases $d<m$ with either $d\leq 6$ or
$Z(d)\leq m<2d$, we have

$f_{\vartriangle}(d,m)=\begin{cases}dm+k\lfloor d/2\rfloor&\text{if }r<d,\\\
dm+k\lfloor d/2\rfloor+r-d+1&\text{if }r\geq d,\end{cases}$ (*)

where a graph in $\mathcal{G}_{\vartriangle}(d,m)$ can be constructed as the
disjoint union of $k$ copies of $C_{d}$ and

  * (i)

$A_{d}$ if $r\geq d$,

  * (ii)

$r$ copies of $d$-stars if $r<d$.

###### Proof.

Let $m=kZ(d)+r$ for some non-negative integers $k$ and $r$ with $0\leq
r<Z(d)$. If $m<d$, then we find $k=0$ and $r=m$ since $Z(d)\geq d$ by Lemma
4.6, so (* ‣ 5.1) holds by Theorem 3.3. If $d=m\in\\{2,3\\}$, then we get
$k=1$ and $r=0$ since $Z(d)=d$ by Lemma 4.6. Since $\lfloor d/2\rfloor=1$, (*
‣ 5.1) holds by Theorem 3.4. If $d=m\geq 4$, then we get $k=0$ and $r=d$ since
$Z(d)=d+1$ by Lemma 4.6. Since $r-d+1=1$, (* ‣ 5.1) holds by Theorem 3.4.
Suppose $d<m$. If $d\in\\{2,3\\}$, then we get $Z(d)=d$, which implies
$k=\lfloor m/d\rfloor$ and $r<d$, so (* ‣ 5.1) holds by Theorem 4.10. If
$d\in\\{4,5,6\\}$, then we get $Z(d)=d+1$, which implies $k=\lfloor
m/(d+1)\rfloor$. Moreover, we find $r=d$ if $m+1$ is divisible by $k+1$ and
$r<d$ otherwise. Therefore, if $m+1$ is divisible by $k+1$ then $r-d+1=1$, so
(* ‣ 5.1) holds by Theorem 4.11. Finally, if $Z(d)\leq m<2d$, then since
$d\leq Z(d)$ we have $m<2Z(d)$, thus $k=1$ and $r<d$, then (* ‣ 5.1) holds by
Theorem 4.8. ∎

Now, we can report the difference between $f_{\mathcal{GEN}}(d,m)$ and
$f_{\vartriangle}(d,m)$ based on our findings. Theorems 2.1 and 5.1 give

$h_{\vartriangle}(d,m):=f_{\mathcal{GEN}}(d,m)-f_{\vartriangle}(d,m)=\left\lfloor\frac{d}{2}\right\rfloor\Bigg{(}\left\lfloor\frac{m}{\lceil\frac{d}{2}\rceil}\right\rfloor-k\Bigg{)}-(r-d+1),$

where $m=kZ(d)+r$ with $0\leq r<Z(d)$ provided that $d$ and $m$ satisfy one of
the following conditions:

  * (i)

$d\geq m$,

  * (ii)

$d<m$ and $d\leq 6$,

  * (iii)

$d<m$ and $Z(d)\leq m<2d$.

The difference $h_{\vartriangle}(d,m)$ corresponds to the number of edges that
we loose in the triangle-free case as compared to the general one. Thus, we
get the following where we observe that apart from two simple cases (where
$m<\lfloor d/2\rfloor$ or $1=d<m$), we loose edges (with respect to the
general case) by restricting the extremal graphs to be triangle-free:

$h_{\vartriangle}(d,m)=\begin{cases}0,&\text{if }m<\lfloor d/2\rfloor,\\\
\lfloor d/2\rfloor,&\text{if }\lfloor d/2\rfloor\leq m<d\\\ d,&\text{if
}d=m\text{ and $d$ is even},\\\ \lfloor d/2\rfloor,&\text{if }d=m\text{ and
$d$ is odd},\\\ 0,&\text{if $1=d<m$,}\\\ m-\lfloor m/2\rfloor,&\text{if
$2=d<m$,}\\\ \lfloor m/2\rfloor-\lfloor m/3\rfloor,&\text{if $3=d<m$,}\\\
2\lfloor m/2\rfloor-2\lfloor m/5\rfloor,&\text{if $4=d<m$ and $m+1$ is not
divisible by 5,}\\\ 2\lfloor m/2\rfloor-2\lfloor m/5\rfloor-1,&\text{if
$4=d<m$ and $m+1$ is divisible by 5,}\\\ 2\lfloor m/3\rfloor-2\lfloor
m/6\rfloor,&\text{if $5=d<m$ and $m+1$ is not divisible by 6,}\\\ 2\lfloor
m/3\rfloor-2\lfloor m/6\rfloor-1,&\text{if $5=d<m$ and $m+1$ is divisible by
6,}\\\ 3\lfloor m/3\rfloor-3\lfloor m/7\rfloor,&\text{if $6=d<m$ and $m+1$ is
not divisible by 7,}\\\ 3\lfloor m/3\rfloor-3\lfloor m/7\rfloor-1,&\text{if
$6=d<m$ and $m+1$ is divisible by 7,}\\\ \lfloor d/2\rfloor,&\text{if $d\geq
7$ and $Z(d)\leq m<3\lceil d/2\rceil$,}\\\ 2\lfloor d/2\rfloor,&\text{if
$d\geq 7$ and $3\lceil d/2\rceil\leq m<2d$.}\par\end{cases}$

In light of Theorem 5.1, the remaining open cases are for $7\leq d<m$, and
either $m<Z(d)$ or $m\geq 2d$. In what follows, we will discuss further
formulations to solve these remaining cases and suggest some conjectures.

##  6 An integer programming formulation and further discussions

To solve the open cases, namely for natural numbers $m$ and $d$ such that
$7\leq d<m$ with either $m<Z(d)$ or $m\geq 2d$, we develop an integer
programming formulation based on our earlier observations. In Conjecture 6.1,
we provide all the parameters involved in this formulation, which is already a
challenging problem. Then, under the assumption that Conjecture 6.1 holds, we
show that our integer program admits an optimal solution with a special
structure. This, in turn, allows us to formulate in Conjecture 6.4 that
Theorem 5.1 is valid for all $m$ and $d$. Lastly, we also conjecture unknown
values of $Z(d)$ (see Lemma 4.7), which plays a crucial role in the solution
of our problem. We conclude our paper with a reformulation of our problem as a
variant of the well-known extremal problem addressed in Turan’s Theorem.

By Corollary 3.5 and Lemma 4.5, there is an edge-extremal graph
$G\in\mathcal{G}_{\vartriangle}(d,m)$ whose components are either $d$-stars,
or edge-extremal factor-critical triangle-free graphs $H$ where
$d\leq\nu(H)\leq Z(d)$. In other words, by letting $x_{i}$ to be the number of
connected components of $G$ whose matching number is $i$, we have (as
expressed in Lemma 4.9 in terms of $g_{\vartriangle}(d,m)$):

$f_{\vartriangle}(d,m)=d\Big{(}m-\sum_{i=d}^{Z(d)}ix_{i}\Big{)}+\sum_{i=d}^{Z(d)}f_{\vartriangle}(d,i)x_{i}=dm+\sum_{i=d}^{Z(d)}(f_{\vartriangle}(d,i)-di)x_{i}.$

It follows that, for a fixed $d$, the value of $f_{\vartriangle}(d,m)$ can be
determined for all natural numbers $m$ by finding the values of
$f_{\vartriangle}(d,i)$ and corresponding $x_{i}$ values only for $d\leq i\leq
Z(d)$. Accordingly, $f_{\vartriangle}(d,m)$ can be computed as the optimal
value of the following integer programming:

This formulation can be seen as a bounded knapsack problem where there is a
bounded number of items of each type. The utilities of the items are
$(f_{\vartriangle}(d,i)-di)$ for $d\leq i\leq Z(d)$ and the volumes of the
items range from $d$ to $Z(d)$ which is yet unknown if $d$ is odd (see Lemma
4.7).

Recall that we have $f_{\vartriangle}(d,d)=d^{2}+1$ for $d\geq 2$ by Theorem
3.4, and $f_{\vartriangle}(d,Z(d))=dZ(d)+\lfloor d/2\rfloor$ for $d\geq 2$ by
Theorem 4.8. It remains to compute $f_{\vartriangle}(d,i)$ for $d<i<Z(d)$. We
suggest Conjecture 6.1 for the value of $f_{\vartriangle}(d,i)$ for
$d<i<Z(d)$, which in turn, allows us to conjecture that the formula for
$f_{\vartriangle}(d,m)$ in Theorem 5.1 can be extended to all the remaining
cases as well (in Conjecture 6.4). Lastly, bearing in mind that the formula
giving the value of $f_{\vartriangle}(d,m)$ can only be computed if $Z(d)$ is
known; we suggest Conjecture 6.5 to settle the values of $Z(d)$ for odd $d\geq
21$, which is left open (see Lemma 4.7).

In what follows, we conjecture that for $d<i<Z(d)$, $f_{\vartriangle}(d,i)$
follows the same trend as what we identified in other cases.

######  Conjecture 6.1.

Theorem 5.1 holds also for $7\leq d<m<Z(d)$. In other words, for $7\leq
d<i<Z(d)$, we have

$f_{\vartriangle}(d,i)=di+i-d+1.$

If Conjecture 6.1 holds, then we get $f_{\vartriangle}(d,i)-di=i-d+1$ for
$2\leq d\leq i<Z(d)$. Since $f_{\vartriangle}(d,Z(d))=dZ(d)+\lfloor
d/2\rfloor$ and the constant term $dm$ in the objective function does not
effect the optimal solution, Model 1 is equivalent to solve the following
optimization problem:

We claim that if Conjecture 6.1 holds, then Model 2 admits an optimal solution
with nice properties. First, we need a direct consequence of Conjecture 6.1.

######  Proposition 6.2.

If Conjecture 6.1 is true, then we have $Z(7)\in\\{8,9\\}$.

###### Proof.

We claim that $Z(7)$ is the smallest natural number $k$ satisfying
$f_{\vartriangle}(7,k)=7k+3$. Indeed, we know that
$f_{\vartriangle}(7,Z(d))=7Z(d)+3$ by Theorem 4.8. Now, suppose
$f_{\vartriangle}(7,k)=7k+3$ for some $k<Z(7)$. Then, we can take a graph
$G\in\mathcal{G}_{\vartriangle}(7,k)$ with $7k+3$ edges. By Corollary 3.5, we
know that each connected component $H$ of $G$ that is not a $7$-star is
factor-critical with $\nu(H)\geq 7$. Since $\nu(H)\leq k<Z(7)$, it follows
that $H$ is not almost $7$-regular, so $E(H)\leq((2\nu(H)+1)7-3)/2=7\nu(H)+2$.
By summing the number of edges over all connected components of $G$, we find
$7k+3=|E(G)|\leq 7k+2$, which is a contradiction. As a result, we have
$f_{\vartriangle}(7,k)<7k+3$ for $k<Z(d)$. Now, if Conjecture 6.1 holds and
$Z(7)\geq 10$, the above discussion implies that
$f_{\vartriangle}(7,9)=66<7\times 9+3$, which is a contradiction. Since
$Z(7)\geq 8$ by Lemma 4.6, the result follows.

∎

Now, we are ready to discuss the optimal solution to Model 2 that admits nice
properties.

######  Proposition 6.3.

If Conjecture 6.1 is true, then for $7\leq d<m<Z(d)$, Model 2 admits an
optimal solution with $\displaystyle{\sum_{i=d}^{Z(d)-1}x_{i}\leq 1}$, that is
where $x_{Z(d)}$ is maximized, and there is at most one other $x_{i}$ which is
1 (all the rest being zero).

###### Proof.

Let $(x_{d},x_{d+1},\ldots,x_{Z(d)-1},x_{Z(d)})$ be an optimal solution for
Model 2 with optimal value $opt$ and such that $x_{d}+x_{Z(d)}$ is maximal. We
first show that $x_{j}\leq 1$ for all $d<j<Z(d)$. Assume the contrary.

If $j\geq\dfrac{d+Z(d)}{2}$, then we can decrease $x_{j}$ by two, and increase
each of $x_{2j-Z(d)}$ and $x_{Z(d)}$ by one, which gives another feasible
solution for Model 2 with objective value $opt+(2j-Z(d)-d+1)+\lfloor
d/2\rfloor-2(j-d+1)=opt+\lfloor(3d-2)/2\rfloor-Z(d)$. Since we increased
$x_{d}+x_{Z(d)}$ by at least one, the new solution is not optimal by
assumption, thus we have $\lfloor(3d-2)/2\rfloor\leq Z(d)-1$. By Lemma 4.7, we
obtain $\lfloor 5(d+1)/4\rfloor\geq Z(d)\geq\lfloor 3d/2\rfloor$, which is a
contradiction for $d\geq 8$. On the other hand, for $d=7$, Proposition 6.2
implies that $Z(7)\leq 9$, which contradicts with $\lfloor(3d-2)/2\rfloor\leq
Z(d)-1$. As a result, if $j\geq\dfrac{d+Z(d)}{2}$, we have $x_{j}\leq 1$.

If $j<\dfrac{d+Z(d)}{2}$, then we can decrease $x_{j}$ by two, and increase
each one of $x_{d}$ and $x_{2j-d}$ by one, which would give a feasible
solution with the objective value $opt+1+(2j-d+1)-2(j-d+1)=opt$. Since we
increased $x_{d}+x_{Z(d)}$ by at least one, we get a contradiction. Therefore,
we have $x_{j}\leq 1$ for all $d<j<Z(d)$.

Now, suppose $x_{a}=x_{b}=1$ for some $d<a<b<Z(d)$. If $a+b\geq Z(d)+d$, then
let us decrease $x_{a}$ and $x_{b}$ by one, and increase $x_{a+b-Z(d)}$ and
$x_{Z(d)}$ by one. By this way, we get a feasible solution with the objective
value

$opt-(a-d+1)-(b-d+1)+(a+b-Z(d)-d+1)+\lfloor d/2\rfloor.$

Since we increased $x_{d}+x_{Z(d)}$ by at least one, we should have
$\lfloor(3d-2)/2\rfloor\leq Z(d)-1$ by the assumption. As similar to previous
cases, this inequality does not hold for $d\geq 7$. If $a+b<d+Z(d)$, then let
us decrease $x_{a}$ and $x_{b}$ by one, and increase $x_{d}$ and $x_{a+b-d}$
by one. By this way, we get a feasible solution with the objective value

$opt-(a-d+1)-(b-d+1)+1+((a+b-d)-d+1)=opt.$

Since we increased $x_{d}+x_{Z(d)}$ by at least one, we get a contradiction.
Therefore, we can say that $x_{j}\geq 1$ holds for at most one $j$ value with
$d<j<Z(d)$.

Now, if $x_{d}\geq 2$, let us decrease $x_{d}$ by two, and increase $x_{Z(d)}$
by 1. This yields a feasible solution with the objective value $opt-2+\lfloor
d/2\rfloor>opt$, which is a contradiction. Hence, we have $x_{d}\leq 1$. The
only remaining case is $x_{d}=1$ and there is exactly one $j$ value with
$x_{j}=1$, $d<j<Z(d)$.

Let us decrease $x_{d}$ and $x_{j}$ by one, and increase $x_{Z(d)}$ by one.
Then, we would get a feasible solution with the optimal value

$opt-1-(j-d+1)+\lfloor d/2\rfloor=opt+\lfloor(3d-4)/2\rfloor-j.$

If $\lfloor(3d-4)/2\rfloor=j$, then we can obtain the same optimal value with
$x_{d}=x_{j}=0$, so the result follows. Thus, we are done if we show the
inequality $\lfloor(3d-4)/2\rfloor\geq j$ for $d\geq 7$. For $d=7$, note that
$Z(7)\in\\{8,9\\}$ by Proposition 6.2. If $Z(7)=8$, then there are no $j$
values with $7<j<Z(7)$, so we are done. If $Z(7)=9$, then, we get $j=8$ and so
the equality is satisfied. For $d=8$, we know $Z(8)=10$ by Lemma 4.7, which
gives $j\leq 9$ and so $\lfloor(3d-4)/2\rfloor-j>0$. For $d\geq 9$, by using
Lemma 4.7, we have

$\lfloor(3d-4)/2\rfloor\geq\lfloor(5d+1)/4\rfloor\geq Z(d)-1\geq j,$

which completes the proof. ∎

Proposition 6.3 can be interpreted as follows: under the assumption that
Conjecture 6.1 holds, one can reach $f_{\vartriangle}(d,m)$ edges by taking
the graph $C_{d}$ as much as possible and adding either one more graph that is
extremal for $f_{\vartriangle}(d,r)$ or $r$ many stars, depending on $r\geq d$
where $r$ is the remainder of $m$ when divided by $Z(d)$. Notice that this is
exactly how we construct an extremal graph in Theorem 5.1. Therefore, the
formula in Theorem 5.1 would be valid for all integers $d$ and $m$ if
Conjecture 6.1 is true:

######  Conjecture 6.4.

Let $m=kZ(d)+r$ for some $0\leq r<Z(d)$. Then, we have

$f_{\vartriangle}(d,m)=\begin{cases}dm+k\lfloor d/2\rfloor&\text{if }r<d\\\
dm+k\lfloor d/2\rfloor+r-d+1&\text{if }r\geq d.\end{cases}$

Our next conjecture is about the value of $Z(d)$ which plays a crucial role in
the computation of $f_{\vartriangle}(d,m)$ and the construction of extremal
graphs. Recall that Lemma 4.6 together with Lemma 4.7 give $Z(d)=\lfloor
5d/4\rfloor$ if $d$ is even or $d\in\\{3,5\\}$; moreover there is a narrow
interval for possible values of $Z(d)$ in the remaining cases (that is $d\geq
7$ odd). In [12], it is stated that every triangle-free graph $G$ with
$\delta(G)>3|V(G)|/8$ is a subgraph of a blow-up of the cycle of length five.
For odd values of $d$, since the graphs $C_{d}$ realizing $Z(d)$ are triangle-
free, almost regular, and factor-critical (by the definition of $Z(d)$), we
have $\delta(C_{d})\geq d-2$ and $|V(C_{d})|=2Z(d)+1\leq 2\lfloor
5(d+1)/4\rfloor+1$ by Lemma 4.7. Since $d-2>3(2\lfloor 5(d+1)/4\rfloor+1)/8$
for all but a few small values of $d$, this result implies that these $C_{d}$
graphs should be blow-up graphs of the cycle of length 5 provided that $d$ is
sufficiently large. We could show for some cases that if $Z(d)<\lfloor
5(d+1)/4\rfloor$ then it is not possible to construct $C_{d}$ which is the
blow-up of a cycle of length 5 and (almost) regular with degree $d$; thus
$Z(d)=\lfloor 5(d+1)/4\rfloor$ for these cases. We believe that this also
holds for the remaining cases if $d$ is large enough, which we formulate as a
conjecture:

######  Conjecture 6.5.

For $d\geq 21$ and odd, we have $Z(d)=\lfloor 5(d+1)/4\rfloor$.

Last but not least, let us reformulate the computation of
$f_{\vartriangle}(d,i)$ for $d\leq i\leq Z(d)$ as a generalized version of
Erdős-Stone’s Theorem which has been described as a fundamental theorem of
extremal graph theory (see [6]). The extremal number $\text{ex}(n,H)$ is
defined as the maximum number of edges in a graph on $n$ vertices not
containing a subgraph isomorphic to $H$. Note that the classical Turan’s
Theorem [14] addresses the answer for $\text{ex}(n,K_{r})$. In our case, we
seek for the maximum number of edges in a triangle-free graph whose maximum
degree is also bounded by some parameter. Indeed, by Corollary 3.5 and Lemma
4.5, for a graph $G\in\mathcal{G}_{\vartriangle}(d,m)$, every connected
component of $G$ which is not a $d$-star is a factor-critical edge-extremal
triangle-free graph with $f_{\vartriangle}(d,i)$ edges, thus with $2i+1$
vertices, where $d\leq i\leq Z(d)$. Hence, by forbidding not a single graph
$H$ but any graph in a family $\mathcal{F}$ in the Erdős-Stone’s Theorem, we
can write $f_{\vartriangle}(d,i)=\text{ex}(2i+1,\\{K_{3},K_{1,d}\\})$ for
$d\leq i\leq Z(d)$. It follows that we have reduced our original problem of
determining the maximum number of edges in a triangle-free graph with degree
and matching number bounds into determining
$\text{ex}(2i+1,\\{K_{3},K_{1,d}\\})$ for $d\leq i\leq Z(d)$. Let us conclude
by noting that Erdős-Stone’s Theorem investigates the asymptotic behavior of
$\text{ex}(n,\mathcal{F})$ whereas we seek for the exact value in the
particular case $\text{ex}(2i+1,\\{K_{3},K_{1,d}\\})$.

## References

  * [1] B. Andrásfai, P. Erdös, and V. T. Sós, On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Math. 8 (1974), 205–218.
  * [2] N. Balachandran and N. Khare, Graphs with restricted valency and matching number, Discrete Math. 309 (2009), 4176–4180.
  * [3] R. Belmonte, P. Heggernes, P. van ’t Hof, R. Saei, Ramsey numbers for line graphs and perfect graphs, In: COCOON ’12. pp. 204–215 (2012)
  * [4] J.R.S. Blair, P. Heggernes, P. T. Lima and D.Lokshtanov, On the maximum number of edges in chordal graphs of bounded degree and matching number, In Latin American Symposium on Theoretical Informatics, pp. 600-612. Springer, Cham, 2020.
  * [5] G. Brinkmann, K. Coolsaet, J. Goedgebeur, H. Mélot, House of Graphs: a database of interesting graphs, Discrete Appl. Math. 161(1-2) (2013), 311-314. Available at http://hog.grinvin.org
  * [6] B. Bollobás, Modern Graph Theory, Graduate Texts in Mathematics 184, pp. 120. Springer-Verlag New York, 1998.
  * [7] V. Chvátal and D. Hanson, Degrees and matchings, J. Combin. Theory Ser. B 20 (1976), 128–138.
  * [8] C. Dibek, T. Ekim and P. Heggernes, Maximum number of edges in claw-free graphs whose maximum degree and matching number are bounded, Discrete Math. 340 (2017), 927–934.
  * [9] J. Edmonds, Maximum matching and a polyhedron with 0, $1$-vertices, J. Res. Nat. Bur. Standards Sect. B 69 (1965), 125–130.
  * [10] P. Erdős, R. Rado, Intersection theorems for systems of sets, J. Lond. Math. Soc. 35 (1960), 85–90.
  * [11] T. Gallai, Neuer Beweis eines Tutte’schen Satzes, Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963), 135–139.
  * [12] R. Häggkvist, Odd cycles of specified length in nonbipartite graphs, In Graph Theory (Cambridge, 1981), Vol. 62 of North-Holland Mathematics Studies, 1982, North-Holland, pp. 89–99.
  * [13] E. Måland, Maximum Number of Edges in Graph Classes under Degree and Matching Constraints. The University of Bergen, Norway, 2015.
  * [14] P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941), 436–452.
  * [15] V. G. Vizing, On an estimate of the chromatic class of a p-graph, (Russian) Diskret. Analiz. 3 (1964), 25–30.


* [70] Qi, W., Shen, Z. and Yi, Y. (2024). Large deviation principle for quasi-stationary distributions and multiscale dynamics of absorbed singular diffusions. Probab. Theory Related Fields 188 (1-2) 667–728.
  * [71] Quattropani, M. and Sau, F. (2023). Mixing of the averaging process and its discrete dual on finite-dimensional geometries. Ann. Appl. Probab. 33 (2) 1136–1171.
  * [72] Reiss, R. (1989). Approximate distributions of order statistics. With applications to nonparametric statistics. Springer Series in Statistics. Springer-Verlag New York.
  * [73] Sato, K. (1999). Lévy processes and infinitely divisible distributions. Cambridge University Press, Cambridge.
  * [74] Smith, A. (2019). The cutoff phenomenon for random birth and death chains. Random Structures Algorithms 50 (2) 287–321.
  * [75] Sweeting, T.J. (1986). On a converse to Scheffé’s theorem. Ann. Statist. 14 (3) 1252-1256.
  * [76] Vernier, E. (2020). Mixing times and cutoffs in open quadratic fermionic systems. SciPost Phys. 9 (049) 1–30.
  * [77] Villani, C. (2009). Optimal transport. Old and new. Grundlehren der mathematischen Wissenschaften 338. Springer-Verlag Berlin.


# Valley Hall edge solitons in a photonic graphene

Qian Tang  1 Boquan Ren  2 Victor O. Kompanets  3 Yaroslav V. Kartashov  3
Yongdong Li  2 and Yiqi Zhang2  1Ministry of Education Key Laboratory for
Nonequilibrium Synthesis and Modulation of Condensed Matter, Shaanxi Province
Key Laboratory of Quantum Information and Quantum Optoelectronic Devices,
School of Physics, Xi’an Jiaotong University, Xi’an 710049, China
2Key Laboratory for Physical Electronics and Devices of the Ministry of
Education & Shaanxi Key Lab of Information Photonic Technique, School of
Electronic Science and Engineering, Xi’an Jiaotong University, Xi’an 710049,
China
3Institute of Spectroscopy, Russian Academy of Sciences, Troitsk, Moscow,
108840, Russia<EMAIL_ADDRESS>
###### Abstract

We predict the existence and study properties of the valley Hall edge solitons
in a composite photonic graphene with a domain wall between two honeycomb
lattices with broken inversion symmetry. Inversion symmetry in our system is
broken due to detuning introduced into constituent sublattices of the
honeycomb structure. We show that nonlinear valley Hall edge states with
sufficiently high amplitude bifurcating from the linear valley Hall edge state
supported by the domain wall, can split into sets of bright spots due to
development of the modulational instability, and that such an instability is a
precursor for the formation of topological bright valley Hall edge solitons
localized due to nonlinear self-action and travelling along the domain wall
over large distances. Topological protection of the valley Hall edge solitons
is demonstrated by modeling their passage through sharp corners of the
$\Omega$-shaped domain wall.

††journal: oe††articletype: Research Article

##  1 Introduction

Topological insulators are considered as a new state of matter due to their
unique physical properties. In solid-state physics, where such insulators were
introduced initially, and where they are still under very active
investigation, electronic topological insulators posses forbidden gap in the
bulk, just like conventional insulators, but allow conductance on their
surface, even in the presence of considerable defects and disorder [1, 2]. The
origin of this effect is connected with the existence of the edge states in
the topological gap opening in the dispersion diagram in the momentum space.
These topologically protected entities are localized at the edge between two
topologically distinct materials. The notion of topological insulators over
the last decade was extended to diverse branches of physics, in particular to
various wave systems. Among them are photonic systems [3, 4, 5, 6, 7, 8, 9,
10, 11, 12], acoustic [13, 14, 15, 16, 17, 18], mechanical systems [19, 20],
ultra-cold atoms [21, 22], polaritons in microcavities [23, 24, 25], and
electrical circuits [26, 27, 28, 29, 30, 31]. The progress in “topological
photonics”, rapidly growing into independent research area, has been
summarized in several recent reviews [32, 33, 34, 35, 36, 37, 38, 39, 40, 41]
covering various aspects of light propagation in these unusual materials. Upon
the development of topological photonics, it has been realized that nonlinear
effects may be very important for the formation, manipulation, and control of
the topological edge states. Many interesting phenomena mediated by the
nonlinearity have been discovered in topological insulators. They include
various bistability effects for edge states in pumped dissipative systems [42,
43, 44], modulational instabilities of the nonlinear edge states [45, 46],
stabilization of operation of topological lasers due to nonlinear gain
saturation [47, 48, 49, 50, 51, 52, 53, 54], nonlinearity-induced topological
transitions [11], as well as rich variety of solitonic effects [55, 56, 57],
including the formation of self-sustained localized states in the bulk of
topological insulators [58, 10], nonlinear vortices [59], topological edge
solitons [60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71], or nonlinearity-
induced higher-order topological phases [72], to name a few.

Topological edge solitons were introduced as hybrid states that are affected
by both the topological nature of the system and the nonlinear self-action.
Their investigation was mostly limited to polaritonic systems with external
magnetic field [46, 62, 63, 44] and to waveguiding systems with longitudinal
refractive index modulations [60, 66, 69] serving to break time-reversal
symmetry of the system. At the same time, it is known that the appearance of
topological edge states in valley Hall systems does not require time-reversal
symmetry breaking and is associated instead with breakup of the inversion
symmetry of the system [the word “valley” is associated here with specific
features (presence of the local extrema) of bands of corresponding systems:
for example, when inversion symmetry of the underlying honeycomb lattice is
broken by detuning of two constituent sublattices, the gap opens between
former Dirac points and local extrema in two upper bands develop that are
called valleys]. The latter setting therefore can be realized without using
external magnetic fields or longitudinal system modulations, that are always
associated with losses. Even though valley Hall edge solitons were considered
previously in sophisticated lattice geometries possessing type-II Dirac cones
in the spectrum [70], the specific structure of the underlying lattice did not
allow illustration of their topological protection. Such states, bifurcating
from linear topological edge states at Bloch momenta yielding appropriate sign
of the group velocity dispersion, and their topological protection so far were
not considered at the domain walls between usual detuned honeycomb lattices
(used in the majority of experiments on linear valley Hall edge states), which
are much easier for experimental implementation.

In this paper, we report on valley Hall edge solitons forming at the domain
wall in conventional honeycomb waveguide array (a photonic graphene). We study
properties of the linear and nonlinear edge states at such domain walls and
present long-living topological edge solitons that demonstrate topological
protection upon passage through sharp bends of the domain wall. Our results
suggest experimentally straightforward approach to implementation of such
states.

In Fig. 1, we display a photonic array of straight waveguides with honeycomb
structure, consisting of two sublattices A and B. The refractive index
modulation depths ($\delta n_{\rm A}$ and $\delta n_{\rm B}$) in two
sublattices can be made slightly different (detuned), as shown by different
colors in Fig. 1. This results in the breakup of the inversion symmetry of the
array, disappearance of the Dirac cones in the spectrum, and opening of the
gap between them. It should be stressed that even though forbidden gap emerges
in the band structure, the Berry curvature $\Omega$ of the first and second
bulk bands satisfies the condition $\Omega(-{\bf k})=-\Omega({\bf k})$, which
indicates that the Chern numbers of the two upper bulk bands remain zero [73].
In this case six valleys appear in the spectrum, with three valleys around K
($\textbf{K}^{\prime}$) points being equivalent. Valley Chern number of a
specific valley is determined to be either $+1/2$ or $-1/2$. Moreover, if the
valley Chern number for a certain valley is $+1/2$ for the lattice with
$\delta n_{\rm A}>\delta n_{\rm B}$, then for the lattice with $\delta n_{\rm
A}<\delta n_{\rm B}$ the Chern number for the same valley will be equal to
$-1/2$ [74]. Thus, if one designs a composite honeycomb lattice with a domain
wall (highlighted by the red ellipse in Fig. 1) between two inversion-
symmetry-broken honeycomb lattices with opposite detunings, the valley Chern
numbers at both sides of the interface become opposite. In this case, bulk-
edge correspondence principle, applied to valley Hall system, predicts the
formation of the edge states localized on the domain wall and decaying in the
direction perpendicular to it. The appearance of such edge states is a
manifestation of the well-known valley Hall effect [75, 76, 77] and
corresponding edge states of topological origin are usually called valley Hall
edge states [78, 74, 79, 80].

Figure 1: Schematic configuration of honeycomb waveguide array with a domain
wall. Two sublattices are distinguished by different colors. Domain wall
between two honeycomb arrays with different detunings is highlighted by the
red ellipse.

##  2 Band structure and linear valley Hall edge state

The propagation of the valley Hall edge state along the longitudinal $z$ axis
of the waveguide array with focusing cubic nonlinearity can be described by
the nonlinear Schrödinger equation,

$i\frac{\partial\psi}{\partial
z}=-\frac{1}{2}\left(\frac{\partial^{2}}{\partial
x^{2}}+\frac{\partial^{2}}{\partial
y^{2}}\right)\psi-{\mathcal{R}}(x,y)\psi-|\psi|^{2}\psi,$ (1)

where $\psi$ is the dimensionless field amplitude, $x$ and $y$ are the
normalized transverse coordinates, and $z$ is the normalized propagation
distance, the function $\cal R$ stands for the refractive index distribution
in the honeycomb array that is independent of the longitudinal coordinate $z$.
The profiles of individual waveguides in the array can be described by
Gaussian functions of width $\sigma$: ${\mathcal{R}}(x,y)=p_{\rm
A,B}\sum_{m,n}e^{-[(x-x_{m,n})^{2}+(y-y_{m,n})^{2}]/\sigma^{2}}$, where
$p_{\rm A,B}\sim\delta n_{\textrm{A,B}}$ stand for the depths of waveguides in
two sublattices, and $(x_{m,n},y_{m,n})$ are the coordinates of the nodes in
the honeycomb grid. We consider a configuration that is periodic along the $y$
axis and is limited along the $x$-axis with outer boundaries located far away
from the domain wall, so that ${\mathcal{R}}(x,y)={\mathcal{R}}(x,y+L)$ with
$L=\sqrt{3}a$ and $a$ being the array constant. As a representative parameter
values we choose $a=1.4$ and $\sigma=0.5$. The average refractive index
modulation depth is set to be $p_{\rm in}=10.3$, while the detuning
$\delta=0.55$. For the honeycomb array on the left side of the domain wall in
Fig. 1 we set $p_{\rm A}=p_{\rm in}+\delta$ and $p_{\rm B}=p_{\rm in}-\delta$,
while for the array on the right side of the domain wall we assume inverted
detuning, so that $p_{\rm A}=p_{\rm in}-\delta$ and $p_{\rm B}=p_{\rm
in}+\delta$. The domain wall emerging between these two arrays that we
consider here is characterized by the reduced refractive index for all sites,
see red ellipse in Fig. 1. Normalized parameters described above correspond to
the following real physical values in waveguide arrays inscribed in fused
silica with femtosecond laser pulses [3, 8, 10, 11, 81, 82] if laser radiation
at the wavelength of $800~{}\rm nm$ is used and characteristic transverse
scale is set to $10~{}\mu\rm m$, that corresponds to dimensionless coordinates
$x,y=1$. In this case the array constant is $14~{}\mu\rm m$, waveguide width
is $5~{}\mu\rm m$, and $p_{\rm in}=10.3$ corresponds to the refractive index
modulation depth of $\sim 1.1\times 10^{-3}$.

Figure 2: (a) Band structure of the photonic graphene with a domain wall. The
black curves are the bulk states, while the red curve is the valley Hall edge
state. (b) First-order $\beta^{\prime}$ and second-order
$\beta^{\prime\prime}$ derivatives of the propagation constant of the valley
Hall edge state. (c) Exemplary profiles of the valley Hall edge states with
the Bloch momenta displayed in the right-bottom corner. These profiles
correspond to the red and green dots in (a). The states are shown within the
window $-20\leq x\leq 20$ and $-9.1\leq y\leq 9.1$.

We obtained the bandgap structure of the composite array with a domain wall by
substituting the solution $\psi(x,y,z)=u(x,y)e^{ik_{y}y+i\beta z}$ into linear
counterpart of Eq. (1). Here $u(x,y)=u(x,y+L)$ is the periodic Bloch wave
function, $k_{y}\in[-{\rm K}_{y}/2,{\rm K}_{y}/2)$ is the Bloch momentum in
the first Brillouin zone with ${\rm K}_{y}=2\pi/L$, and $\beta$ is the
propagation constant of the linear mode that is a function of $k_{y}$. Using
plane-wave expansion method we obtained the bandgap structure shown in Fig.
2(a), in which the bulk states are indicated by the black lines and the in-gap
valley Hall edge state is indicated by the red line. To better understand
properties of the edge state, we also display the first-order
$\beta^{\prime}=d\beta/dk_{y}$ (solid line) and second-order
$\beta^{\prime\prime}=d^{2}\beta/dk_{y}^{2}$ (dashed line) derivatives of the
propagation constant of the edge state in Fig. 2(b). The first-order
derivative $\beta^{\prime}$ provides the group velocity $v=-\beta^{\prime}$
with which edge state moves along the domain wall, while the second-order
derivative $\beta^{\prime\prime}$ quantifies the dispersion of the edge state
and allows to estimate, in particular, the rate of expansion along the domain
wall of the localized envelope, if it is superimposed on the edge state. As
shown in Fig. 2(b), $\beta^{\prime\prime}$ is negative in the entire Brillouin
zone which is necessary to obtain bright solitons. If the value is positive,
one obtains dark solitons [83]. In Fig. 2(c), we display two examples of the
linear valley Hall edge states corresponding to the red and greed dots in Fig.
2(a). The localization of the state at $k_{y}=-0.3{\rm K}_{y}$ with
propagation constant closer to the center of the gap (red dot) is much better
than that of the state at $k_{y}=-0.467{\rm K}_{y}$ taken close to the gap
edge (green dot). For both these $k_{y}$ values $\beta^{\prime}>0$ that
corresponds to the motion in the negative $y$ direction during propagation.
Notice that the same domain wall supports states propagating in the opposite
direction, since the valley Hall system is time-reversal symmetric, and there
must be a back-propagating state as the time-reversal conjugate of the
forward-propagating state. In the valley Hall system, the counter-propagating
states can hardly couple (such coupling is only possible under the action of
strong localized defects that couple two valleys, while smooth large-scale
perturbations do not couple them) making such systems beneficial in comparison
with topologically trivial waveguide arrays. In the following we consider
states with Bloch momentum $k_{y}=-0.3{\rm K}_{y}$, but point out that their
properties remain similar for other $k_{y}$ values.

##  3 Nonlinear valley Hall edge state and quasi-soliton

To obtain bright valley Hall edge solitons, we first calculate nonlinear
extension of the valley Hall edge states. To do this, we insert the ansatz
$\psi(x,y,z)=u(x,y)e^{ik_{y}y+i\mu z}$, where $\mu$ is the nonlinear
propagation constant shift, into nonlinear Eq. (1) that yields the equation

$\mu u=\frac{1}{2}\left(\frac{\partial^{2}}{\partial
x^{2}}+\frac{\partial^{2}}{\partial y^{2}}+2ik_{y}\frac{\partial}{\partial
y}-k_{y}^{2}\right)u+\mathcal{R}(x,y)u+|u|^{2}u,$ (2)

which can be solved by using Newton method for a given nonlinear propagation
constant shift $\mu$ that lies in the interval $\beta_{\rm
li}\leq\mu\leq\beta_{\rm ge}$. Here, $\beta_{\rm li}\approx 3.473$ is the
propagation constant of the linear valley Hall edge state at $k_{y}=-0.3{\rm
K}_{y}$ [see the red dot in Fig. 2(a)], while $\beta_{\rm ge}\approx 3.832$ is
the propagation constant corresponding to the top edge of the gap for the same
Bloch momentum $k_{y}$. The peak amplitude $a$ (solid curve) and power per one
$y$-period of the structure
$P=\int_{-\infty}^{+\infty}\int_{0}^{L}|\psi|^{2}dxdy$ (red curve) for the
nonlinear valley Hall edge state family are shown in Fig. 3(a). They both
monotonously increase with increasing nonlinear propagation constant shift
$\mu$ and they vanish exactly in the point, where nonlinear edge state family
bifurcates from the linear family. Amplitude profiles $|u|$ of two
representative nonlinear edge states with $\mu=3.516$ and $\mu=3.8$,
corresponding respectively to the black and red dots in Fig. 3(a), are shown
in Fig. 3(b). Since the state indicated by the red dot is much closer to the
top edge of the gap, its localization is worse than that of the state
corresponding to the black dot. We choose the state corresponding to the black
dot with $\mu=3.516$ and investigate its modulational instability by adding a
perturbation into its initial profile that is $\sim\nu\cos(\omega y)$, with
$\nu=0.01$ and $\omega$ being the amplitude and the frequency, respectively.
Such small perturbations experience clear exponential growth at the initial
stage of instability development as long as modulation frequency $\omega$ is
within the modulational instability band. The dependence of the perturbation
growth rate $\delta$ on frequency $\omega$ can be easily obtained from direct
simulations of propagation, as shown in Fig. 3(c). The dependence
$\delta(\omega)$ unveils that the modulation instability bandwidth is finite.

Figure 3: (a) Peak amplitude (black curve; left vertical axis) and power (red
curve; right vertical axis) of the nonlinear valley Hall edge state as a
function of nonlinear propagation constant shift $\mu$. (b) Examples of
profiles of the nonlinear valley Hall edge states for $\mu$ values displayed
in the right-bottom corner and corresponding to the black and red dots in (a).
The states are shown within the window $-20\leq x\leq 20$ and $-9.1\leq y\leq
9.1$. (c) Growth rate $\delta$ of the small perturbation added to the
nonlinear edge state with $\mu=3.516$ versus frequency of the perturbation
$\omega$.

Next we consider dynamics of propagation of the nonlinear edge states. We are
interested mostly in the edge states with not too small peak amplitudes (or
their behavior will be close to that of linear edge states) that exhibit
relatively fast decay in the course of propagation due to the development of
modulational instability. For example, one can choose the same nonlinear edge
state, whose modulation instability is studied in Fig. 3(c). To illustrate the
development of modulational instability, one can introduce the periodic
perturbation as adopted in Fig. 3(c). Besides, one can also perturb the
nonlinear valley Hall edge state by a random $5\%$-amplitude noise i.e.,
consider input in the form $\psi(x,y)[1+\delta(x,y)]$, where $\delta(x,y)$ is
a random number uniformly distributed within the segment $[-0.05,+0.05]$ and
propagate it in the structure containing $200$ $y$-periods, as shown in Fig.
4(a). The amplitude profiles shown at different propagation distances reveal
the development of modulational instability, which results in breakup of the
wave into multiple bright spots — precursors of bright solitons, whose
formation is possible in this system due to focusing nonlinearity and
appropriate sign of the second-order dispersion $\beta^{\prime\prime}$. Notice
that instability development does not lead to dramatic radiation into the
bulk, i.e. nearly all power remains in the vicinity of the domain wall. The
peak amplitude $a$ of the nonlinear state during propagation is depicted in
Fig. 4(b). The red dot on this dependence corresponds to $z=210$ and to
sufficiently pronounced edge state modulations, as it follows from Fig. 4(a).

Figure 4: (a) Amplitude profiles $|\psi|$ with $\mu=3.516$ of the perturbed
propagating nonlinear valley Hall edge state at different propagation
distances. (b) Peak amplitude $a$ of the state versus propagation distance.
All states are shown within the window $-20\leq x\leq 20$ and $-121.2\leq
y\leq 121.2$.

To confirm that isolated bright spots emerging as a result of modulation
instability development indeed can give rise to stable valley Hall edge quasi-
solitons (here “quasi” means that such states still exhibit small radiative
losses during propagation, even though these losses are so weak that they do
not lead to noticeable decrease of peak amplitude even at $z\sim 10^{4}$, see
below), we selected one of such spots indicated by the green circle in Fig.
4(a) as an input state at $z=0$ in Fig. 5(a) and propagated it up to
$z=10^{4}$. The evolution of the peak amplitude $a_{\rm nlin}$ (black curve)
and integral center position $y_{c}=(\iint|\psi|^{2}dxdy)^{-1}\iint
y|\psi|^{2}dxdy$ of the emerged quasi-soliton during propagation is presented
in Fig. 5(c). One can see that after slight initial decrease, the peak
amplitude $a_{\rm nlin}$ of so constructed input exhibits only small
oscillations and does not decrease with distance, clearly indicating on the
fact that nonlinear self-action has compensated diffraction broadening for
this self-sustained state. The edge soliton moves along the $y$-axis in its
negative direction with constant velocity and in our case traverses $y$-window
(where we used periodic boundary conditions) multiple times, without any
signature of diffractive broadening. In Fig. 5(a), we also display amplitude
profiles of the quasi-soliton at different distances: they show that the
profile of the quasi-soliton remains nearly unchanged. We would like to note
that the input spot in Fig. 5(a) is not exactly the valley Hall edge soliton
solution and this is the reason for slight initial decrease of the peak
amplitude that corresponds to the stage at which wavepacket self-adjusts to
soliton shape. If nonlinearity in Eq. (1) is switched off, the same input
quickly and dramatically spreads in linear medium, extending along the domain
wall. This is illustrated in Fig. 5(b), where we show the output distribution
at $z=500$ after linear propagation, when it substantially extends along the
domain wall. In Fig. 5(c), we also show the corresponding peak amplitude
$a_{\rm lin}$ during linear propagation, but only within the region $z\leq
1000$. Further propagation will lead to the interference of the state due to
the limited size of the calculation window which affects the peak amplitude of
the state. Besides the method of generation of quasi-solitons adopted here
that utilizes modulation instability [46, 44, 70], one can also derive an
envelope equation for such solitons directly from Eq. (1) using the methods
developed for continuous topological systems in [66, 69].

Figure 5: (a) Long-range stable propagation dynamics of the valley Hall edge
quasi-soliton. (b) Profile for the same input after linear propagation at
$z=500$. (c) Peak amplitude (right axis) for nonlinear $a_{\rm nlin}$ (black
curve) and linear $a_{\rm lin}$ (blue curve) propagation regimes and integral
soliton center position $y_{c}$ in nonlinear regime (left axis) versus
propagation distance $z$. All amplitude distributions in (a) are shown within
the window $-20\leq x\leq 20$ and $-121.2\leq y\leq 121.2$.

##  4 Topological protection of the valley Hall edge soliton

One of the most representative properties of the topological edge states is
their topological protection. While certain small-scale modulations of the
domain wall may still cause backscattering in the valley Hall system,
topological solitons in this system can circumvent sharp corners without
backward reflection or radiation. Notice that in previously reported example
[70] of the nonlinear valley Hall system with type-II Dirac cones, the
specific geometry of the interface did not allow to illustrate this type of
dynamics. In contrast, topological protection can be easily visualized in our
system. We thus construct a domain wall with a $\Omega$-like shape, that
possesses 4 sharp corners (the angle is $60^{\circ}$), as shown by the blue
channel in Fig. 6(a). Since the lattice unit cell used in this work has $\rm
C_{3v}$ symmetry, the formation of such zigzag-type turns with an angle of
$60^{\circ}$ or $120^{\circ}$ is allowed. We use the same input as in Fig.
5(a) and check its propagation dynamics along the $\Omega$-shaped domain wall,
see Fig. 6(b). Presented results clearly show that soliton passes all sharp
corners in the domain wall without experiencing reflection. Notice that one of
the main advantages of our system is considerable width of the gap – hence all
obtained solitons have sufficiently large propagation velocities
$v=-\beta^{\prime}$ allowing them to pass through bends and corners over
sufficiently small propagation distances [thus, $z=200$ in Fig. 6(b) is of the
order of experimentally available sample length for laser-written waveguide
arrays]. An animation corresponding to the propagation in Fig. 6 is provided
in the Visualisation 1, that visually shows the topological protection.

Figure 6: (a) Inversion-symmetry-broken honeycomb lattice with a
$\Omega$-shaped domain wall (the blue channel). We indicate four corners of
this structure with numbers. (b) Amplitude profiles at different propagation
distances illustrating passage of soliton through all sharp bends of the
domain wall. All states are shown within the window $-53\leq x\leq 53$ and
$-121.2\leq y\leq 121.2$.

##  5 Conclusion

Summarizing, we have demonstrated valley Hall edge solitons in a composite
honeycomb lattice with broken inversion symmetry. We have shown that a domain
wall created in the composite honeycomb lattice supports edge states
originating from the valley Hall effect. Their nonlinear counterparts
bifurcating from the linear valley Hall edge states were obtained by using the
Newton method. We used modulational instability to demonstrate that such
nonlinear edge states split into sets of solitons, each of which can show
extremely long stable propagation along the domain wall. Finally, topological
protection was illustrated by considering interactions of valley Hall edge
solitons with $\Omega$-shaped domain walls. Our work suggests experimentally
feasible approach to generation of topological edge solitons that does not
rely on longitudinal array modulations leading to enhanced losses. Our results
may be generalized to other platforms where nontrivial topology can be
combined with nonlinear response of the system [84, 85, 55, 56, 57].

Funding National Natural Science Foundation of China (12074308, U1537210);
Russian Science Foundation (21-12-00096); Fundamental Research Funds for the
Central Universities (xzy012019038).

Disclosures The authors declare no conflicts of interest.

Data Availability Statement Data underlying the results presented in this
paper are not publicly available at this time but may be obtained from the
authors upon reasonable request.

## References

  * [1] M. Z. Hasan and C. L. Kane, “Colloquium: Topological insulators,” Rev. Mod. Phys. 82, 3045–3067 (2010).
  * [2] X.-L. Qi and S.-C. Zhang, “Topological insulators and superconductors,” Rev. Mod. Phys. 83, 1057–1110 (2011).
  * [3] M. C. Rechtsman, J. M. Zeuner, Y. Plotnik, Y. Lumer, D. Podolsky, F. Dreisow, S. Nolte, M. Segev, and A. Szameit, “Photonic Floquet topological insulators,” Nature 496, 196–200 (2013).
  * [4] F. D. M. Haldane and S. Raghu, “Possible realization of directional optical waveguides in photonic crystals with broken time-reversal symmetry,” Phys. Rev. Lett. 100, 013904 (2008).
  * [5] Z. Wang, Y. Chong, J. D. Joannopoulos, and M. Soljačić, “Observation of unidirectional backscattering-immune topological electromagnetic states,” Nature 461, 772–775 (2009).
  * [6] N. H. Lindner, G. Refael, and V. Galitski, “Floquet topological insulator in semiconductor quantum wells,” Nat. Phys. 7, 490–495 (2011).
  * [7] M. Hafezi, E. A. Demler, M. D. Lukin, and J. M. Taylor, “Robust optical delay lines with topological protection,” Nat. Phys. 7, 907–912 (2011).
  * [8] S. Stützer, Y. Plotnik, Y. Lumer, P. Titum, N. H. Lindner, M. Segev, M. C. Rechtsman, and A. Szameit, “Photonic topological Anderson insulators,” Nature 560, 461–465 (2018).
  * [9] Y. Yang, Z. Gao, H. Xue, L. Zhang, M. He, Z. Yang, R. Singh, Y. Chong, B. Zhang, and H. Chen, “Realization of a three-dimensional photonic topological insulator,” Nature 565, 622–626 (2019).
  * [10] S. Mukherjee and M. C. Rechtsman, “Observation of Floquet solitons in a topological bandgap,” Science 368, 856–859 (2020).
  * [11] L. J. Maczewsky, M. Heinrich, M. Kremer, S. K. Ivanov, M. Ehrhardt, F. Martinez, Y. V. Kartashov, V. V. Konotop, L. Torner, D. Bauer, and A. Szameit, “Nonlinearity-induced photonic topological insulator,” Science 370, 701–704 (2020).
  * [12] Z. Yang, E. Lustig, Y. Lumer, and M. Segev, “Photonic Floquet topological insulators in a fractal lattice,” Light Sci. Appl. 9, 128 (2020).
  * [13] Z. Yang, F. Gao, X. Shi, X. Lin, Z. Gao, Y. Chong, and B. Zhang, “Topological acoustics,” Phys. Rev. Lett. 114, 114301 (2015).
  * [14] Y.-G. Peng, C.-Z. Qin, D.-G. Zhao, Y.-X. Shen, X.-Y. Xu, M. Bao, H. Jia, and X.-F. Zhu, “Experimental demonstration of anomalous Floquet topological insulator for sound,” Nat. Commun. 7, 13368 (2016).
  * [15] C. He, X. Ni, H. Ge, X.-C. Sun, Y.-B. Chen, M.-H. Lu, X.-P. Liu, and Y.-F. Chen, “Acoustic topological insulator and robust one-way sound transport,” Nat. Phys. 12, 1124–1129 (2016).
  * [16] J. Lu, C. Qiu, L. Ye, X. Fan, M. Ke, F. Zhang, and Z. Liu, “Observation of topological valley transport of sound in sonic crystals,” Nat. Phys. 13, 369–374 (2017).
  * [17] X. Zhang, M. Xiao, Y. Cheng, M.-H. Lu, and J. Christensen, “Topological sound,” Commun. Phys. 1, 97 (2018).
  * [18] G. Ma, M. Xiao, and C. T. Chan, “Topological phases in acoustic and mechanical systems,” Nat. Rev. Phys. 1, 281–294 (2019).
  * [19] R. Süsstrunk and S. D. Huber, “Observation of phononic helical edge states in a mechanical topological insulator,” Science 349, 47–50 (2015).
  * [20] S. D. Huber, “Topological mechanics,” Nat. Phys. 12, 621–623 (2016).
  * [21] N. Goldman, J. Dalibard, A. Dauphin, F. Gerbier, M. Lewenstein, P. Zoller, and I. B. Spielman, “Direct imaging of topological edge states in cold-atom systems,” Proc. Natl. Acad. Sci. 110, 6736–6741 (2013).
  * [22] G. Jotzu, M. Messer, R. Desbuquois, M. Lebrat, T. Uehlinger, D. Greif, and T. Esslinger, “Experimental realisation of the topological Haldane model,” Nature 515, 237–240 (2014).
  * [23] A. V. Nalitov, D. D. Solnyshkov, and G. Malpuech, “Polariton $\mathbb{Z}$ topological insulator,” Phys. Rev. Lett. 114, 116401 (2015).
  * [24] P. St-Jean, V. Goblot, E. Galopin, A. Lemaître, T. Ozawa, L. Le Gratiet, I. Sagnes, J. Bloch, and A. Amo, “Lasing in topological edge states of a one-dimensional lattice,” Nat. Photon. 11, 651–656 (2017).
  * [25] S. Klembt, T. H. Harder, O. A. Egorov, K. Winkler, R. Ge, M. A. Bandres, M. Emmerling, L. Worschech, T. C. H. Liew, M. Segev, C. Schneider, and S. Höfling, “Exciton-polariton topological insulator,” Nature 562, 552–556 (2018).
  * [26] V. V. Albert, L. I. Glazman, and L. Jiang, “Topological properties of linear circuit lattices,” Phys. Rev. Lett. 114, 173902 (2015).
  * [27] Y. Hadad, J. C. Soric, A. B. Khanikaev, and A. Alù, “Self-induced topological protection in nonlinear circuit arrays,” Nat. Electron. 1, 178–182 (2018).
  * [28] S. Imhof, C. Berger, F. Bayer, J. Brehm, L. W. Molenkamp, T. Kiessling, F. Schindler, C. H. Lee, M. Greiter, T. Neupert, and R. Thomale, “Topolectrical-circuit realization of topological corner modes,” Nature Physics 14, 925–929 (2018).
  * [29] N. A. Olekhno, E. I. Kretov, A. A. Stepanenko, P. A. Ivanova, V. V. Yaroshenko, E. M. Puhtina, D. S. Filonov, B. Cappello, L. Matekovits, and M. A. Gorlach, “Topological edge states of interacting photon pairs emulated in a topolectrical circuit,” Nat. Commun. 11, 1436 (2020).
  * [30] T. Helbig, T. Hofmann, S. Imhof, M. Abdelghany, T. Kiessling, L. W. Molenkamp, C. H. Lee, A. Szameit, M. Greiter, and R. Thomale, “Generalized bulk-boundary correspondence in non-Hermitian topolectrical circuits,” Nat. Phys. 16, 747–750 (2020).
  * [31] R. Li, B. Lv, H. Tao, J. Shi, Y. Chong, B. Zhang, and H. Chen, “Ideal type-II Weyl points in topological circuits,” National Sci. Rev. 8, nwaa192 (2020).
  * [32] L. Lu, J. D. Joannopoulos, and M. Soljačić, “Topological photonics,” Nat. Photon. 8, 821–829 (2014).
  * [33] T. Ozawa, H. M. Price, A. Amo, N. Goldman, M. Hafezi, L. Lu, M. C. Rechtsman, D. Schuster, J. Simon, O. Zilberberg, and I. Carusotto, “Topological photonics,” Rev. Mod. Phys. 91, 015006 (2019).
  * [34] M. Kim, Z. Jacob, and J. Rho, “Recent advances in 2D, 3D and higher-order topological photonics,” Light Sci. Appl. 9, 130 (2020).
  * [35] D. Smirnova, D. Leykam, Y. Chong, and Y. Kivshar, “Nonlinear topological photonics,” Appl. Phys. Rev. 7, 021306 (2020).
  * [36] Y. Ota, K. Takata, T. Ozawa, A. Amo, Z. Jia, B. Kante, M. Notomi, Y. Arakawa, and S. Iwamoto, “Active topological photonics,” Nanophoton. 9, 547–567 (2020).
  * [37] D. Leykam and L. Yuan, “Topological phases in ring resonators: recent progress and future prospects,” Nanophoton. 9, 4473–4487 (2020).
  * [38] M. Segev and M. A. Bandres, “Topological photonics: Where do we go from here?” Nanophoton. 10, 425–434 (2021).
  * [39] M. Parto, Y. G. N. Liu, B. Bahari, M. Khajavikhan, and D. N. Christodoulides, “Non-Hermitian and topological photonics: optics at an exceptional point,” Nanophoton. 10, 403–423 (2021).
  * [40] H. Wang, S. K. Gupta, B. Xie, and M. Lu, “Topological photonic crystals: a review,” Front. Optoelectron. 13, 50–72 (2020).
  * [41] H. Liu, B. Xie, H. Cheng, J. Tian, and S. Chen, “Topological photonic states in artificial microstructures [Invited],” Chin. Opt. Lett. 19, 052602 (2021).
  * [42] Y. V. Kartashov and D. V. Skryabin, “Bistable topological insulator with exciton-polaritons,” Phys. Rev. Lett. 119, 253904 (2017).
  * [43] W. Zhang, X. Chen, Y. V. Kartashov, D. V. Skryabin, and F. Ye, “Finite-dimensional bistable topological insulators: From small to large,” Laser Photon. Rev. 13, 1900198 (2019).
  * [44] Y. Q. Zhang, Y. V. Kartashov, and A. Ferrando, “Interface states in polariton topological insulators,” Phys. Rev. A 99, 053836 (2019).
  * [45] Y. Lumer, M. C. Rechtsman, Y. Plotnik, and M. Segev, “Instability of bosonic topological edge states in the presence of interactions,” Phys. Rev. A 94, 021801 (2016).
  * [46] Y. V. Kartashov and D. V. Skryabin, “Modulational instability and solitary waves in polariton topological insulators,” Optica 3, 1228–1236 (2016).
  * [47] G. Harari, M. A. Bandres, Y. Lumer, M. C. Rechtsman, Y. D. Chong, M. Khajavikhan, D. N. Christodoulides, and M. Segev, “Topological insulator laser: Theory,” Science 359, eaar4003 (2018).
  * [48] M. A. Bandres, S. Wittek, G. Harari, M. Parto, J. Ren, M. Segev, D. N. Christodoulides, and M. Khajavikhan, “Topological insulator laser: Experiments,” Science 359, eaar4005 (2018).
  * [49] A. Dikopoltsev, T. H. Harder, E. Lustig, O. A. Egorov, J. Beierlein, A. Wolf, Y. Lumer, M. Emmerling, C. Schneider, S. Höfling, M. Segev, and S. Klembt, “Topological insulator vertical-cavity laser array,” Science 373, 1514–1517 (2021).
  * [50] B. Bahari, A. Ndao, F. Vallini, A. El Amili, Y. Fainman, and B. Kanté, “Nonreciprocal lasing in topological cavities of arbitrary geometries,” Science 358, 636–640 (2017).
  * [51] Y. V. Kartashov and D. V. Skryabin, “Two-dimensional topological polariton laser,” Phys. Rev. Lett. 122, 083902 (2019).
  * [52] Y. Zeng, U. Chattopadhyay, B. Zhu, B. Qiang, J. Li, Y. Jin, L. Li, A. G. Davies, E. H. Linfield, B. Zhang, Y. Chong, and Q. J. Wang, “Electrically pumped topological laser with valley edge modes,” Nature 578, 246–250 (2020).
  * [53] H. Zhong, Y. D. Li, D. H. Song, Y. V. Kartashov, Y. Q. Zhang, Y. P. Zhang, and Z. Chen, “Topological valley Hall edge state lasing,” Laser Photon. Rev. 14, 2000001 (2020).
  * [54] Y. Gong, S. Wong, A. J. Bennett, D. L. Huffaker, and S. S. Oh, “Topological insulator laser using valley-hall photonic crystals,” ACS Photon. 7, 2089–2097 (2020).
  * [55] Y. V. Kartashov, G. E. Astrakharchik, B. A. Malomed, and L. Torner, “Frontiers in multidimensional self-trapping of nonlinear fields and matter,” Nat. Rev. Phys. 1, 185–197 (2019).
  * [56] B. A. Malomed and D. Mihalache, “Nonlinear waves in optical and matter-wave media: A topical survey of recent theoretical and experimental results,” Rom. J. Phys. 64, 106 (2019).
  * [57] D. Mihalache, “Localized structures in optical and matter-wave media: A selection of recent studies,” Rom. Rep. Phys. 73, 403 (2021).
  * [58] Y. Lumer, Y. Plotnik, M. C. Rechtsman, and M. Segev, “Self-localized states in photonic topological insulators,” Phys. Rev. Lett. 111, 243905 (2013).
  * [59] O. Bleu, G. Malpuech, and D. D. Solnyshkov, “Robust quantum valley Hall effect for vortices in an interacting bosonic quantum fluid,” Nat. Commun. 9, 3991 (2018).
  * [60] D. Leykam and Y. D. Chong, “Edge solitons in nonlinear-photonic topological insulators,” Phys. Rev. Lett. 117, 143901 (2016).
  * [61] M. J. Ablowitz and J. T. Cole, “Tight-binding methods for general longitudinally driven photonic lattices: Edge states and solitons,” Phys. Rev. A 96, 043868 (2017).
  * [62] D. R. Gulevich, D. Yudin, D. V. Skryabin, I. V. Iorsh, and I. A. Shelykh, “Exploring nonlinear topological states of matter with exciton-polaritons: Edge solitons in kagome lattice,” Sci. Rep. 7, 1780 (2017).
  * [63] C. Li, F. Ye, X. Chen, Y. V. Kartashov, A. Ferrando, L. Torner, and D. V. Skryabin, “Lieb polariton topological insulators,” Phys. Rev. B 97, 081103 (2018).
  * [64] D. A. Smirnova, L. A. Smirnov, D. Leykam, and Y. S. Kivshar, “Topological edge states and gap solitons in the nonlinear Dirac model,” Laser Photon. Rev. 13, 1900223 (2019).
  * [65] W. Zhang, X. Chen, Y. V. Kartashov, V. V. Konotop, and F. Ye, “Coupling of edge states and topological Bragg solitons,” Phys. Rev. Lett. 123, 254103 (2019).
  * [66] S. K. Ivanov, Y. V. Kartashov, A. Szameit, L. Torner, and V. V. Konotop, “Vector topological edge solitons in Floquet insulators,” ACS Photon. 7, 735–745 (2020).
  * [67] S. K. Ivanov, Y. V. Kartashov, L. J. Maczewsky, A. Szameit, and V. V. Konotop, “Edge solitons in Lieb topological Floquet insulator,” Opt. Lett. 45, 1459–1462 (2020).
  * [68] S. K. Ivanov, Y. V. Kartashov, L. J. Maczewsky, A. Szameit, and V. V. Konotop, “Bragg solitons in topological Floquet insulators,” Opt. Lett. 45, 2271–2274 (2020).
  * [69] S. K. Ivanov, Y. V. Kartashov, M. Heinrich, A. Szameit, L. Torner, and V. V. Konotop, “Topological dipole Floquet solitons,” Phys. Rev. A 103, 053507 (2021).
  * [70] H. Zhong, S. Xia, Y. Zhang, Y. Li, D. Song, C. Liu, and Z. Chen, “Nonlinear topological valley Hall edge states arising from type-II Dirac cones,” Adv. Photon. 3, 056001 (2021).
  * [71] D. A. Smirnova, L. A. Smirnov, E. O. Smolina, D. G. Angelakis, and D. Leykam, “Gradient catastrophe of nonlinear photonic valley-Hall edge pulses,” Phys. Rev. Research 3, 043027 (2021).
  * [72] F. Zangeneh-Nejad and R. Fleury, “Nonlinear second-order topological insulators,” Phys. Rev. Lett. 123, 053902 (2019).
  * [73] D. Xiao, M.-C. Chang, and Q. Niu, “Berry phase effects on electronic properties,” Rev. Mod. Phys. 82, 1959–2007 (2010).
  * [74] J. Noh, S. Huang, K. P. Chen, and M. C. Rechtsman, “Observation of photonic topological valley Hall edge states,” Phys. Rev. Lett. 120, 063902 (2018).
  * [75] K. F. Mak, K. L. McGill, J. Park, and P. L. McEuen, “The valley Hall effect in ${\rm MoS}_{2}$ transistors,” Science 344, 1489–1492 (2014).
  * [76] J.-W. Liu, F.-L. Shi, X.-T. He, G.-J. Tang, W.-J. Chen, X.-D. Chen, and J.-W. Dong, “Valley photonic crystals,” Adv. Phys. X 6, 1905546 (2021).
  * [77] H. Xue, Y. Yang, and B. Zhang, “Topological valley photonics: Physics and device applications,” Adv. Photon. Research 2, 2100013 (2021).
  * [78] X. Wu, Y. Meng, J. Tian, Y. Huang, H. Xiang, D. Han, and W. Wen, “Direct observation of valley-polarized topological edge states in designer surface plasmon crystals,” Nat. Commun. 8, 1304 (2017).
  * [79] M. I. Shalaev, W. Walasik, A. Tsukernik, Y. Xu, and N. M. Litchinitser, “Robust topologically protected transport in photonic crystals at telecommunication wavelengths,” Nat. Nanotech. 14, 31–34 (2019).
  * [80] Y. Yang, Y. Yamagami, X. Yu, P. Pitchappa, J. Webber, B. Zhang, M. Fujita, T. Nagatsuma, and R. Singh, “Terahertz topological photonics for on-chip communication,” Nat. Photon. 14, 446–451 (2020).
  * [81] M. S. Kirsch, Y. Zhang, M. Kremer, L. J. Maczewsky, S. K. Ivanov, Y. V. Kartashov, L. Torner, D. Bauer, A. Szameit, and M. Heinrich, “Nonlinear second-order photonic topological insulators,” Nat. Phys. 17 (2021).
  * [82] D. Tan, Z. Wang, B. Xu, and J. Qiu, “Photonic circuits written by femtosecond laser in glass: improved fabrication and recent progress in photonic devices,” Adv. Photon. 3, 024002 (2021).
  * [83] B. Ren, H. Wang, V. O. Kompanets, Y. V. Kartashov, Y. Li, and Y. Zhang, “Dark topological valley Hall edge solitons,” Nanophoton. 10, 3559–3566 (2021).
  * [84] H. Zhai, M. Rechtsman, Y.-M. Lu, and K. Yang, “Focus on topological physics: from condensed matter to cold atoms and optics,” New J. Phys. 18, 080201 (2016).
  * [85] M. S. Rudner and N. H. Lindner, “Band structure engineering and non-equilibrium dynamics in Floquet topological insulators,” Nat. Rev. Phys. 2, 229–244 (2020).