# Some properties of morphic images
of (eventually) dendric words

France Gheeraert  Department of Mathematics, University of Liège, Allée de la
Découverte 12 (B37), B-4000 Liège, Belgium.
<EMAIL_ADDRESS>
###### Abstract

The class of (eventually) dendric words generalizes well-studied families such
as the Sturmian words, the Arnoux-Rauzy words or the codings of interval
exchanges. Dendricity is also a particular case of neutrality. We show that,
however, the notions of eventual dendricity and eventual neutrality coincide.
This paper then focuses on two questions linking dendricity and morphisms. We
first look at the evolution of the factor complexity when applying a non-
erasing morphism to an eventually dendric word and show that it can only grow
by an additive constant. We next generalize a result known for Sturmian words
and consider the morphisms that preserve dendricity for all dendric words. We
show that they correspond exactly to the morphisms generated by the Arnoux-
Rauzy morphisms.

##  1 Introduction

Given a bi-infinite word, the study of the left and right extensions of its
factors provides information about the factor complexity of the word [5] and
the general structure of the language. Well known families such as Sturmian,
Arnoux-Rauzy or neutral words can be defined using extensions. In [2], the
authors introduced the notion of dendric words under the terminology of tree
words. These are defined using the notion of extension graph, a bipartite
graph whose set of vertices is the disjoint union of the left and right
extensions of a given factor $w$ and there is an edge between the left copy of
$a$ and the right copy of $b$ if $awb$ is a factor. A bi-infinite word is
dendric if the extension graphs of all its factors are trees. This notion was
later generalized to eventually dendric words in [7] by only requiring the
extension graphs of long enough factors to be trees.

The families of dendric and of eventually dendric words both exhibit several
combinatorial [3, 4, 7] and ergodic [1, 6] properties. Some of these
properties offer a first link between morphisms and dendricity. For example,
these families are stable under derivation by return words and under maximal
bifix decoding. Both of these operations provide examples of (eventually)
dendric words whose image under a particular morphism is also (eventually)
dendric. Moreover, a deeper study of the stability of dendricity under
particular morphisms gives an $S$-adic characterization of dendric and
eventually dendric shift spaces [10].

In this paper, we delve deeper into the study of the link between morphisms
and dendricity. For that, we mainly answer two questions.

The first one is the growth of the factor complexity. We improve a result of
[5] in the case of eventually dendric words by proving that, when applying a
non-erasing morphism to an eventually dendric word, the factor complexity can
only grow by an additive constant. As the factor complexities of dendric and
eventually dendric words are well known and related to the size of the
alphabet in the first case and the asymptotic pairs [7] in the second case,
this gives us additional restrictions on the image, provided that it is
dendric (resp., eventually dendric).

The second objective is to generalize a well-known result for Sturmian and
Arnoux-Rauzy words. In [11], the authors proved that a morphism preserves the
Arnoux-Rauzy property for one (aperiodic) Arnoux-Rauzy word if and only if it
preserves it for every Arnoux-Rauzy word, if and only if it is generated by
the so-called Arnoux-Rauzy morphisms. In the case of dendric words, we lose
the first equivalence. However, we prove that the only dendric preserving
morphisms are still the ones generated by the Arnoux-Rauzy morphisms. This
generalizes a result of [9] where the authors proved it for a specific sub-
family of morphisms.

This paper is organized as follows. In Section 2, we recall some basic notions
and tools of combinatorics on words then in Section 3, we introduce the
families of words studied in this paper and prove that some of these coincide.

Section 4 focuses on the study of the evolution of the factor complexity when
applying a morphism to an eventually neutral word. The main result here is
that the factor complexity can only grow by an additive constant. For that, we
use the notion of coverings of a finite word.

Finally, we consider the monoid generated by the Arnoux-Rauzy morphisms. We
show in Section 5 that its elements are exactly the morphisms that preserve
dendricity for all dendric words. We also prove that the morphisms preserving
codings of regular interval exchange transformations are trivial, except in
the Sturmian case.

##  2 Definitions

Let $\mathcal{A}$ be an alphabet, i.e. a finite set of letters. Unless
specified otherwise, we will always assume that the alphabets are of size at
least 2. We denote by $\mathcal{A}^{*}$ (resp., $\mathcal{A}^{\mathbb{Z}}$)
the set of finite (resp., bi-infinite) words with letters in the alphabet
$\mathcal{A}$. When we want to specify that all the letters of $\mathcal{A}$
appear in a bi-infinite word $x\in\mathcal{A}^{\mathbb{Z}}$, we will say that
$x$ is a bi-infinite word _over_ $\mathcal{A}$.

Given a finite word $w=w_{1}\dots w_{n}\in\mathcal{A}^{n}$, its _length_
denoted $|w|$ is the integer $n$. The _empty word_ is the only word of length
zero and is denoted by $\varepsilon$. The set of non-empty words in
$\mathcal{A}^{*}$ is $\mathcal{A}^{+}$. For a word $w\in\mathcal{A}^{+}$, we
will use the notations $w_{[i,j]}$ for $w_{i}\dots w_{j}$ and $w^{\omega}$
(resp., ${}^{\omega}w$) for the right-infinite word $www\dots$ (resp., the
left-infinite word $\dots www$).

A finite word $u$ is a _factor_ of $w\in\mathcal{A}^{*}$ if there exists
$p,s\in\mathcal{A}^{*}$ such that $w=pus$. Moreover, if $p=\varepsilon$
(resp., $s=\varepsilon$) we say that $u$ is a _prefix_ (resp., _suffix_) of
$w$. We can extend the notion of factors to bi-infinite words by saying that a
finite word $u$ is a _factor_ of $x\in\mathcal{A}^{\mathbb{Z}}$ if there exist
a left-infinite word $p$ and a right-infinite word $s$ such that $x=pus$. The
set of factors of $x\in\mathcal{A}^{\mathbb{Z}}$ is called its _language_ and
is denoted $\mathcal{L}(x)$. The notation $\mathcal{L}_{\geq n}(x)$ (resp.,
$\mathcal{L}_{\leq n}(x)$, $\mathcal{L}_{n}(x)$) represents the elements of
$\mathcal{L}(x)$ of length at least (resp., at most, exactly) $n$. The _factor
complexity_ of $x$ is then the function $p_{x}:\mathbb{N}\to\mathbb{N}$ such
that $p_{x}(n)=\operatorname{\\#}\mathcal{L}_{n}(x)$.

Two finite words are _prefix comparable_ if one is prefix of the other. A
_prefix code_ is a set $S$ of finite words such that, for any two distinct
$u,v\in S$, $u$ and $v$ are not prefix comparable. Moreover, given a bi-
infinite word $x$, $S\subseteq\mathcal{L}(x)$ is said to be an _$x$ -maximal
prefix code_ if it is a prefix code and every word of $\mathcal{L}(x)$ is
prefix comparable with (at least) one element of $S$. We similarly define the
notions of suffix comparable, suffix code and $x$-maximal suffix code.

A _morphism_ $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ is a monoid
homomorphism between $\mathcal{A}^{*}$ and $\mathcal{B}^{*}$ (endowed with
concatenation). Moreover, we assume that $\mathcal{B}$ is minimal, i.e. every
letter of $\mathcal{B}$ appear in the image of some word under $\sigma$. We
almost exclusively work with _non-erasing morphisms_ , i.e. such that the
images of the letters are not empty. In that case, we can naturally extend
$\sigma$ to bi-infinite words. The _width_ of a morphism
$\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ is
$\lVert\sigma\rVert:=\max\\{|\sigma(a)|\mid a\in\mathcal{A}\\}$. A _coding_ is
a non-erasing morphism of width 1. Furthermore, if the images of the letters
are distinct, we say that it is a _bijective coding_.

##  3 Neutral and dendric words

Given a bi-infinite word $x\in\mathcal{A}^{\mathbb{Z}}$ and one of its factor
$w$, the sets of _left_ , _right_ and _bi-extensions_ of $w$ are defined
respectively as

$\displaystyle E^{-}_{x}(w)$ $\displaystyle=\\{a\in\mathcal{A}\mid
aw\in\mathcal{L}(x)\\}$ $\displaystyle E^{+}_{x}(w)$
$\displaystyle=\\{a\in\mathcal{A}\mid wa\in\mathcal{L}(x)\\}$ $\displaystyle
E_{x}(w)$ $\displaystyle=\\{(a,b)\in\mathcal{A}\times\mathcal{A}\mid
awb\in\mathcal{L}(x)\\}.$

A word $w$ is said to be _left_ (resp., _right_) _special_ if it has at least
two left (resp., right) extensions. It is _bispecial_ if it is left and right
special.

We define the _multiplicity_ of $w$ as

$m_{x}(w)=\operatorname{\\#}E_{x}(w)-\operatorname{\\#}E^{-}_{x}(w)-\operatorname{\\#}E^{+}_{x}(w)+1.$

We then say that $w$ is _neutral_ if $m_{x}(w)=0$ and it is _weak_ (resp.,
_strong_) if $m_{x}(w)<0$ (resp., $m_{x}(w)>0$).

The multiplicity is strongly related to the _first difference of complexity_
$s_{x}(n):=p_{x}(n+1)-p_{x}(n)$. We have the following result.

######  Proposition 1 (Cassaigne and Nicolas [5]).

Let $x\in\mathcal{A}^{\mathbb{Z}}$. For all $n\geq 0$,

  1. 1.

$s_{x}(n)=\sum_{w\in\mathcal{L}_{n}(x)}(\operatorname{\\#}E^{+}_{x}(w)-1)=\sum_{w\in\mathcal{L}_{n}(x)}(\operatorname{\\#}E^{-}_{x}(w)-1)$
;

  2. 2.

$s_{x}(n+1)-s_{x}(n)=\sum_{w\in\mathcal{L}_{n}(x)}m_{x}(w)$.

The left, right and bi-extensions of $w$ in $x$ can also be represented in a
graph called the _extension graph_ of $w$ and denoted $\mathcal{E}_{x}(w)$. It
is the undirected bipartite graph whose set of vertices is the disjoint union
of $E^{-}_{x}(w)$ and $E^{+}_{x}(w)$ and containing the edge $(a,b)\in
E^{-}_{x}(w)\times E^{+}_{x}(w)$ if and only if $(a,b)$ is a bi-extension of
$w$.

Based on this graph, we define additional families of words. A word $w$ is
said to be _dendric_ (resp., _acyclic_ , _connected_) if its extension graph
is a tree (resp., acyclic, connected). Remark that, if a word is not
bispecial, then it is always dendric.

######  Example 2.

Let $x$ be the word ${}^{\omega}(001)\cdot(001)^{\omega}$. The extension
graphs of the empty word and of the letter 0 are represented in Figure 1. We
can see that $\varepsilon$ is dendric and 0 is acyclic. Moreover, these are
the only bispecial words thus every other factor of $x$ is dendric.

$\mathcal{E}_{x}(\varepsilon)$$0$$1$$0$$1$$\mathcal{E}_{x}(0)$$0$$1$$0$$1$
Figure 1: The extension graph of $\varepsilon$ (on the left) is a tree and the
extension graph of $0$ (on the right) is acyclic.

As a direct consequence of the link between the number of edges and the number
of vertices in a tree, we have the following lemma.

######  Lemma 3.

Let $x\in\mathcal{A}^{\mathbb{Z}}$ and $w\in\mathcal{L}(x)$.

  1. 1.

If $w$ is connected (resp., acyclic), then it is strong (resp., weak) or
neutral.

  2. 2.

If $w$ is connected (resp., acyclic) and neutral, then it is dendric.

For any property $P$ among _neutral_ , _weak or neutral_ , _strong or neutral_
, _dendric_ , _acyclic_ and _connected_ , we say that a bi-infinite word $x$
is _eventually_ $P$ if there exists $N\geq 0$ such that the words of
$\mathcal{L}_{\geq N}(x)$ satisfy the property $P$. The minimal such $N$ is
then called the _threshold_. Furthermore, if the threshold is 0, we will drop
the adverb “eventually”.

Remark that, as a direct consequence of Proposition 1, if
$x\in\mathcal{A}^{\mathbb{Z}}$ is a neutral bi-infinite word over
$\mathcal{A}$, then the factor complexity of $x$ is given by

$p_{x}(n)=(\operatorname{\\#}\mathcal{A}-1)n+1.$

When looking at eventual properties, several notions coincide. However, the
thresholds may differ, as stated in the following result.

######  Proposition 4.

Let $x\in\mathcal{A}^{\mathbb{Z}}$. The following are equivalent:

  1. 1.

$x$ is eventually dendric with threshold $N$;

  2. 2.

$x$ is eventually acyclic with threshold $M$;

  3. 2$\,{}^{\prime}\\!\\!$.

$x$ is eventually neutral with threshold $M^{\prime}$;

  4. 3.

$x$ is eventually weak or neutral with threshold $K$.

Moreover, $K\leq M\leq N$ and $K\leq M^{\prime}\leq N$.

###### Proof.

By Lemma 3, it only remains to prove that, if $x$ is eventually weak or
neutral, then it is eventually dendric.

Assume that $x$ is eventually weak or neutral of threshold $K$ but not
eventually dendric. Thus, there exist an infinite number of words of
$\mathcal{L}(x)$ which are weak or neutral but not dendric. Let $W$ denote the
set of these words and let $u\in\mathcal{L}_{\geq K}(x)$ be a prefix of an
infinite number of elements of $W$. Assume also that
$\operatorname{\\#}E^{-}_{x}(u)$ is minimal among such words.

There exists a right extension $a$ such that $ua$ is a prefix of an infinite
number of words of $W$ and, by hypothesis on $u$,
$E^{-}_{x}(ua)=E^{-}_{x}(u)$. In particular, $u$ is then connected. Since it
is weak or neutral, it is neutral and dendric by Lemma 3 and $a$ is the unique
right extension of $u$ such that $ua$ is left special. As the elements of $W$
are not dendric, they are bispecial thus left-special and therefore cannot
begin with $ub$, $b\neq a$. Since, $u$ is not in $W$, we deduce that

$W\cap u\mathcal{A}^{*}=W\cap ua\mathcal{A}^{*}.$

Iterating the reasoning, for each $n$, we can find a word $v^{(n)}$ of length
$n$ such that

$W\cap u\mathcal{A}^{*}=W\cap uv^{(n)}\mathcal{A}^{*}$

thus the elements of $W\cap u\mathcal{A}^{*}$ are of length at least $|u|+n$
for all $n$. As $W\cap u\mathcal{A}^{*}$ contains finite words, this is a
contradiction. ∎

Some well studied families of words are particular examples of dendric words.
It is the case of the Sturmian words, the Arnoux-Rauzy words and of the
codings of regular interval exchange transformations. This last family will be
useful in this paper. We recall here its definition.

Given two total orders $\leq,\preceq$ on $\mathcal{A}=\\{a_{1},\dots,a_{k}\\}$
and $k$ lengths $\lambda_{a_{1}},\dots,\lambda_{a_{k}}>0$ such that
$\sum_{i=1}^{k}\lambda_{i}=1$, the associated _interval exchange
transformation_ is the bijective map $T:[0,1[\to[0,1[$ such that

$T(z)=z-\sum_{a_{j}<a_{i}}\lambda_{a_{j}}+\sum_{a_{j}\prec
a_{i}}\lambda_{a_{j}}\quad\text{if
}z\in\left[\sum_{a_{j}<a_{i}}\lambda_{a_{j}},\sum_{a_{j}\leq
a_{i}}\lambda_{a_{j}}\right[.$

In other words, for all $1\leq i\leq k$, it maps the interval
$I_{a_{i}}:=\left[\sum_{a_{j}<a_{i}}\lambda_{a_{j}},\sum_{a_{j}\leq
a_{i}}\lambda_{a_{j}}\right[$ to the interval
$J_{a_{i}}:=\left[\sum_{a_{j}\prec a_{i}}\lambda_{a_{j}},\sum_{a_{j}\preceq
a_{i}}\lambda_{a_{j}}\right[$. If, moreover, the orbits (under $T$) of the
non-zero $\sum_{a_{j}<a_{i}}\lambda_{a_{j}}$, $i\in\\{1,\dots,k\\}$, are
infinite and disjoint, then we say that $T$ is a _regular interval exchange
transformation_ , or RIET for short. In that case, the orbit of each
$z\in[0,1[$ is dense [12].

For $z\in[0,1[$, its _(natural) coding_ is the bi-infinite word
$x\in\mathcal{A}^{\mathbb{Z}}$ such that, for all $n\in\mathbb{Z}$,
$x_{n}=a_{i}$ if and only if $T^{n}(z)$ is in the interval $I_{a_{i}}$.
Observe in particular that, if $T$ is an RIET, then $ab\in\mathcal{L}(x)$ if
and only if $J_{a}\cap I_{b}\neq\emptyset$.

It is also sometimes interesting to use the following combinatorial
characterization of codings of regular interval exchange transformations.

######  Theorem 5 (Ferenczi-Zamboni [8], Gheeraert-Lejeune-Leroy [9]).

A word $x$ over $\mathcal{A}$ is the natural coding of a regular interval
exchange transformation with the pair of orders $\binom{\leq}{\preceq}$ if and
only if it is recurrent and it satisfies the following conditions for every
$w\in\mathcal{L}(x)$:

  1. 1.

for all $(a_{1},b_{1}),(a_{2},b_{2})\in E_{x}(w)$, if $a_{1}\prec a_{2}$, then
$b_{1}\leq b_{2}$;

  2. 2.

for all $a_{1},a_{2}\in E^{-}_{x}(w)$, if $a_{1},a_{2}$ are consecutive for
$\preceq$, then $E^{+}_{x}(a_{1}w)\cap E^{+}_{x}(a_{2}w)$ is a singleton.

Moreover, up to symmetry, $\binom{\leq}{\preceq}$ is the only pair of orders
satisfying these properties for all $w\in\mathcal{L}(x)$.

In other words, $x$ is the coding of an RIET if and only if $x$ is recurrent,
dendric and, in every extension graph, if the left extensions are placed on a
line with respect to $\preceq$ and the right extensions are placed on a
parallel line according to the order $\leq$, then the edges can be drawn as
straight non-crossing segments. We will say that such a graph is _planar_ for
$(\preceq,\leq)$.

Finally, to generate counter-examples, we will need the following result.

######  Lemma 6.

Let $\mathcal{A}$ be an alphabet, let $G$ be a bipartite graph with
$\mathcal{A}$ as its set of left (resp., right) vertices, and let
$\leq,\preceq$ be two total orders on $\mathcal{A}$ such that, for all
$i\in\\{1,\dots,\operatorname{\\#}\mathcal{A}-1\\}$, the sets of the $i$
smallest elements for $\leq$ and for $\preceq$ are different. If $G$ is
connected and planar for $(\preceq,\leq)$, then there exists a natural coding
$x$ of a regular interval exchange transformation associated with the orders
$\leq$ and $\preceq$ such that $G=\mathcal{E}_{x}(\varepsilon)$.

###### Proof.

The edges of $G$ give us the factors of length $2$ and thus, restrictions on
the lengths of the intervals. As $G$ is planar, it is possible to find lengths
that satisfy these restrictions and, using the condition on the orders, we can
choose them such that the corresponding interval exchange transformation (with
orders $\leq$ and $\preceq$) is regular. It then suffices to take $x$ as the
coding of any point for this transformation. The graph
$\mathcal{E}_{x}(\varepsilon)$ will contain all the edges of $G$, and exactly
those as $G$ is connected and $\mathcal{E}_{x}(\varepsilon)$ is a tree. ∎

##  4 Factor complexity

In [5], Cassaigne and Nicolas proved that, when applying a non-erasing
morphism, the complexity grows at most by a multiplicative constant. In this
section, we refine this result to prove that, if the initial bi-infinite word
is eventually neutral, then the complexity grows at most by an additive
constant.

For the proof, we will use the notion of covering.

######  Definition 7.

Let $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a non-erasing morphism. A
_covering_ of a non empty word $u\in\mathcal{B}^{+}$ is a pair
$(w,k)\in\mathcal{A}^{+}\times\mathbb{Z}_{\geq 0}$ such that
$u=\sigma(w)_{[k+1,k+|u|]}$ and $w$ is minimal, i.e.

  1. 1.

$k+1\leq|\sigma(w_{1})|$ and

  2. 2.

$k+|u|>\left|\sigma(w_{[1,|w|-1]})\right|$.

For a bi-infinite word $x$ and for $n>0$, we define by $C_{x,\sigma}(n)$ the
set of coverings $(w,k)$ of words of length $n$ such that
$w\in\mathcal{L}(x)$. We then denote
$c_{x,\sigma}(n)=\operatorname{\\#}C_{x,\sigma}(n)$. As we usually consider
only one morphism at a time, we will drop the subscript $\sigma$.

######  Example 8.

Let $\sigma$ be such that $\sigma:a\mapsto ab,b\mapsto abb$. The coverings of
$babb$ are given by $(ab,1)$ and $(bb,2)$. If $x$ is a Sturmian word over the
alphabet $\\{a,b\\}$ containing the factor $aa$ (and therefore, not the factor
$bb$), we have $(ab,1)\in C_{x}(4)$ and $(bb,2)\not\in C_{x}(4)$.

######  Remark 9.

If $(w,k)$ is a covering of a letter $a$, then by minimality, $w$ is also a
letter and $k$ can then vary between $0$ and $|\sigma(w)|-1$ thus

$c_{x}(1)=\sum_{a\in\mathcal{A}}|\sigma(a)|,$

independently of the bi-infinite word $x$ over $\mathcal{A}$.

The following lemma gives a trivial link between the number of coverings and
the factor complexity of the image.

######  Lemma 10.

For all bi-infinite word $x\in\mathcal{A}^{\mathbb{Z}}$ and non-erasing
morphism $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$, we have

$p_{\sigma(x)}(n)\leq c_{x}(n).$

###### Proof.

The map
$c:C_{x}(n)\to\mathcal{L}_{n}(\sigma(x)),\quad(w,k)\mapsto\sigma(w)_{[k+1,k+n]}$
is well defined and is surjective since each element of
$\mathcal{L}_{n}(\sigma(x))$ has at least one covering in $C_{x}(n)$. ∎

Thus, instead of directly bounding the complexity of the image, it suffices to
bound the number of coverings. We will need the following lemma.

######  Lemma 11.

Let $x$ be an eventually strong (resp., weak) or neutral word with threshold
$N$. For any $x$-maximal suffix code $W\subseteq\mathcal{L}_{\geq
K}(x)\cap\mathcal{L}_{\leq M}(x)$ with $K\geq N$, we have

$s_{x}(K)\leq\sum_{w\in W}(\operatorname{\\#}E^{+}_{x}(w)-1)\leq s_{x}(M)$
$\left(\text{resp., }s_{x}(K)\geq\sum_{w\in
W}(\operatorname{\\#}E^{+}_{x}(w)-1)\geq s_{x}(M)\right).$

###### Proof.

We prove the result when $x$ is eventually strong or neutral. The other case
is similar. Let us first look at the left inequality and let $k=\max\\{|w|\mid
w\in W\\}$. If $k=K$, then $W\subseteq\mathcal{L}_{K}(x)$ and, as $W$ is
$x$-maximal, we must have the equality. Therefore,

$\sum_{w\in W}(\operatorname{\\#}E^{+}_{x}(w)-1)=s_{x}(K)$

by Proposition 1. Otherwise, we proceed by induction to show that we can
decrease $k$. Let

$W^{\prime}=(W\cap\mathcal{L}_{<k}(x))\cup\\{w\mid\exists a\in
E^{-}_{x}(w)\text{ st. }aw\in W\cap\mathcal{L}_{k}(x)\\}.$

By definition, the set $W^{\prime}$ is also an $x$-maximal suffix code
included in $\mathcal{L}_{\geq K}(x)\cap\mathcal{L}_{\leq M}(x)$. Moreover,
$\max\\{|w|\mid w\in W^{\prime}\\}=k-1$. It remains to prove that

$\sum_{w\in W}(\operatorname{\\#}E^{+}_{x}(w)-1)\geq\sum_{w\in
W^{\prime}}(\operatorname{\\#}E^{+}_{x}(w)-1).$

Let $w\in W^{\prime}\setminus W$. By $x$-maximality of $W$, we must have
$aw\in W$ for all $a\in E^{-}_{x}(w)$. In addition, $w$ is of length at least
$N$ thus it is strong or neutral. This implies that

$\sum_{a\in
E^{-}_{x}(w)}\left(\operatorname{\\#}E^{+}_{x}(aw)-1\right)=\operatorname{\\#}E_{x}(w)-\operatorname{\\#}E^{-}_{x}(w)\geq\operatorname{\\#}E^{+}_{x}(w)-1.$

As it is true for any $w\in W^{\prime}\setminus W$, this ends the proof of the
first inequality.

For the second inequality, we similarly prove that we can inductively increase
$m=\min\\{|w|\mid w\in W\\}$ until $m=M$. It suffices to consider

$W^{\prime}=(W\cap\mathcal{L}_{>m}(x))\cup\\{aw\mid w\in
W\cap\mathcal{L}_{m}(x),a\in E^{-}_{x}(w)\\}$

and $w\in W\setminus W^{\prime}$. Using the same inequalities as above, we
then show that $\sum_{w\in W}(\operatorname{\\#}E^{+}_{x}(w)-1)\leq\sum_{w\in
W^{\prime}}(\operatorname{\\#}E^{+}_{x}(w)-1)$. ∎

Note that a similar proof shows that the previous result is also true when
considering an $x$-maximal prefix code and replacing $E^{+}_{x}(w)$ by
$E_{x}^{-}(w)$ in the inequalities.

######  Proposition 12.

Let $x\in\mathcal{A}^{\mathbb{Z}}$ and let $\sigma$ be a non-erasing morphism.

  1. 1.

If $x$ is eventually neutral with threshold $N$ then there exists
$C\in\mathbb{Z}$ such that, for any $n\geq\max\\{1,N\lVert\sigma\rVert\\}$,

$c_{x}(n)=C+p_{x}(n).$

In particular, if $x$ is a neutral bi-infinite word over $\mathcal{A}$, we
have

$c_{x}(n)=\sum_{a\in\mathcal{A}}|\sigma(a)|\
+(\operatorname{\\#}\mathcal{A}-1)(n-1)$

for all $n\geq 1$.

  2. 2.

If $x$ is eventually strong or neutral with threshold $N$ then there exists
$C\in\mathbb{Z}$ such that, for any $n\geq\max\\{1,N\lVert\sigma\rVert\\}$,

$c_{x}(n)\leq C+p_{x}(n).$

###### Proof.

We prove the two cases simultaneously by studying the growth
$c_{x}(n+1)-c_{x}(n)$.

Remark that the elements of $C_{x}(n)$ and of $C_{x}(n+1)$ are linked. Indeed,
each $(w,k)\in C_{x}(n)$ is related to one or several elements of $C_{x}(n+1)$
in one of the following ways.

  * •

If $|\sigma(w)|=k+n$, then for all $a\in E^{+}_{x}(w)$, $(wa,k)$ is an element
of $C_{x}(n+1)$.

  * •

Otherwise, we have $|\sigma(w)|\geq k+n+1$ thus $(w,k)$ itself is in
$C_{x}(n+1)$.

Moreover, with this technique, we obtain every element of $C_{x}(n+1)$ exactly
once. When looking at $c_{x}(n+1)-c_{x}(n)$, we are then only interested in
the pairs $(w,k)\in C_{x}(n)$ such that $|\sigma(w)|=k+n$. However, for a
given word $w$, there exists $k<|\sigma(w_{1})|$ such that $|\sigma(w)|=k+n$
if and only if

$|\sigma(w_{[2,|w|]})|<n\leq|\sigma(w)|,$

and this $k$ is then unique. Thus, if $W_{n}$ is the set

$W_{n}=\\{w\in\mathcal{L}(x)\mid\,|\sigma(w_{[2,|w|]})|<n\leq|\sigma(w)|\\},$

we have

$c_{x}(n+1)-c_{x}(n)=\sum_{w\in W_{n}}(\operatorname{\\#}E^{+}_{x}(w)-1)$

for all $n\geq 1$.

By definition and since $\sigma$ is non-erasing, $W_{n}$ is an $x$-maximal
suffix code and it contains words of length at most $n$ and at least
$\left\lceil\frac{n}{\lVert\sigma\rVert}\right\rceil$.

Thus by Lemma 11, we obtain:

  1. 1.

if $x$ is eventually neutral with threshold $N$, then for any
$n\geq\max\\{1,N\lVert\sigma\rVert\\}$,

$c_{x}(n+1)-c_{x}(n)=\sum_{w\in
W_{n}}(\operatorname{\\#}E^{+}_{x}(w)-1)=s_{x}(n);$

  2. 2.

if $x$ is eventually strong or neutral with threshold $N$, then for any
$n\geq\max\\{1,N\lVert\sigma\rVert\\}$,

$c_{x}(n+1)-c_{x}(n)=\sum_{w\in W_{n}}(\operatorname{\\#}E^{+}_{x}(w)-1)\leq
s_{x}(n).$

The conclusion follows, using Remark 9 and the value of the factor complexity
in the neutral case. ∎

######  Theorem 13.

If $x$ is an eventually weak (resp., strong) or neutral bi-infinite word and
$\sigma$ is a non-erasing morphism, then there exists $C\in\mathbb{Z}$ such
that

$p_{\sigma(x)}(n)\leq C+p_{x}(n)$

for all $n\geq 0$.

###### Proof.

Recall that, by Proposition 4, an eventually weak or neutral word is
eventually neutral. Using Proposition 12, we can then find $C$ such that

$c_{x}(n)\leq C+p_{x}(n)$

for all $n\geq 0$. We then conclude using Lemma 10. ∎

As a direct consequence of Theorem 13, we obtain the following result.

######  Corollary 14.

Let $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a non-erasing morphism. If
there exists a neutral bi-infinite word $x$ over $\mathcal{A}$ such that
$\sigma(x)$ is neutral, then
$\operatorname{\\#}\mathcal{B}\leq\operatorname{\\#}\mathcal{A}$.

###### Proof.

Indeed, $p_{x}(n)=(\operatorname{\\#}\mathcal{A}-1)n+1$ and
$p_{\sigma(x)}(n)=(\operatorname{\\#}\mathcal{B}-1)n+1$ for any $n$ thus the
conclusion follows from Theorem 13. ∎

######  Remark 15.

Without additional hypothesis on $\sigma$, the inequality of Corollary 14 is
the only restriction we can obtain on the sizes of the alphabets of a morphism
preserving the neutrality of a bi-infinite word, or even preserving dendricity
of a bi-infinite word. Indeed, using codings of RIET, we can build examples
for any values of $\operatorname{\\#}\mathcal{A}$,
$\operatorname{\\#}\mathcal{B}$ such that
$\operatorname{\\#}\mathcal{B}\leq\operatorname{\\#}\mathcal{A}$ with the
following technique.

Let $y$ be the coding of a point in an RIET $T$ with
$\operatorname{\\#}\mathcal{B}$ intervals and $x$ the coding of the same point
in the interval exchange transformation obtained by cutting one of the
intervals of $T$ into
$\operatorname{\\#}\mathcal{A}-\operatorname{\\#}\mathcal{B}+1$ sub-intervals.
The bi-infinite word $x$ is then on an alphabet of size
$\operatorname{\\#}\mathcal{A}$ and, if $\sigma$ maps all the letters coding
these sub-intervals to a new letter, then $y=\sigma(x)$ (up to a bijective
coding). This morphism $\sigma$ then preserves dendricity for an infinite
number of dendric bi-infinite words.

##  5 Dendric preserving morphisms

As seen in the previous section, the fact that a morphism preserves dendricity
for an infinite number of dendric bi-infinite words does not imply that the
starting alphabet and the image alphabet have the same size. However, we will
now prove that it is true when the morphism preserves dendricity for all
dendric bi-infinite words.

######  Definition 16.

A morphism $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ is _dendric preserving_
if, for any dendric bi-infinite word $x$ over $\mathcal{A}$, the bi-infinite
word $\sigma(x)$ is dendric.

######  Remark 17.

Although we only consider alphabets of size at least 2 in this paper, the
dendric preserving morphisms when one of the alphabets is unary can easily be
described. Indeed, if $\operatorname{\\#}\mathcal{B}=1$, then any morphism
$\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ is dendric preserving. And if
$\operatorname{\\#}\mathcal{A}=1$, then, for any morphism
$\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ and any bi-infinite word
$x\in\mathcal{A}^{\mathbb{Z}}$, the image $\sigma(x)$ is periodic thus
$\sigma$ is dendric preserving if and only if
$\operatorname{\\#}\mathcal{B}=1$.

We now define two words associated with a given morphism. These words will
play an important role when looking at factors in the image.

######  Definition 18.

Let $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a non-erasing morphism. If
it is finite, we denote by $p_{\sigma}$ (resp., $s_{\sigma}$) the longest
common prefix (resp., suffix) to all the $\sigma(a)^{\omega}$ (resp.,
${}^{\omega}\sigma(a)$), $a\in\mathcal{A}$.

Observe that, $p_{\sigma}$ and $s_{\sigma}$ can be empty. In the case of a
dendric preserving morphism, $p_{\sigma}$ and $s_{\sigma}$ are well defined,
as stated by the following lemma.

######  Lemma 19.

Let $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a non-erasing morphism. If
$p_{\sigma}$ (resp., $s_{\sigma}$) is not defined, then there exists a word
$v\in\mathcal{B}^{+}$ such that $\sigma(x)=\,^{\omega}v.v^{\omega}$ for any
bi-infinite word $x\in\mathcal{A}^{\mathbb{Z}}$.

###### Proof.

Assume that $p_{\sigma}$ is not defined, the proof for $s_{\sigma}$ is
similar. Thus there exists an infinite word $y\in\mathcal{B}^{\mathbb{N}}$
such that $\sigma(a)^{\omega}=y$ for all $a\in\mathcal{A}$. This word $y$ is
then periodic of period $p:=\gcd(\\{|\sigma(a)|\mid a\in\mathcal{A}\\})$ by
Fine and Wilf’s theorem. Let $v$ be its prefix of length $p$. By construction,
for each letter $a$, $\sigma(a)$ is a power of $v$. This proves that
$\sigma(x)=\,^{\omega}v.v^{\omega}$. ∎

The following result provides different equivalent ways that we could have
defined $p_{\sigma}$. We also have a similar result for $s_{\sigma}$ using
suffixes.

######  Lemma 20.

Let $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a non-erasing morphism. For
any word $p\in\mathcal{B}^{*}$ and any letter $a\in\mathcal{A}$, the following
are equivalent:

  1. 1.

$p$ is a prefix of $\sigma(a)^{\omega}$;

  2. 2.

$p$ is a proper prefix of $\sigma(a)p$.

Moreover, the following are also equivalent:

  1. 1.

$p$ satisfies one of the (equivalent) properties above for every letter
$a\in\mathcal{A}$;

  2. 2.

$p$ is a prefix of $\sigma(w)p$ for any $w\in\mathcal{A}^{*}$;

  3. 3.

there exists $N\geq 0$ such that $p$ is a prefix of $\sigma(w)$ for any
$w\in\mathcal{A}^{\geq N}$.

###### Proof.

If $p$ is a prefix of $\sigma(a)^{\omega}$, then it directly follows that it
is a prefix of $\sigma(a)p$. For the converse, $p$ is prefix comparable with
$\sigma(a)$ thus $\sigma(a)p$ is prefix comparable with $\sigma(a)^{2}$. This
implies that $p$ is prefix comparable with $\sigma(a)^{2}$. We iterate to show
that $p$ is prefix comparable with $\sigma(a)^{k}$ for any $k\in\mathbb{N}$.
The morphism $\sigma$ is non-erasing thus this implies that $p$ is a prefix of
$\sigma(a)^{\omega}$.

Let us show the second set of equivalences.

Assume that $p$ satisfies the previous properties for all the letters. We
proceed by induction on the length of $w$ to show that $p$ is a prefix of
$\sigma(w)p$. If $w=\varepsilon$, it is trivial. Assume that it is satisfied
for $w^{\prime}$ and that $w=w^{\prime}a$, $a\in\mathcal{A}$. By hypothesis,
$p$ is a prefix of $\sigma(a)p$ thus $\sigma(w^{\prime})p$ is a prefix of
$\sigma(w)p$. The conclusion follows.

Since the morphism $\sigma$ is non-erasing, for any word
$w\in\mathcal{A}^{\geq|p|}$, the length of $\sigma(w)$ is at least $|p|$ thus
$p$ being a prefix of $\sigma(w)p$ implies that $p$ is a prefix of
$\sigma(w)$.

Finally, if $p$ is a prefix of $\sigma(w)$ for any long enough $w$, then $p$
is a prefix of $\sigma(a^{k})$ for any large enough $k$ thus $\sigma$ is a
prefix of $\sigma(a)^{\omega}$ for any letter $a\in\mathcal{A}$. ∎

######  Proposition 21.

Let $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a dendric preserving
morphism. For each letter $b\in\mathcal{B}$, there exists at most one letter
$a\in\mathcal{A}$ such that $p_{\sigma}b$ is a prefix of $\sigma(a)p_{\sigma}$
and at most one letter $a^{\prime}\in\mathcal{A}$ such that $bs_{\sigma}$ is a
suffix of $s_{\sigma}\sigma(a^{\prime})$.

###### Proof.

Assume by contrary that there exist two letters $a,a^{\prime}\in\mathcal{A}$
such that $p_{\sigma}b$ is a prefix of both $\sigma(a)p_{\sigma}$ and
$\sigma(a^{\prime})p_{\sigma}$. By maximality of $p_{\sigma}$, there also
exists a letter $a^{\prime\prime}\in\mathcal{A}$ and a letter $b^{\prime}\neq
b$ such that $p_{\sigma}b^{\prime}$ is a prefix of
$\sigma(a^{\prime\prime})p_{\sigma}$.

Similarly, by maximality of $s_{\sigma}$, there exist two distinct letters
$d,d^{\prime}\in\mathcal{B}$ and two letters $c,c^{\prime}\in\mathcal{A}$ such
that $ds_{\sigma}$ is a suffix of $s_{\sigma}\sigma(c)$ and
$d^{\prime}s_{\sigma}$ is a suffix of $s_{\sigma}\sigma(c^{\prime})$.

Using Lemma 6 for example, we can find a coding $x$ of an RIET over
$\mathcal{A}$ (so, in particular a dendric bi-infinite word) such that
$ca,ca^{\prime\prime},c^{\prime}a^{\prime\prime},c^{\prime}a^{\prime}$ are
factors of length $2$. In $\sigma(x)$, the extension graph of
$s_{\sigma}p_{\sigma}$ then contains a cycle passing through $b,b^{\prime}$ on
the right and $d,d^{\prime}$ on the left, a contradiction. ∎

######  Remark 22.

More specifically, the previous result is true as soon as $s_{\sigma}$ and
$p_{\sigma}$ exist and, for any coding $x$ of an RIET, the extension graph of
$s_{\sigma}p_{\sigma}$ in $\sigma(x)$ is acyclic.

Combined with Corollary 14, this result directly implies the equality of the
sizes of the alphabets.

######  Corollary 23.

If $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ is dendric preserving, then
$\operatorname{\\#}\mathcal{A}=\operatorname{\\#}\mathcal{B}$.

On a two letters alphabet, the dendric words are exactly the Sturmian words.
In this case, the dendric preserving morphisms are called _Sturmian morphisms_
and it is well known (see [13] for example) that they are exactly, up to a
bijective coding, the morphisms generated by

$L_{0}:\begin{cases}0\mapsto 0\\\ 1\mapsto 01\end{cases}\quad
R_{0}:\begin{cases}0\mapsto 0\\\ 1\mapsto 10\end{cases}\quad
L_{1}:\begin{cases}0\mapsto 10\\\ 1\mapsto 1\end{cases}\quad
R_{1}:\begin{cases}0\mapsto 01\\\ 1\mapsto 1\end{cases}.$

These morphisms can be generalized to larger alphabets by the Arnoux-Rauzy
morphisms.

######  Definition 24.

The _Arnoux-Rauzy morphisms_ over $\mathcal{A}$ are defined by

$L_{\ell}:\begin{cases}\ell\mapsto\ell\\\ a\mapsto\ell a&\forall
a\in\mathcal{A}\setminus\\{\ell\\}\end{cases}\qquad
R_{\ell}:\begin{cases}\ell\mapsto\ell\\\ a\mapsto a\ell&\forall
a\in\mathcal{A}\setminus\\{\ell\\}\end{cases}$

for any letter $\ell\in\mathcal{A}$.

Note that, given an alphabet $\mathcal{A}$, we could restrict ourselves to
Arnoux-Rauzy morphisms for a fixed letter $\ell\in\mathcal{A}$ and compose
with permutations of $\mathcal{A}$ to obtain the other Arnoux-Rauzy morphisms
since $\pi^{-1}S_{\ell}\pi=S_{\pi^{-1}(\ell)}$ for $S\in\\{L,R\\}$.

It is easy to see that these morphisms are dendric preserving. In fact, we
have the following stronger result.

######  Lemma 25.

For any bi-infinite word $x$ over $\mathcal{A}$ and any letter
$\ell\in\mathcal{A}$, $x$ is dendric if and only if $y:=L_{\ell}(x)$ (resp.,
$y:=R_{\ell}(x)$) is.

In particular, a morphism $\tau$ is dendric preserving if and only if
$L_{\ell}\circ\tau$ (resp., $R_{\ell}\circ\tau$) is.

###### Proof.

Let $x$ be a bi-infinite word over $\mathcal{A}$ and $\ell\in\mathcal{A}$.
Observe that $\mathcal{L}(L_{\ell}(x))=\mathcal{L}(R_{\ell}(x))$ therefore one
is dendric if and only if the other is. Let $y=L_{\ell}(x)$. If a word
$w\in\mathcal{L}(y)$ is bispecial, then it is empty or it begins and ends with
$\ell$. In the first case, $w$ is trivially dendric. In the other case, there
exists $u\in\mathcal{L}(x)$ such that $w=L_{\ell}(u)\ell$. Moreover, for any
$u\in\mathcal{L}(x)$,

$(a,b)\in E_{y}(L_{\ell}(u)\ell)\Leftrightarrow(a,b)\in E_{x}(u),$

thus $L_{\ell}(u)\ell$ is dendric if and only if $u$ is. This proves that $x$
is dendric if and only if $y$ is. ∎

For a given alphabet $\mathcal{A}$, let us denote by $AR_{\mathcal{A}}$ the
monoid generated by the Arnoux-Rauzy morphisms over $\mathcal{A}$. The
morphisms of $AR_{\mathcal{A}}$ are dendric preserving by the previous lemma.
We will now prove that these are, up to a bijective coding, the only dendric
preserving morphisms with domain alphabet $\mathcal{A}$.

######  Lemma 26.

Let $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a dendric preserving
morphism. If $s_{\sigma}p_{\sigma}=\varepsilon$, then $\sigma$ is a bijective
coding between $\mathcal{A}$ and $\mathcal{B}$.

###### Proof.

First, remark that in the case of a two letters alphabet, it directly follows
from the study of Sturmian morphisms. For larger alphabets, it suffices to
prove that all the images of letters have length one as the images of the
letters will then all be different by Proposition 21. Assume by contrary that
there exist $a\in\mathcal{A}$, $b,c\in\mathcal{B}$ such that $bc$ is a factor
of $\sigma(a)$. Let $b^{\prime}$ denote the letter such that
$\sigma(b^{\prime})$ ends with $b$ and $c^{\prime}$ be the letter such that
$\sigma(c^{\prime})$ begins with $c$. Such letters exist by Proposition 21.

Since we are on an alphabet of size at least 3, we can find a dendric bi-
infinite word $x$ over $\mathcal{A}$ such that $b^{\prime}c^{\prime}$ is not
in its language (using Lemma 6 for example).111Note that this is not true if
$b^{\prime}\neq c^{\prime}$ and we are on an alphabet of size $2$. The bi-
infinite word $x$ is dendric thus the vertices $b^{\prime}$ on the left and
$c^{\prime}$ on the right are connected by a unique path in
$\mathcal{E}_{x}(\varepsilon)$ and this path is not reduced to the edge
$(b^{\prime},c^{\prime})$ as this edge does not exist. By Proposition 21, it
implies that $b$ and $c$ are also connected by a path in
$\mathcal{E}_{\sigma(x)}(\varepsilon)$ and that this path is not reduced to
the edge $(b,c)$. However, $bc$ is a factor of $\sigma(a)$ thus $(b,c)$ is an
edge of $\mathcal{E}_{\sigma(x)}(\varepsilon)$ and we have a cycle, a
contradiction since $\sigma(x)$ must be dendric. ∎

######  Lemma 27.

Let $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a dendric preserving
morphism. If $|s_{\sigma}p_{\sigma}|=n>0$, then

  1. 1.

$(s_{\sigma}p_{\sigma})_{1}=(s_{\sigma}p_{\sigma})_{n}=:\ell$ and it is such
that
$E_{\sigma(x)}(\varepsilon)=(\\{\ell\\}\times\mathcal{B})\cup(\mathcal{B}\times\\{\ell\\})$
for any dendric bi-infinite word $x$ over $\mathcal{A}$;

  2. 2.

there exists a dendric preserving morphism
$\tau:\mathcal{A}^{*}\to\mathcal{B}^{*}$ such that
$\sigma\in\\{L_{\ell}\circ\tau,R_{\ell}\circ\tau\\}$. Moreover,
$|s_{\tau}p_{\tau}|<|s_{\sigma}p_{\sigma}|$.

###### Proof.

  1. 1.

Let $x$ be a dendric bi-infinite word over $\mathcal{A}$. By Proposition 21
and since $\operatorname{\\#}\mathcal{A}=\operatorname{\\#}\mathcal{B}$, we
know that $E^{+}_{\sigma(x)}((s_{\sigma}p_{\sigma})_{n})=\mathcal{B}$ and that
$E^{-}_{\sigma(x)}((s_{\sigma}p_{\sigma})_{1})=\mathcal{B}$. We can deduce
that
$E_{\sigma(x)}(\varepsilon)=\left(\\{(s_{\sigma}p_{\sigma})_{n}\\}\times\mathcal{B}\right)\cup\left(\mathcal{B}\times\\{(s_{\sigma}p_{\sigma})_{1}\\}\right)$
since $\varepsilon$ is dendric in $\sigma(x)$. Moreover,
$(s_{\sigma}p_{\sigma})_{1}=(s_{\sigma}p_{\sigma})_{n}$. Indeed, otherwise
$(s_{\sigma}p_{\sigma})_{1}$ is not right special and can only be followed by
itself in $\sigma(x)$. This will contradict the fact that
$(s_{\sigma}p_{\sigma})_{n}$ appears at bounded intervals in $\sigma(x)$.

  2. 2.

Assume that $p_{\sigma}\neq\varepsilon$ and that $(p_{\sigma})_{1}=\ell$.
Thus, for each letter $a\in\mathcal{A}$, $\sigma(a)$ begins with $\ell$.
Moreover, by the first item, any letter other than $\ell$ can only be followed
by $\ell$ in $\sigma(a)$ thus we can find $u$ such that
$\sigma(a)=L_{\ell}(u)$. We then define $\tau$ such that
$\sigma=L_{\ell}\circ\tau$. Remark that, by maximality of $s_{\sigma}$ and
$p_{\sigma}$, we have $s_{\sigma}p_{\sigma}=L_{\ell}(s_{\tau}p_{\tau})\ell$.

If $p_{\sigma}=\varepsilon$ or $(p_{\sigma})_{1}\neq\ell$, then we first show
that, for each letter $a\in\mathcal{A}$, $\sigma(a)$ ends with $\ell$. Using
the first item, for any dendric bi-infinite word $x$, the letter $\ell$
appears in every factor of length 2 of $\sigma(x)$. Therefore, it suffices to
prove that, for each letter $a$, we can find a dendric bi-infinite word $x$
over $\mathcal{A}$ such that $ab\in\mathcal{L}(x)$ where $\sigma(b)$ does not
begin with $\ell$. This is always possible. Indeed, if
$p_{\sigma}=\varepsilon$, by Proposition 21, there is exactly one letter
$a_{0}\in\mathcal{A}$ such that $\sigma(a_{0})$ begins with $\ell$ and if
$(p_{\sigma})_{1}\neq\ell$, there is no such letter. Thus, we can simply take
$x$ such that $a$ is right special to conclude that $\sigma(a)$ ends with
$\ell$. Similarly to what we did previously, we can now define $\tau$ such
that $\sigma=R_{\ell}\circ\tau$. Remark that, $s_{\sigma}p_{\sigma}=\ell
R_{\ell}(s_{\tau}p_{\tau})$.

In both cases, $\tau$ is dendric preserving by Lemma 25 and
$|s_{\tau}p_{\tau}|<|s_{\sigma}p_{\sigma}|$.

∎

######  Theorem 28.

A non-erasing morphism $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ is dendric
preserving if and only if it is, up to a bijective coding, in the monoid
$AR_{\mathcal{A}}$ generated by the Arnoux-Rauzy morphisms.

###### Proof.

The fact that such a morphism is dendric preserving is a direct consequence of
Lemma 25. Assume now that $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ is
dendric preserving. By Corollary 23,
$\operatorname{\\#}\mathcal{A}=\operatorname{\\#}\mathcal{B}$ thus, up to a
bijective coding, we can assume that $\mathcal{A}=\mathcal{B}$. The conclusion
follows from iterating Lemma 27 and from Lemma 26. ∎

As in Remark 22, a careful analysis of the proofs of the previous results
shows that the hypotheses can be reduced. More specifically, we have actually
shown the following result.

######  Theorem 29.

Let $\mathcal{A}$ and $\mathcal{B}$ be such that
$\operatorname{\\#}\mathcal{B}\leq\operatorname{\\#}\mathcal{A}$ and let
$\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ be a non-erasing and non-periodic
morphism, i.e. there exists $x\in\mathcal{A}^{\mathbb{Z}}$ such that
$\sigma(x)$ is not periodic. If there exists a family
$F\subseteq\mathcal{A}^{\mathbb{Z}}$ such that

  1. 1.

for all distinct $a,b,c\in\mathcal{A}$ and all distinct
$a^{\prime},b^{\prime}\in\mathcal{A}$, there exists $x\in F$ such that
$aa^{\prime},ba^{\prime},bb^{\prime},cb^{\prime}$ are factors of $x$, or
$ab^{\prime},bb^{\prime},ba^{\prime},ca^{\prime}$ are factors of $x$,

  2. 2.

for all distinct $a,b\in\mathcal{A}$ and all distinct
$a^{\prime},b^{\prime},c^{\prime}\in\mathcal{A}$, there exists $x\in F$ such
that $aa^{\prime},ab^{\prime},bb^{\prime},bc^{\prime}$ are factors of $x$, or
$ba^{\prime},bb^{\prime},ab^{\prime},ac^{\prime}$ are factors of $x$,

  3. 3.

for all $a,b\in\mathcal{A}$, there exists $x\in F$ such that $ab$ is not a
factor of $x$ but, in $\mathcal{E}_{x}(\varepsilon)$, the left vertex labeled
by $a$ and the right vertex labeled by $b$ are connected,

and if the factors of $s_{\sigma}p_{\sigma}$ are acyclic in $\sigma(x)$ for
all $x\in F$, then $\sigma$ is, up to a bijective coding, in the monoid
$AR_{\mathcal{A}}$.

###### Proof.

Indeed, the existence of $s_{\sigma}$ and $p_{\sigma}$ is guaranteed by Lemma
19. Proposition 21 then derives from item 1, item 2 and the fact that
$s_{\sigma}p_{\sigma}$ is acyclic in the image, and Corollary 23 directly
follows since
$\operatorname{\\#}\mathcal{B}\leq\operatorname{\\#}\mathcal{A}$. For Lemma
26, we use item 3 and the acyclicity of $\varepsilon$ in the image. In Lemma
27, the existence of the morphism $\tau$ is a consequence of the acyclicity of
$\varepsilon$ and of item 3. Moreover, for any bispecial factor $u$ of
$s_{\tau}p_{\tau}$, there is a corresponding factor $v$ of
$s_{\sigma}p_{\sigma}$ such that
$\mathcal{E}_{\tau(x)}(u)=\mathcal{E}_{\sigma(x)}(v)$ for any word $x$ (see
the proof of Lemma 25) thus, for all $x\in F$, the factors of
$s_{\tau}p_{\tau}$ are acyclic in $\tau(x)$ and $\tau$ also satisfies the
conditions. ∎

Remark that, as a consequence of Lemma 6, the family of codings of RIET on an
alphabet of size at least 3 satisfies these properties, a fact that we already
used to obtain the characterization of dendric preserving morphisms. We will
now look at the morphisms preserving the codings of RIET, called _RIET
preserving_ for short.

As a consequence of the combinatorial characterization of RIET (Theorem 5), we
directly obtain the following result which is a particular case of the
stability of interval exchange transformations under induction [14].

######  Corollary 30.

If $L_{\ell}(x)$ (resp., $R_{\ell}(x)$) is the coding of a regular interval
exchange transformation for the orders $\binom{\leq}{\preceq}$, then $x$ is
also the coding of a regular interval exchange transformation for the same
orders.

We now obtain a complete description of RIET preserving morphisms.

######  Theorem 31.

A non-erasing morphism $\sigma:\mathcal{A}^{*}\to\mathcal{B}^{*}$ preserves
the codings of regular interval exchange transformations if and only if we are
in one of the two following cases:

  1. 1.

$\operatorname{\\#}\mathcal{A}=2$ and $\sigma$ is a Sturmian morphism,

  2. 2.

$\operatorname{\\#}\mathcal{A}\geq 3$ and $\sigma$ is a bijective coding.

###### Proof.

Using Theorem 29, it only remains to prove that, on an alphabet of size
greater or equal to $3$, the compositions of Arnoux-Rauzy morphisms do not
preserve the codings of RIET. Moreover, using Corollary 30, it suffices to
prove that the Arnoux-Rauzy morphisms themselves are not RIET preserving.

Let $\ell\in\mathcal{A}$, let $x$ be a coding of a regular interval exchange
transformation associated to the orders $\leq$ and $\preceq$ such that $\ell$
is neither the maximum nor the minimum for $\leq$, and let $y=L_{\ell}(x)$.
The proof is similar for $y=R_{\ell}(x)$. By Theorem 5, the pair of orders
$\binom{\leq}{\preceq}$ is then the only one satisfying items 1 and 2 for all
non empty $w\in\mathcal{L}(y)$. However, it does not satisfy item 1 for the
empty word since
$E_{y}(\varepsilon)=(\\{\ell\\}\times\mathcal{A})\cup(\mathcal{A}\times\\{\ell\\})$.
Thus $y$ is not the coding of an RIET. ∎

##  6 Conclusion

Not much is known about the behavior of dendric and eventually dendric words
when applying a morphism. The results presented in this paper provide some
answers but more general questions remain.

  1. 1.

It is not known whether the family of eventually dendric words is stable under
any morphism. Initial researches seem to suggest that it is the case however,
to our knowledge, there is no proof yet. Note that it is closely related to
the question of stability under topological factorization asked in [7].

  2. 2.

In [10], the authors gave a complete characterization of whether the image of
a dendric word under a given morphism is dendric, for morphisms of a
particular shape. It is natural to wonder if such a characterization exists,
without initial restriction on the morphism.

## Acknowledgment

The author is supported by an FNRS Research Fellow grant. The author would
like to thank Julien Leroy for discussions about the results of this paper.

## References

  * [1] Valérie Berthé, P. Cecchi Bernales, Fabien Durand, Julien Leroy, Dominique Perrin, and Samuel Petite.  On the dimension group of unimodular $\mathcal{S}$-adic subshifts.  Monatsh. Math., 194(4):687–717, 2021.
  * [2] Valérie Berthé, Clelia De Felice, Francesco Dolce, Julien Leroy, Dominique Perrin, Christophe Reutenauer, and Giuseppina Rindone.  Acyclic, connected and tree sets.  Monatsh. Math., 176(4):521–550, 2015.
  * [3] Valérie Berthé, Clelia De Felice, Francesco Dolce, Julien Leroy, Dominique Perrin, Christophe Reutenauer, and Giuseppina Rindone.  Maximal bifix decoding.  Discrete Math., 338(5):725–742, 2015.
  * [4] Valérie Berthé, Francesco Dolce, Fabien Durand, Julien Leroy, and Dominique Perrin.  Rigidity and substitutive dendric words.  Internat. J. Found. Comput. Sci., 29(5):705–720, 2018.
  * [5] Julien Cassaigne and François Nicolas.  Factor complexity.  In Combinatorics, automata and number theory, volume 135 of Encyclopedia Math. Appl., pages 163–247. Cambridge Univ. Press, Cambridge, 2010.
  * [6] Michael Damron and Jon Fickenscher.  The number of ergodic measures for transitive subshifts under the regular bispecial condition.  Ergod. Theory Dyn. Syst., 42(1):86–140, 2022.
  * [7] Francesco Dolce and Dominique Perrin.  Eventually dendric shift spaces.  Ergod. Theory Dyn. Syst., 41(7):2023–2048, 2021.
  * [8] Sébastien Ferenczi and Luca Q. Zamboni.  Languages of $k$-interval exchange transformations.  Bull. Lond. Math. Soc., 40(4):705–714, 2008.
  * [9] France Gheeraert, Marie Lejeune, and Julien Leroy.  $\mathcal{S}$-adic characterization of minimal ternary dendric shifts.  Ergod. Theory Dyn. Syst., 42(11):3393–3432, 2022.
  * [10] France Gheeraert and Julien Leroy.  $\mathcal{S}$-adic characterization of minimal dendric shifts, 2022.  arXiv:2206.00333.
  * [11] Jacques Justin and Giuseppe Pirillo.  Episturmian words and episturmian morphisms.  Theor. Comput. Sci., 276(1-2):281–313, 2002.
  * [12] Michael Keane.  Interval exchange transformations.  Math. Z., 141:25–31, 1975.
  * [13] M. Lothaire.  Algebraic combinatorics on words, volume 90 of Encycl. Math. Appl. Cambridge: Cambridge University Press, 2002.
  * [14] Gérard Rauzy.  Échanges d’intervalles et transformations induites.  Acta Arith., 34(4):315–328, 1979.


212019314723

# Binding Number, Toughness and General Matching Extendability in Graphs

Hongliang Lu1 Supported by the National Natural Science Foundation of China,
No. 11471257 and 11871391. Qinglin Yu2,3 Supported by the Discovery Grant from
the Natural Sciences and Engineering Research Council of Canada, and the
Shanxi Hundred-Talent Program of Shanxi Province.
Corresponding email<EMAIL_ADDRESS>Department of Mathematics, Xi’an Jiaotong
University, Xi’an, China
School of Science, Xi’an Polytechnic University, Xi’an, China
Department of Mathematics and Statistics, Thompson Rivers University,
Kamloops, BC, Canada

(2018-7-31; 2018-12-13)

###### Abstract

A connected graph $G$ with at least $2m+2n+2$ vertices which contains a
perfect matching is $E(m,n)$-extendable, if for any two sets of disjoint
independent edges $M$ and $N$ with $|M|=m$ and $|N|=n$, there is a perfect
matching $F$ in $G$ such that $M\subseteq F$ and $N\cap F=\emptyset$.
Similarly, a connected graph with at least $n+2k+2$ vertices is called
$(n,k)$-extendable if for any vertex set $S$ of size $n$ and any matching $M$
of size $k$ of $G-S$, $G-S-V(M)$ contains a perfect matching. Let
$\varepsilon$ be a small positive constant, $b(G)$ and $t(G)$ be the binding
number and toughness of a graph $G$. The two main theorems of this paper are:
for every graph $G$ with sufficiently large order, 1) if $b(G)\geq
4/3+\varepsilon$, then $G$ is $E(m,n)$-extendable and also $(n,k)$-extendable;
2) if $t(G)\geq 1+\varepsilon$ and $G$ has a high connectivity, then $G$ is
$E(m,n)$-extendable and also $(n,k)$-extendable. It is worth to point out that
the binding number and toughness conditions for the existence of the general
matching extension properties are almost same as that for the existence of
perfect matchings.

###### keywords:

Binding number, toughness, perfect matching, matching extendability

##  1 Introduction

In this paper, we only consider simple connected graphs. Let $G$ be a graph
with vertex set $V(G)$ and edge set $E(G)$. A _matching_ is a set of
independent edges and we often refer a matching with $k$ edges as a
$k$-matching. For a matching $M$, we use $V(M)$ to denote the set of the
endvertices of the edges in $M$ and $|M|$ to denote the number of edges in
$M$. A matching is called a _perfect matching_ if it covers all vertices of
graph $G$. For $S\subseteq V(G)$, we write $G[S]$ for the subgraph of $G$
induced by $S$ and $G-S$ for $G[V(G)\backslash S]$. The number of odd
components (i.e., components with odd order) and the number of components of
$G$ are denoted by $c_{0}(G)$ and $c(G)$, respectively. Let $N_{G}(S)$ denote
the set of neighbors of a set $S$ in a graph $G$, and $\kappa(G)$ denote the
vertex connectivity of graph $G$.

Let $M$ be a matching of $G$. If there is a matching $M^{\prime}$ of $G$ such
that $M\subseteq M^{\prime}$, we say that $M$ can be extended to $M^{\prime}$
or $M^{\prime}$ is an _extension_ of $M$. Suppose that $G$ is a connected
graph with perfect matchings. If each $k$-matching can be extended to a
perfect matching in $G$, then $G$ is called _$k$ -extendable_. To avoid
triviality, we require that $|V(G)|\geq 2k+2$ for $k$-extendable graphs. This
family of graphs was introduced and studied first by Plummer (1980). A graph
$G$ is called $n$-factor-critical if after deleting any $n$ vertices the
remaining subgraph of $G$ has a perfect matching, which was introduced in Yu
(1993) and was a generalization of the notions of the well-known factor-
critical graphs and bicritical graphs (the cases corresponding to $n=1$ and
$2$, respectively). Note that every connected factor-critical graph is 2-edge-
connected (see Yu (1993)).

Let $G$ be a graph and let $n,k$ be nonnegative integers such that $|V(G)|\geq
n+2k+2$ and $|V(G)|-n\equiv 0\pmod{2}$. If deleting any $n$ vertices from $G$
the remaining subgraph of $G$ contains a $k$-matching and moreover, each
$k$-matching in the subgraph can be extended to a perfect matching, then $G$
is called _$(n,k)$ -extendable_ (Liu and Yu (2001)). This term can be
considered as a general framework to unify the concepts of $n$-factor-
criticality and $k$-extendability. In particular, $(n,0)$-extendable graphs
are exactly $n$-factor-critical graphs and $(0,k)$-extendable graphs are the
same as $k$-extendable graphs. A graph is called _$E(m,n)$ -extendable_ if
deleting edges of any $n$-matching, the resulted graph is $m$-extendable
(Porteous and Aldred (1996)). $E(m,0)$-extendability is equivalent to
$m$-extendability, and $(n,k)$-extendability and $E(m,n)$-extendability are
referred as general matching extensions, which are widely studied in graph
theory (see Plummer (1994, 1996, 2008)).

For a non-complete graph $G$, its _toughness_ is defined by

$t(G)=\min_{S\subset V(G)}\frac{|S|}{c(G-S)}$

where $S$ is taken over all cut-sets of $G$. The _binding number_ $b(G)$ is
defined to be the minimum, taken over all $S\subseteq V(G)$ with
$S\neq\emptyset$ and $N_{G}(S)\neq V(G)$, of the ratios
$\frac{|N_{G}(S)|}{|S|}$.

Toughness and binding number have been effective graphic parameters for
studying factors and matching extensions in graphs. For instances, 1-tough
graphs guarantee the existence of perfect matchings (see Chvátal (1973)) and
graphs with $b(G)\geq\frac{4}{3}$ contain perfect matchings (see Woodall
(1973)). There are sufficient conditions with respect to $t(G)$ and $b(G)$ in
terms of $m,n,k$ to ensure the existences of $k$-extendability,
$E(m,n)$-extendability and other matching extensions (see Chen (1995); Liu and
Yu (1998); Plummer (1988a, 2008)). Moreover, Robertshaw and Woodall (2002)
proved a remarkable result that a graph with $b(G)$ slightly greater than
$\frac{4}{3}$ ensure $k$-extendability if the order of $G$ is sufficiently
large. Recently, Plummer and Saito (2017) extended this result to
$E(m,n)$-extendability. In this paper, we continue the study in this direction
and prove that the essential bounds of $t(G)$ and $b(G)$ (i.e., $1$ and
$\frac{4}{3}$) which guarantee the existence of a perfect matching can also
ensure the existence of all general matching extensions mentioned earlier.

Tutte (1947) gave a characterization for a graph to have a perfect matching.

######  Theorem 1.1 (Tutte (1947))

Let $G$ be a graph with even order. Then $G$ contains a perfect matching if
and only if for any $S\subseteq V(G)$

$c_{0}(G-S)\leq|S|.$

The following result is an extension of Tutte’s theorem and also a lean
version of a comprehensive structure theorem for matchings, due to Gallai
(1964) and Edmonds (1965). See Lovász and Plummer (1986) for a detailed
statement and discussion of this theorem.

######  Theorem 1.2 (see Lovász and Plummer (1986))

Let $G$ be a graph with even order. Then $G$ contains no perfect matchings if
and only if there exists a set $S\subset V(G)$ such that

$fc(G-S)\geq|S|+2,$

where $fc(G-S)$ denotes the number of factor-critical components of $G-S$.

The proofs of the main theorems require the following two results as lemmas.

######  Theorem 1.3 (Liu and Yu (2001))

If $G$ is an $(n,k)$-extendable graph and $n\geq 1,k\geq 2$, then $G$ is also
$(n+2,k-2)$-extendable.

######  Theorem 1.4 (Plummer (1988b))

If a graph $G$ is connected and $k$-extendable graph ($k\geq 1$), then $G-e$
is $(k-1)$-extendable for any edge $e$ of $G$.

##  2 Binding Number and Matching Extendability

Chen (1995) proved that a graph $G$ of even order at least $2m+2$ is
$m$-extendable if $b(G)>\max\\{m,(7m+13)/12\\}$. Robertshaw and Woodall (2002)
proved a stronger result (in most cases). We state their result in a simpler
but slightly weaker form below.

######  Theorem 2.1 (Robertshaw and Woodall (2002))

For any positive real number $\varepsilon$ and nonnegative integer $m$, there
exists an integer $N=N(\varepsilon,m)$ such that every graph $G$ of even order
greater than $N$ and $b(G)>4/3+\varepsilon$ is $m$-extendable.

In this section, we extend the above result using a different proof technique.

###### Theorem 2.2

Let $k,g$ be two positive integers such that $g\geq 3$ and let
$g_{0}=2\lfloor\frac{g}{2}\rfloor+1$. For any positive real number
$\varepsilon<\frac{1}{g_{0}}$, there exists $N=N(\varepsilon,k,g_{0})$ such
that for every graph $G$ with order at least $N$ and girth $g$, if
$b(G)>\frac{g_{0}+1}{g_{0}}+\varepsilon$, then $G$ is $k$-extendable.

######  Proof 2.3.

Suppose that the result does not hold. Then there exists a graph $G$ with
order at least $N$ and $b(G)>\frac{g_{0}+1}{g_{0}}+\varepsilon$ such that $G$
is not $k$-extendable. By the definition of $k$-extendable graphs, there
exists a $k$-matching $M$ such that $G-V(M)$ contains no perfect matchings.
From Theorem 1.2, there exists $S\subset V(G)-V(M)$ such that

$fc(G-V(M)-S)=s+q,$

where $q\geq 2$ is even by parity and $s:=|S|$. Let $C_{1},\ldots,C_{s+q}$
denote these factor-critical components of $G-S-V(M)$ such that
$|C_{1}|\leq\cdots\leq|C_{s+q}|$. Without loss of generality, we assume
$|C_{1}|=\ldots=|C_{l}|=1$. Note that $|C_{i}|\geq 3$ implies $g(C_{i})\geq g$
as $C_{i}$ is 2-edge-connected. Thus we have $|C_{i}|\geq g_{0}$ for $l+1\leq
i\leq s+q$. Write $U=\cup_{i=2}^{s+q}V(C_{i})$ and $W=V(G)-U-S-V(M)$. Note
that $V(C_{1})\subseteq W$ and $s+q\geq 2$. So we have $U\neq\emptyset$ and
$W\neq\emptyset$. One may see that $N(U)\cap W=\emptyset$ and $N(W)\cap
U=\emptyset$. Hence $N(U)\not=V(G)$ and $N(W)\not=V(G)$. Denote
$r=\max\\{2,l+1\\}$. Thus we have

$\displaystyle b(G)$
$\displaystyle\leq\min\\{\frac{|N(U)|}{|U|},\frac{|N(W)|}{|W|}\\}$
$\displaystyle\leq\min\\{\frac{2k+s+\sum_{i=r}^{s+q}|C_{i}|}{r-2+\sum_{i=r}^{s+q}|C_{i}|},\frac{|G|-\sum_{i=2}^{s+q}|C_{i}|}{|G|-2k-s-\sum_{i=2}^{s+q}|C_{i}|}\\}$
$\displaystyle=\min\\{f,h\\}$

where $f=\frac{2k+s+\sum_{i=r}^{s+q}|C_{i}|}{r-2+\sum_{i=r}^{s+q}|C_{i}|}$ and
$h=\frac{|G|-\sum_{i=2}^{s+q}|C_{i}|}{|G|-2k-s-\sum_{i=2}^{s+q}|C_{i}|}$.

Claim 1.  $2k+s>r-2$.

This claim is implied by the following inequality:

$\displaystyle 1<\frac{g_{0}+1}{g_{0}}+\varepsilon<b(G)\leq
f=\frac{2k+s+\sum_{i=r}^{s+q}|C_{i}|}{r-2+\sum_{i=r}^{s+q}|C_{i}|},$

Claim 2.  $\sum_{i=r}^{s+q}|C_{i}|<g_{0}(2k+s)$.

Suppose that $\sum_{i=r}^{s+q}|C_{i}|\geq g_{0}(2k+s)$. By Claim 1, we have

$\displaystyle b(G)\leq f$
$\displaystyle\leq\frac{2k+s+g_{0}(2k+s)}{r-2+g_{0}(2k+s)}$
$\displaystyle\leq\frac{2k+s+g_{0}(2k+s)}{g_{0}(2k+s)}$
$\displaystyle=\frac{g_{0}+1}{g_{0}},$

a contradiction.

Claim 3.  $s<\max\\{2(g_{0}-1)k,\frac{2k}{g_{0}\varepsilon}\\}$.

Suppose that $s\geq\max\\{2(g_{0}-1)k,\frac{2k}{g_{0}\varepsilon}\\}$. Since
$s\geq 2(g_{0}-1)k$, we infer that

$\displaystyle\frac{s(g_{0}+1)+2k}{g_{0}s}\leq\frac{g_{0}}{g_{0}-1}.$ (1)

If

$\displaystyle\frac{g_{0}+1}{g_{0}}+\varepsilon<\frac{(g_{0}+1)s+2k}{g_{0}s},$
(2)

then $s<\frac{2k}{g_{0}\varepsilon}$, a contradiction. So it is enough for us
to show (2). Consider $q<r-1$. Then we infer that

$\displaystyle\frac{g_{0}+1}{g_{0}}+\varepsilon<f$
$\displaystyle\leq\frac{2k+s+g_{0}(s+q-r+1)}{r-2+g_{0}(s+q-r+1)}\quad\quad\mbox{(by
Claim 1 and $\sum_{i=r}^{s+q}|C_{i}|\geq g_{0}(s+q-r+1)$})$
$\displaystyle=\frac{s(g_{0}+1)+2k+g_{0}(q-r+1)}{g_{0}s+g_{0}(q-r+1)+r-2}$
$\displaystyle<\frac{s(g_{0}+1)+2k+g_{0}(q-r+1)}{g_{0}s+g_{0}(q-r+1)+r-1-q}$
$\displaystyle=\frac{s(g_{0}+1)+2k-g_{0}(r-1-q)}{g_{0}s-(g_{0}-1)(r-1-q)}$
$\displaystyle\leq\frac{(g_{0}+1)s+2k}{g_{0}s}.\quad\quad\mbox{(by
(\ref{g0-ratio}) and $g_{0}s+g_{0}(q-r+1)>q-r+1$)}$

Next, we consider $q\geq r-1$, then

$\displaystyle\frac{g_{0}+1}{g_{0}}+\varepsilon<f$
$\displaystyle\leq\frac{2k+s+g_{0}(s+q-r+1)}{r-2+g_{0}(s+q-r+1)}\quad\quad\mbox{(by
Claim 1 and $\sum_{i=r}^{s+q}|C_{i}|\geq g_{0}(s+q-r+1)$})$
$\displaystyle\leq\frac{2k+s+g_{0}(s+q^{\prime}-r+1)}{r-2+g_{0}(s+q^{\prime}-r+1)}\quad\quad\mbox{(for
any $q^{\prime}$ satisfying $q\geq q^{\prime}\geq r-1$})$
$\displaystyle=\frac{s(g_{0}+1)+2k}{g_{0}s+r-2}$
$\displaystyle\leq\frac{(g_{0}+1)s+2k}{g_{0}s}.$

This completes the proof of Claim 3.

Claim 4.  $l<\max\\{2g_{0}k+1,\frac{2k}{g_{0}\varepsilon}+1\\}$.

Suppose that $l\geq\max\\{2g_{0}k+1,\frac{2k}{g_{0}\varepsilon}+1\\}$. From
Claim 3, we have

$\displaystyle s<\max\\{2(g_{0}-1)k,\frac{2k}{g_{0}\varepsilon}\\}.$ (3)

From (3), we see $l\geq s+1$ and thus

$\displaystyle\frac{g_{0}+1}{g_{0}}+\varepsilon<\ f$
$\displaystyle=\frac{2k+s+\sum_{i=r}^{s+q}|C_{i}|}{r-2+\sum_{i=r}^{s+q}|C_{i}|}$
$\displaystyle=\frac{2k+s+\sum_{i=r}^{s+q}|C_{i}|}{l-1+\sum_{i=r}^{s+q}|C_{i}|}$
$\displaystyle\leq\frac{2k+s}{l-1}\quad\quad\mbox{(by Claim 1)}$
$\displaystyle\leq\frac{2k+l-1}{l-1}$
$\displaystyle\leq\frac{g_{0}+1}{g_{0}},\quad\quad\mbox{(since $l\geq
2g_{0}k+1$)}$

a contradiction.

From Claim 2, we have

$\displaystyle\sum_{i=r}^{s+q}|C_{i}|<g_{0}(2k+s).$ (4)

Thus

$\displaystyle\frac{g_{0}+1}{g_{0}}+\varepsilon<h$
$\displaystyle=\frac{|G|-\sum_{i=2}^{s+q}|C_{i}|}{|G|-2k-s-\sum_{i=2}^{s+q}|C_{i}|}$
$\displaystyle=\frac{|G|-(r-2)-\sum_{i=r}^{s+q}|C_{i}|}{|G|-2k-s-(r-2)-\sum_{i=r}^{s+q}|C_{i}|}$
$\displaystyle\leq\frac{|G|-(r-2)-g_{0}(2k+s)}{|G|-2k-s-(r-2)-g_{0}(2k+s)}\quad\mbox{(by
(\ref{sum-Ci}))}$ $\displaystyle\leq\frac{|G|-l-g_{0}(2k+s)}{|G|-2k-s-l-
g_{0}(2k+s)}\quad\mbox{(since $r=\max\\{2,l+1\\}\leq l+2$)}$
$\displaystyle=\frac{|G|-2kg_{0}-g_{0}s-l}{|G|-2k-2kg_{0}-(g_{0}+1)s-l},$

i.e.,

$\displaystyle\frac{g_{0}+1}{g_{1}}+\varepsilon<\frac{|G|-2kg_{0}-g_{0}s-l}{|G|-2k-2kg_{0}-(g_{0}+1)s-l}.$
(5)

Claims 2 and 3 imply that $s,l$ are bounded, therefore

$\lim_{|G|\rightarrow\infty}\frac{|G|-2kg_{0}-g_{0}s-l}{|G|-2k-2kg_{0}-(g_{0}+1)s-l}=1.$

For a large $N$, (5) leads to a contradiction when $|G|>N$. This completes the
proof.

Clearly, Theorem 2.2 is a generalization of Theorem 2.1. For connected graphs
$G$, the girth $g$ of $G$ is at least three. Setting $g_{0}=3$, we obtain the
following results regarding the general matching extensions (i.e., stronger
properties).

###### Corollary 2.4

Let $n,k$ be two positive integers. For any $\varepsilon<1/3$, there exists
$N=N(\varepsilon,n,k)$ such that if $b(G)>\frac{4}{3}+\varepsilon$ and the
order of $G$ is at least $N$, then $G$ is $(n,k)$-extendable.

######  Proof 2.5.

Since $b(G)>\frac{4}{3}+\varepsilon$, by Theorem 2.1, for a sufficiently large
$|G|$, $G$ is $(k+2n)$-extendable or $(0,k+2n)$-extendable. By Theorem 1.3,
$G$ is $(n,k)$-extendable.

With similar discussion as in Corollary 2.4, we can deduce
$E(m,n)$-extendability with the same conditions, which is a result proved in
Plummer and Saito (2017) but here we gave a much shorter proof.

###### Corollary 2.6

Let $m,n$ be two positive integers. For any $\varepsilon<\frac{1}{3}$, there
exists $N=N(\varepsilon,m,n)$ such that for every graph $G$ with order at
least $N$, if $b(G)>\frac{4}{3}+\varepsilon$, then $G$ is $E(m,n)$-extendable.

######  Proof 2.7.

Since $b(G)>\frac{4}{3}+\varepsilon$, by Theorem 2.1, for a sufficiently large
$|G|$, $G$ is $(m+n)$-extendable. Let $M=\\{e_{1},e_{2},\dots,e_{n}\\}$ be any
$n$-matching. By Theorem 1.4, $G_{1}=G-e_{1}$ is $(m+n-1)$-extendable.
Applying Theorem 1.4 recursively, we conclude that
$G_{n}=G-\\{e_{1},e_{2},\dots,e_{n}\\}$ is $m$-extendable, that is, $G$ is
$E(m,n)$-extendable.

Remark: Clearly, Corollaries 2.4 and 2.6 can be easily stated in terms of the
more general condition $b(G)>\frac{g_{0}+1}{g_{0}}+\varepsilon$. However,
without the parameter $g$, the results look more neatly.

##  3 Toughness and Matching Extendability

It is not hard to construct examples with any given large toughness, but do
not have $(n,k)$-extendability or $E(m,n)$-extendability. Therefore toughness
alone is insufficient to guarantee the general matching extension properties.
However, with an additional condition in terms of connectivity, it only
requires slightly large than 1-toughness to deduce the desired matching
extendability.

######  Theorem 3.1.

Let $n$ be a positive integer, $\varepsilon$ be a small positive constant and
$G$ be a graph with $t(G)\geq 1+\varepsilon$ and $|V(G)|\equiv n\pmod{2}$. If
$\kappa(G)>\frac{(n-2)(1+\varepsilon)}{\varepsilon}$, then $G$ is $n$-factor-
critical.

######  Proof 3.2.

Suppose that $G$ is not $n$-factor-critical. By the definition of $n$-factor-
critical, there exists a subset $S$ of order $n$ such that $G-S$ contains no
perfect matchings. By Theorem 1.1, there exists $T\subseteq V(G)-S$ such that

$q=c_{0}(G-S-T)\geq|T|+2.$

Note that $q\geq 2$. So

$\displaystyle 1+\varepsilon\leq t(G)$
$\displaystyle\leq\frac{|S|+|T|}{|T|+2}$
$\displaystyle\leq\frac{\kappa}{\kappa-n+2},\quad\quad\mbox{(since $\kappa\leq
n+|T|$)}$

which implies

$\kappa\leq\frac{(n-2)(1+\varepsilon)}{\varepsilon},$

a contradiction. This completes the proof.

Remark: The connectivity condition in the theorem is sharp. Let $n,t$ be two
positive integers and $\varepsilon$ be a small constant such that
$n+t<\frac{(n-2)(1+\varepsilon)}{\varepsilon}$. Let $G_{1}=K_{n+t}$,
$G_{2}=(t+1)K_{1}$, and $G_{3}=K_{r}$ ($r$ is any positive integer). Define
$G=G_{1}+(G_{2}\cup G_{3})$, that is, $G$ is a graph obtained by connecting
each vertex in $G_{1}$ to each vertex in $G_{2}$ and $G_{3}$. Let
$S=V(G_{1})$. Then $S$ is a cut set of $G$ and thus $\kappa\leq
n+t\leq\frac{(n-2)(1+\varepsilon)}{\varepsilon}$. It is easy to verify that

$t(G)=\frac{|S|}{c(G-S)}=\frac{n+t}{t+2}\geq 1+\varepsilon.$

However, for any set $R$ of $n$ vertices in $S$, $G-R$ has no perfect
matchings. So $G$ is not $n$-factor-critical.

From Theorem 3.1, it is easy to see the following.

###### Corollary 3.3

Let $n,k$ be two positive integers. Let $\varepsilon$ be a positive constant
and $G$ be a graph with $t(G)\geq 1+\varepsilon$. If
$\kappa(G)>\frac{(2k-2)(1+\varepsilon)}{\varepsilon}$, then $G$ is
$k$-extendable.

With the same arguments as in the proof of Corollary 2.6, Theorem 3.1 implies
the following.

###### Corollary 3.4

Let $m,n$ be two positive integers. Let $\varepsilon$ be a positive constant
and $G$ be a graph with $t(G)\geq 1+\varepsilon$. If
$\kappa(G)>\frac{(2m+2n-2)(1+\varepsilon)}{\varepsilon}$, then $G$ is
$E(m,n)$-extendable.

###### Acknowledgements.

The authors are grateful to an anonymous referee for his/her useful
suggestions.

## References

  * Chen (1995) C. P. Chen.  Binding number and toughness for matching extension.  _Discrete Math._ , 146:303–306, 1995.
  * Chvátal (1973) V. Chvátal.  Tough graphs and hamiltonian circuits.  _Discrete Math._ , 5:215–228, 1973.
  * Liu and Yu (1998) G. Liu and Q. Yu.  Toughness and perfect matchings in graphs.  _Ars Combin._ , 48:129–134, 1998.
  * Liu and Yu (2001) G. Liu and Q. Yu.  Generalization of matching extensions in graphs.  _Discrete Math._ , 231:311–320, 2001.
  * Lovász and Plummer (1986) L. Lovász and M. D. Plummer.  Matching theory.  volume 29 of _Annals of Discrete Mathematics_. North-Holland, 1986\.
  * Plummer (1980) M. D. Plummer.  On $n$-extendable graphs.  _Discrete Math._ , 31:201–210, 1980.
  * Plummer (1988a) M. D. Plummer.  Toughness and matching extension in graphs.  _Discrete Math._ , 72:311–320, 1988a.
  * Plummer (1988b) M. D. Plummer.  Matching extension and connectivity in graphs.  _Congress. Numer._ , 63:147–160, 1988b.
  * Plummer (1994) M. D. Plummer.  Extending matching in graphs: a survey.  _Discrete Math._ , 127:277–292, 1994.
  * Plummer (1996) M. D. Plummer.  Extending matching in graphs: an update.  _Congress. Numer._ , 116:3–32, 1996.
  * Plummer (2008) M. D. Plummer.  Recent progress in matching extension, building bridges.  volume 19 of _Bolyai Soc. Math. Stud._ , pages 427–454. Springer, Berlin, 2008.
  * Plummer and Saito (2017) M. D. Plummer and A. Saito.  Toughness, binding number and restricted matching extension in a graph.  _Discrete Math._ , 340:2665–2672, 2017.
  * Porteous and Aldred (1996) M. Porteous and R. E. L. Aldred.  Matching extensions with prescribed and forbidden edges.  _Australas. J. Combin._ , 13:163–174, 1996.
  * Robertshaw and Woodall (2002) A. M. Robertshaw and D. R. Woodall.  Binding number conditions for matching extension.  _Discrete Math._ , 248:169–179, 2002.
  * Tutte (1947) W. T. Tutte.  The factorization of linear graphs.  _J. Lond. Math. Soc._ , 22:107–111, 1947.
  * Woodall (1973) D. R. Woodall.  The binding number of a graph and its anderson number.  _J. Combin. Theory Ser. B_ , 15:225–255, 1973.
  * Yu (1993) Q. Yu.  Characterizations of various matching extensions in graphs.  _Australas. J. Combin._ , 7:55–64, 1993.