# Word-representability of split graphs generated by morphisms

Kittitat Iamthong111Department of Mathematics and Statistics, University of
Strathclyde, 26 Richmond Street Glasgow G1 1XH, United Kingdom. Email:
<EMAIL_ADDRESS>.

###### Abstract

A graph $G=(V,E)$ is word-representable if and only if there exists a word $w$
over the alphabet $V$ such that letters $x$ and $y$, $x\neq y$, alternate in
$w$ if and only if $xy\in E$. A split graph is a graph in which the vertices
can be partitioned into a clique and an independent set. There is a long line
of research on word-representable graphs in the literature, and recently,
word-representability of split graphs has attracted interest.

In this paper, we first give a characterization of word-representable split
graphs in terms of permutations of columns of the adjacency matrices. Then, we
focus on the study of word-representability of split graphs obtained by
iterations of a morphism, the notion coming from combinatorics on words. We
prove a number of general theorems and provide a complete classification in
the case of morphisms defined by $2\times 2$ matrices.

##  1 Introduction

A graph $G=(V,E)$ is word-representable if and only if there exists a word $w$
over the alphabet $V$ such that letters $x$ and $y$, $x\neq y$, alternate in
$w$ if and only if $xy\in E$. In this definition, letters $x$ and $y$
alternate in $w$ if after removing all letters but $x$ and $y$, we would
either get a word of the form $xyxy\cdots$, or of the form $yxyx\cdots$, of
even or odd length. Also, by definition, $w$ must contain each letter in $V$
at least once. For example, the cycle graph on four vertices labeled 1, 2, 3,
4 in clockwise direction is word-representable because it can be represented
by the word 14213243.

There is a long line of research on word-representable graphs in the
literature that is summarized in [5]. Word-representable graphs are important
as they generalize several well-known and well-studied classes of graphs such
as 3-colorable graphs, comparability graphs and circle graphs [6]. Note that
the class of word-representable graphs is hereditary, that is, removing a
vertex in a word-representable graph results in a word-representable graph.
The wheel graph $W_{5}$ is the smallest non-word-representable graph. One of
the key results in the area is the following theorem, where an orientation of
a graph is semi-transitive if it is acyclic, and for any directed path
$v_{0}\rightarrow v_{1}\rightarrow\cdots\rightarrow v_{k}$ either there is no
edge between $v_{0}$ and $v_{k}$, or $v_{i}\rightarrow v_{j}$ is an edge for
all $0\leq i<j\leq k$.

######  Theorem 1 ([4]).

A graph is word-representable if and only if it admits a semi-transitive
orientation.

The following simple lemma will also be of use to us in this paper.

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

Let $K_{m}$ be a clique in a graph $G$. Then any acyclic orientation of $G$
induces a transitive orientation on $K_{m}$ (where the presence of edges
$u\rightarrow v$ and $v\rightarrow z$ implies the presence of the edge
$u\rightarrow z$). In particular, any semi-transitive orientation of $G$
induces a transitive orientation on $K_{m}$. In either case, the orientation
induced on $K_{m}$ contains a single source and a single sink.

###  1.1 Split graphs.

A split graph is a graph in which the vertices can be partitioned into a
clique and an independent set [3]. The paper [7] initiated a systematic study
of word-representability of split graphs, which was extended in a follow up
paper [1]. In particular, characterizations of split graphs in terms of
forbidden induced subgraphs were obtained in [7] and [1] for cliques of sizes
4 and 5, respectively. Also, a characterization of semi-transitive
orientations of split graphs was obtained in [7] (see below), and split graphs
were used to solve a long standing problem in the theory of word-
representation in [1]. We note though that currently a complete
characterization of split graphs (e.g. in terms of forbidden subgraphs) seems
to be a non-feasible problem, so a natural research direction is in
understanding (non-)word-representable subclasses of split graphs.

type A | type B | sourcesinktype C
---|---|---
Figure 1:  Three types of vertices in $E_{n-m}$ in a semi-transitive
orientation of $(E_{n-m},K_{m})$. The vertical oriented paths are a schematic
way to show (parts of) $\vec{P}$

Let $S_{n}=(E_{n-m},K_{m})$ be a word-representable split graph, where $K_{m}$
is the maximal clique, and $E_{n-m}$ is the independent set. Then, by Theorem
1, $S_{n}$ admits a semi-transitive orientation. Further, by Lemma 2 we know
that any such orientation induces a transitive orientation on $K_{m}$ with the
longest directed path $\vec{P}$. Theorem 5 below characterizes semi-transitive
orientations of split graphs.

######  Theorem 3 ([7]).

Any semi-transitive orientation of a split graph $S_{n}=(E_{n-m},K_{m})$
subdivides the set of all vertices in $E_{n-m}$ into three, possibly empty,
groups corresponding to each of the following types (also shown schematically
in Figure 1), where $\vec{P}=p_{1}\rightarrow\cdots\rightarrow p_{m}$ is the
longest directed path in $K_{m}$:

  * •

A vertex in $E_{n-m}$ is of type A if it is a source and is connected to all
vertices in $\\{p_{i},p_{i+1},\ldots,p_{j}\\}$ for some $1\leq i\leq j\leq m$;

  * •

A vertex in $E_{n-m}$ is of type B if it is a sink and is connected to all
vertices in $\\{p_{i},p_{i+1},\ldots,p_{j}\\}$ for some $1\leq i\leq j\leq m$;

  * •

A vertex $v\in E_{n-m}$ is of type C if there is an edge $x\rightarrow v$ for
each $x\in I_{v}=\\{p_{1},p_{2},\ldots,p_{i}\\}$ and there is an edge
$v\rightarrow y$ for each $y\in O_{v}=\\{p_{j},p_{j+1},\ldots,p_{m}\\}$ for
some $1\leq i<j\leq m$.

There are additional restrictions, given by the next theorem, on relative
positions of the neighbours of vertices of types A, B and C.

######  Theorem 4 ([7]).

Let $S_{n}=(E_{n-m},K_{m})$ be oriented semi-transitively with
$\vec{P}=p_{1}\rightarrow\cdots\rightarrow p_{m}$. For a vertex $x\in E_{n-m}$
of type C, there is no vertex $y\in E_{n-m}$ of type A or B, which is
connected to both $p_{|I_{x}|}$ and $p_{m-|O_{x}|+1}$. Also, there is no
vertex $y\in E_{n-m}$ of type C such that either $I_{y}$, or $O_{y}$ contains
both $p_{|I_{x}|}$ and $p_{m-|O_{x}|+1}$.

One can now classify semi-transitive orientations on split graphs.

######  Theorem 5 ([7]).

An orientation of a split graph $S_{n}=(E_{n-m},K_{m})$ is semi-transitive if
and only if

  * (i)

$K_{m}$ is oriented transitively;

  * (ii)

each vertex in $E_{n-m}$ is of one of the three types in Theorem 3;

  * (iii)

the restrictions in Theorem 4 are satisfied.

###  1.2 Split graphs generated by morphisms

Let $A$ and $B$ be alphabets (possibly $A=B$). A map $\varphi:A^{*}\rightarrow
B^{*}$ is called a morphism, if we have $\varphi(uv)=\varphi(u)\varphi(v)$ for
any $u,v\in A^{*}$. A morphism $\varphi$ can be defined by defining
$\varphi(a)$ for each $a\in A$. A particular property of a morphism $\varphi$
is that $\varphi(\varepsilon)=\varepsilon$, where $\varepsilon$ is the empty
word. Morphisms are a central object in the area of combinatorics on words
[8], and there is a natural extension of the notion to two, or more,
dimensions. Indeed, one can begin with a matrix $M$ whose entries are elements
of $A$, and then obtain $\varphi(M)$ by substituting each element in $M$ by
matrices having the same dimensions and given by some substitution rules.

Relevance of (2-dimensional) morphisms to split graphs is coming through the
ideas communicated in [2], where patterns in adjacency matrices are considered
to study word-representability of graphs, and the notion of an infinite word-
representable graph is introduced. In this paper, we study word-
representability of families of split graphs defined by iteration of
morphisms, and in particular, we give a complete classification in the case of
$2\times 2$ matrices. However, a key theorem we prove that characterizes word-
representability of split graphs in terms of permutations of columns in the
adjacency matrix is applicable to any split graph (see Theorem 15).

###  1.3 Organization of the paper

After introducing a number of preliminary results and examples in Section 2,
that includes our key result (Theorem 15), in Section 3 we present a number of
general results on split graphs generated by morphisms. In Section 4 we
provide a complete classification of word-representable split graphs defined
by iteration of morphisms using two $2\times 2$ matrices; our results in this
section are summarized in Tables 1 and 2. Finally, in Section 5 we state a
number of open research questions.

Case | $A$ | $B$ |  $\rm IWR$$(A,B)$ | Ref. | Case | $A$ | $B$ |  $\rm IWR$$(A,B)$ | Ref.
---|---|---|---|---|---|---|---|---|---
1 | $\begin{bmatrix}0&0\\\ 0&0\end{bmatrix}$ | $\begin{bmatrix}*&*\\\ *&*\end{bmatrix}$ | $\infty$ | $A=0$ |  |  |  |  |
2 | $\begin{bmatrix}1&0\\\ 0&0\end{bmatrix}$ | $\begin{bmatrix}0&0\\\ 0&0\end{bmatrix}$ | $\infty$ |  Prop. 24 | 18 | $\begin{bmatrix}0&1\\\ 0&0\end{bmatrix}$ | $\begin{bmatrix}0&0\\\ 0&0\end{bmatrix}$ | $\infty$ |  Prop. 24
3 |  | $\begin{bmatrix}1&0\\\ 0&0\end{bmatrix}$ | $\infty$ |  Cor. 22 | 19 |  | $\begin{bmatrix}1&0\\\ 0&0\end{bmatrix}$ | 3 |  Rem. 32
4 |  | $\begin{bmatrix}0&1\\\ 0&0\end{bmatrix}$ | 3 |  Pro. 31 | 20 |  | $\begin{bmatrix}0&1\\\ 0&0\end{bmatrix}$ | $\infty$ |  Cor. 22
5 |  | $\begin{bmatrix}0&0\\\ 1&0\end{bmatrix}$ | 3 |  Rem. 32 | 21 |  | $\begin{bmatrix}0&0\\\ 1&0\end{bmatrix}$ | 4 |  Rem. 34
6 |  | $\begin{bmatrix}0&0\\\ 0&1\end{bmatrix}$ | 4 |  Prop. 33 | 22 |  | $\begin{bmatrix}0&0\\\ 0&1\end{bmatrix}$ | 3 |  Rem. 32
7 |  | $\begin{bmatrix}1&1\\\ 0&0\end{bmatrix}$ | $\infty$ |  Rem 43 | 23 |  | $\begin{bmatrix}1&1\\\ 0&0\end{bmatrix}$ | $\infty$ |  Rem 43
8 |  | $\begin{bmatrix}1&0\\\ 1&0\end{bmatrix}$ | $\infty$ |  Rem 43 | 24 |  | $\begin{bmatrix}1&0\\\ 1&0\end{bmatrix}$ | 3 |  Rem. 32
9 |  | $\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$ | $\infty$ |  Prop 44 | 25 |  | $\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$ | 3 |  Rem. 32
10 |  | $\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$ | 3 |  Rem. 32 | 26 |  | $\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$ | $\infty$ |  Rem 45
11 |  | $\begin{bmatrix}0&1\\\ 0&1\end{bmatrix}$ | 3 |  Rem. 32 | 27 |  | $\begin{bmatrix}0&1\\\ 0&1\end{bmatrix}$ | $\infty$ |  Rem 43
12 |  | $\begin{bmatrix}0&0\\\ 1&1\end{bmatrix}$ | 3 |  Rem. 32 | 28 |  | $\begin{bmatrix}0&0\\\ 1&1\end{bmatrix}$ | 3 |  Rem. 32
13 |  | $\begin{bmatrix}1&1\\\ 1&0\end{bmatrix}$ | $\infty$ |  Rem 43 | 29 |  | $\begin{bmatrix}1&1\\\ 1&0\end{bmatrix}$ | 3 |  Rem. 32
14 |  | $\begin{bmatrix}1&1\\\ 0&1\end{bmatrix}$ | 3 |  Rem. 32 | 30 |  | $\begin{bmatrix}1&1\\\ 0&1\end{bmatrix}$ | $\infty$ |  Rem 43
15 |  | $\begin{bmatrix}1&0\\\ 1&1\end{bmatrix}$ | 3 |  Rem. 32 | 31 |  | $\begin{bmatrix}1&0\\\ 1&1\end{bmatrix}$ | 2 |  Rem. 30
16 |  | $\begin{bmatrix}0&1\\\ 1&1\end{bmatrix}$ | 2 |  Prop. 29 | 32 |  | $\begin{bmatrix}0&1\\\ 1&1\end{bmatrix}$ | 3 |  Rem. 32
17 |  | $\begin{bmatrix}1&1\\\ 1&1\end{bmatrix}$ | 3 |  Rem. 32 | 33 |  | $\begin{bmatrix}1&1\\\ 1&1\end{bmatrix}$ | 3 |  Rem. 32
34 | $\begin{bmatrix}0&0\\\ 0&1\end{bmatrix}$ | $\begin{bmatrix}0&0\\\ 0&0\end{bmatrix}$ | $\infty$ |  Prop. 24 | 50 | $\begin{bmatrix}1&1\\\ 0&0\end{bmatrix}$ | $\begin{bmatrix}0&0\\\ 0&0\end{bmatrix}$ | $\infty$ |  Prop. 24
35 |  | $\begin{bmatrix}1&0\\\ 0&0\end{bmatrix}$ | 4 |  Rem. 34 | 51 |  | $\begin{bmatrix}1&0\\\ 0&0\end{bmatrix}$ | $\infty$ |  Rem 43
36 |  | $\begin{bmatrix}0&1\\\ 0&0\end{bmatrix}$ | 3 |  Rem. 32 | 52 |  | $\begin{bmatrix}0&1\\\ 0&0\end{bmatrix}$ | $\infty$ |  Rem 43
37 |  | $\begin{bmatrix}0&0\\\ 1&0\end{bmatrix}$ | 3 |  Rem. 32 | 53 |  | $\begin{bmatrix}0&0\\\ 1&0\end{bmatrix}$ | 4 |  Rem. 34
38 |  | $\begin{bmatrix}0&0\\\ 0&1\end{bmatrix}$ | $\infty$ |  Cor. 22 | 54 |  | $\begin{bmatrix}0&0\\\ 0&1\end{bmatrix}$ | 4 |  Rem. 34
39 |  | $\begin{bmatrix}1&1\\\ 0&0\end{bmatrix}$ | 3 |  Rem. 32 | 55 |  | $\begin{bmatrix}1&1\\\ 0&0\end{bmatrix}$ | $\infty$ |  Cor. 22
40 |  | $\begin{bmatrix}1&0\\\ 1&0\end{bmatrix}$ | 3 |  Rem. 32 | 56 |  | $\begin{bmatrix}1&0\\\ 1&0\end{bmatrix}$ | $\infty$ |  Rem 43
41 |  | $\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$ | $\infty$ |  Rem 45 | 57 |  | $\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$ | 3 |  Rem. 32
42 |  | $\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$ | 3 |  Rem. 32 | 58 |  | $\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$ | 3 |  Rem. 32
43 |  | $\begin{bmatrix}0&1\\\ 0&1\end{bmatrix}$ | $\infty$ |  Rem 43 | 59 |  | $\begin{bmatrix}0&1\\\ 0&1\end{bmatrix}$ | $\infty$ |  Rem 43
44 |  | $\begin{bmatrix}0&0\\\ 1&1\end{bmatrix}$ | $\infty$ |  Rem 43 | 60 |  | $\begin{bmatrix}0&0\\\ 1&1\end{bmatrix}$ | $\infty$ |  Prop. 24
45 |  | $\begin{bmatrix}1&1\\\ 1&0\end{bmatrix}$ | 2 |  Rem. 30 | 61 |  | $\begin{bmatrix}1&1\\\ 1&0\end{bmatrix}$ | $\infty$ |  Rem 43
46 |  | $\begin{bmatrix}1&1\\\ 0&1\end{bmatrix}$ | 3 |  Rem. 32 | 62 |  | $\begin{bmatrix}1&1\\\ 0&1\end{bmatrix}$ | $\infty$ |  Rem 43
47 |  | $\begin{bmatrix}1&0\\\ 1&1\end{bmatrix}$ | 3 |  Rem. 32 | 63 |  | $\begin{bmatrix}1&0\\\ 1&1\end{bmatrix}$ | 4 |  Rem. 34
48 |  | $\begin{bmatrix}0&1\\\ 1&1\end{bmatrix}$ | $\infty$ |  Rem 43 | 64 |  | $\begin{bmatrix}0&1\\\ 1&1\end{bmatrix}$ | 4 |  Rem. 34
49 |  | $\begin{bmatrix}1&1\\\ 1&1\end{bmatrix}$ | 3 |  Rem. 32 | 65 |  | $\begin{bmatrix}1&1\\\ 1&1\end{bmatrix}$ | $\infty$ |  Prop. 24
Table 1: The index of word-representability of infinite split graphs $G(A,B)$ for $2\times 2$ matrices $A$ and $B$. Case | A | B |  $\rm IWR$$(A,B)$ | Ref. | Case | A | B |  $\rm IWR$$(A,B)$ | Ref.
---|---|---|---|---|---|---|---|---|---
66 | $\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$ | $\begin{bmatrix}0&0\\\ 0&0\end{bmatrix}$ | 3 |  Rem. 32 | 82 | $\begin{bmatrix}0&1\\\ 0&1\end{bmatrix}$ | $\begin{bmatrix}0&0\\\ 0&0\end{bmatrix}$ | $\infty$ |  Prop. 24
67 |  | $\begin{bmatrix}1&0\\\ 0&0\end{bmatrix}$ | 3 |  Rem. 32 | 83 |  | $\begin{bmatrix}1&0\\\ 0&0\end{bmatrix}$ | 4 |  Rem. 34
68 |  | $\begin{bmatrix}0&1\\\ 0&0\end{bmatrix}$ | 3 |  Rem. 32 | 84 |  | $\begin{bmatrix}0&1\\\ 0&0\end{bmatrix}$ | $\infty$ |  Rem 43
69 |  | $\begin{bmatrix}0&0\\\ 1&0\end{bmatrix}$ | 3 |  Rem. 32 | 85 |  | $\begin{bmatrix}0&0\\\ 1&0\end{bmatrix}$ | 4 |  Rem. 34
70 |  | $\begin{bmatrix}0&0\\\ 0&1\end{bmatrix}$ | 3 |  Rem. 32 | 86 |  | $\begin{bmatrix}0&0\\\ 0&1\end{bmatrix}$ | $\infty$ |  Rem 43
71 |  | $\begin{bmatrix}1&1\\\ 0&0\end{bmatrix}$ | 3 |  Rem. 32 | 87 |  | $\begin{bmatrix}1&1\\\ 0&0\end{bmatrix}$ | 4 |  Rem. 34
72 |  | $\begin{bmatrix}1&0\\\ 1&0\end{bmatrix}$ | 3 |  Rem. 32 | 88 |  | $\begin{bmatrix}1&0\\\ 1&0\end{bmatrix}$ | $\infty$ |  Prop. 24
73 |  | $\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$ | $\infty$ |  Cor. 22 | 89 |  | $\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$ | 3 |  Rem. 32
74 |  | $\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$ | $\infty$ |  Prop 46 | 90 |  | $\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$ | 3 |  Rem. 32
75 |  | $\begin{bmatrix}0&1\\\ 0&1\end{bmatrix}$ | 3 |  Rem. 32 | 91 |  | $\begin{bmatrix}0&1\\\ 0&1\end{bmatrix}$ | $\infty$ |  Cor. 22
76 |  | $\begin{bmatrix}0&0\\\ 1&1\end{bmatrix}$ | 3 |  Rem. 32 | 92 |  | $\begin{bmatrix}0&0\\\ 1&1\end{bmatrix}$ | 4 |  Rem. 34
77 |  | $\begin{bmatrix}1&1\\\ 1&0\end{bmatrix}$ | 3 |  Rem. 32 | 93 |  | $\begin{bmatrix}1&1\\\ 1&0\end{bmatrix}$ | 4 |  Rem. 34
78 |  | $\begin{bmatrix}1&1\\\ 0&1\end{bmatrix}$ | 3 |  Rem. 32 | 94 |  | $\begin{bmatrix}1&1\\\ 0&1\end{bmatrix}$ | $\infty$ |  Rem 43
79 |  | $\begin{bmatrix}1&0\\\ 1&1\end{bmatrix}$ | 3 |  Rem. 32 | 95 |  | $\begin{bmatrix}1&0\\\ 1&1\end{bmatrix}$ | 4 |  Rem. 34
80 |  | $\begin{bmatrix}0&1\\\ 1&1\end{bmatrix}$ | 3 |  Rem. 32 | 96 |  | $\begin{bmatrix}0&1\\\ 1&1\end{bmatrix}$ | $\infty$ | case 94
81 |  | $\begin{bmatrix}1&1\\\ 1&1\end{bmatrix}$ | 2 |  Rem. 30 | 97 |  | $\begin{bmatrix}1&1\\\ 1&1\end{bmatrix}$ | $\infty$ |  Prop. 24
98 | $\begin{bmatrix}1&1\\\ 0&1\end{bmatrix}$ | $\begin{bmatrix}0&0\\\ 0&0\end{bmatrix}$ | 4 |  Rem. 34 | 114 | $\begin{bmatrix}1&1\\\ 1&1\end{bmatrix}$ | $\begin{bmatrix}0&0\\\ 0&0\end{bmatrix}$ | $\infty$ |  Prop. 24
99 |  | $\begin{bmatrix}1&0\\\ 0&0\end{bmatrix}$ | 3 |  Rem. 32 | 115 |  | $\begin{bmatrix}1&0\\\ 0&0\end{bmatrix}$ | 5 |  Rem. 51
100 |  | $\begin{bmatrix}0&1\\\ 0&0\end{bmatrix}$ | $\infty$ |  Rem 43 | 116 |  | $\begin{bmatrix}0&1\\\ 0&0\end{bmatrix}$ | 5 |  Rem. 51
101 |  | $\begin{bmatrix}0&0\\\ 1&0\end{bmatrix}$ | 2 |  Rem. 30 | 117 |  | $\begin{bmatrix}0&0\\\ 1&0\end{bmatrix}$ | 5 |  Prop. 50
102 |  | $\begin{bmatrix}0&0\\\ 0&1\end{bmatrix}$ | 3 |  Rem. 32 | 118 |  | $\begin{bmatrix}0&0\\\ 0&1\end{bmatrix}$ | 5 |  Rem. 51
103 |  | $\begin{bmatrix}1&1\\\ 0&0\end{bmatrix}$ | $\infty$ |  Rem 43 | 119 |  | $\begin{bmatrix}1&1\\\ 0&0\end{bmatrix}$ | $\infty$ |  Prop. 24
104 |  | $\begin{bmatrix}1&0\\\ 1&0\end{bmatrix}$ | 3 |  Rem. 32 | 120 |  | $\begin{bmatrix}1&0\\\ 1&0\end{bmatrix}$ | $\infty$ |  Prop. 24
105 |  | $\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$ | 4 |  Rem. 34 | 121 |  | $\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$ | 3 |  Prop. 48
106 |  | $\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$ | 3 |  Rem. 32 | 122 |  | $\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$ | 3 |  Rem. 49
107 |  | $\begin{bmatrix}0&1\\\ 0&1\end{bmatrix}$ | $\infty$ |  Rem 43 | 123 |  | $\begin{bmatrix}0&1\\\ 0&1\end{bmatrix}$ | $\infty$ |  Prop. 24
108 |  | $\begin{bmatrix}0&0\\\ 1&1\end{bmatrix}$ | 3 |  Rem. 32 | 124 |  | $\begin{bmatrix}0&0\\\ 1&1\end{bmatrix}$ | $\infty$ |  Prop. 24
109 |  | $\begin{bmatrix}1&1\\\ 1&0\end{bmatrix}$ | 3 |  Rem. 32 | 125 |  | $\begin{bmatrix}1&1\\\ 1&0\end{bmatrix}$ | $\infty$ |  Thm. 42
110 |  | $\begin{bmatrix}1&1\\\ 0&1\end{bmatrix}$ | $\infty$ |  Cor. 22 | 126 |  | $\begin{bmatrix}1&1\\\ 0&1\end{bmatrix}$ | $\infty$ |  Thm. 42
111 |  | $\begin{bmatrix}1&0\\\ 1&1\end{bmatrix}$ | 3 |  Rem. 32 | 127 |  | $\begin{bmatrix}1&0\\\ 1&1\end{bmatrix}$ | $\infty$ |  Thm. 42
112 |  | $\begin{bmatrix}0&1\\\ 1&1\end{bmatrix}$ | 3 |  Rem. 32 | 128 |  | $\begin{bmatrix}0&1\\\ 1&1\end{bmatrix}$ | $\infty$ |  Thm. 42
113 |  | $\begin{bmatrix}1&1\\\ 1&1\end{bmatrix}$ | $\infty$ |  Rem 43 | 129 |  | $\begin{bmatrix}1&1\\\ 1&1\end{bmatrix}$ | $\infty$ |  Prop. 24
Table 2:  The remaining cases of the index of word-representability of
infinite split graphs $G(A,B)$ for $2\times 2$ matrices $A$ and $B$.

##  2 Preliminaries

######  Definition 6.

Let $M$ be a binary $m\times n$ matrix. Define $S(M)$ to be the matrix

$\left[{\begin{array}[]{cc}L_{n}&M^{T}\\\ M&O_{m}\\\ \end{array}}\right]$

where $O_{m}$ is the $m\times m$ zero matrix and $L_{n}$ is the $n\times n$
matrix such that all diagonal entries are $0$’s and all other entries are
$1$’s.

It is easy to see that for any binary $m\times n$ matrix $M$, $S(M)$ is the
adjacency matrix of a split graph with the maximal clique of order $n$ or
$n+1$. We denote the split graph by $G(M)$. Clearly, $M$ gives edges between
the clique and independent set in $G(M)$, and the order of the maximal clique
depends on the existence of a $11\cdots 1$ row in $M$.

######  Example 7.

If $M=\left[{\begin{array}[]{cccc}1&0&1&0\\\ 0&1&1&0\\\ 1&0&0&0\\\
0&0&0&1\end{array}}\right]$ then

$S(M)=\left[{\begin{array}[]{cccccccc}0&1&1&1&1&0&1&0\\\ 1&0&1&1&0&1&0&0\\\
1&1&0&1&1&1&0&0\\\ 1&1&1&0&0&0&0&1\\\ 1&0&1&0&0&0&0&0\\\ 0&1&1&0&0&0&0&0\\\
1&0&0&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\end{array}}\right]$

is the adjacency matrix of the graph shown in Figure 2.

Figure 2:  The split graph $G(M)$ given by $S(M)$ in Example 7.

######  Remark 8.

If $M$ is a zero matrix, then $G(M)$ is a disjoint union of a clique and
isolated vertices and is word-representable, because the clique is semi-
transitively (in fact, transitively) orientable and there are no other edges
in $G(M)$.

The following lemma is Lemma 8 in [7].

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

Let $S_{n}=(E_{n-m},K_{m})$ be a split graph with the maximum clique $K_{m}$,
and a spit graph $S_{n+1}$ is obtained from $S_{n}$ by either adding a vertex
of degree $0$ (to $E_{n-m}$), or adding a vertex of degree $1$ (to $E_{n-m}$),
or by “coping” a vertex (either in $E_{n-m}$ or in $K_{m}$), that is, by
adding a vertex whose neighbourhood is identical to the neighbourhood of a
vertex in $S_{n}$. Then $S_{n}$ is word-representable if and only if $S_{n+1}$
is word-representable.

To analyze word-representability of a given split graph, by Lemma 9 we can
delete vertices of degree 0 and vertices of degree 1, as well as delete all
but one vertex having the same neighborhood.

######  Proposition 10.

Let $M$ be an $m\times n$ matrix. If every row, or every column of $M$ is of
the form $00\cdots 0$ or $11\cdots 1$, then $G(M)$ is word-representable.

###### Proof.

If every row of $M$ consists of all $0$’s or all $1$’s then in $G(M)$, each
vertex in the independent set is an isolated vertex, or is connected to every
vertex in the clique. By Lemma 9, word-representability of $G(M)$ is
equivalent to word-representability of either the clique $K_{n+1}$, or the
disjoint union of a clique ($K_{n}$ or $K_{n+1}$) and an isolated vertex,
which are clearly semi-transitively orientable, and thus, by Theorem 1, word-
representable.

On the other hand, if every column of $M$ consists of all $0$’s or all $1$’s
then the neighborhood of each vertex in the independent set is the same and,
by Lemma 9, word-representability of $G(M)$ is equivalent to word-
representability of the clique $K_{n}$ with a vertex $x$ connected to some,
maybe none or all of clique’s vertices. If w.l.o.g. $x$ is connected to
vertices $1,2,\ldots,p$, $0\leq p\leq n$, in $K_{n}$ formed by the vertices
$1,2,\ldots,n$, then the word $x12\cdots px(p+1)(p+2)\cdots n$ represents the
graph. ∎

It is obvious that if $M^{*}$ is a matrix obtained by a row or column
permutation of a matrix $M$, then $G(M^{*})$ is a split graph obtained by
relabelling the vertices of the graph $G(M)$. Hence we get the following
lemma.

######  Lemma 11.

Let $M$ be an $m\times n$ binary matrix and $M^{*}$ is a matrix obtained from
a sequence of row and/or column permutations of $M$. Then, $G(M)$ is word-
representable if and only if $G(M^{*})$ is word-representable.

######  Lemma 12.

Let $M:=[m_{ij}]_{m\times n}$ be an $m\times n$ binary matrix such that
$m_{k1}=m_{k2}=\cdots=m_{kn}=1$ for some $k\in\\{1,2,\ldots,m\\}$. If

$N=\begin{bmatrix}m_{11}&m_{12}&\cdots&m_{1n}&0\\\
m_{21}&m_{22}&\cdots&m_{2n}&0\\\ \vdots&\vdots&&\vdots&\vdots\\\
m_{(k-1)1}&m_{(k-1)2}&\cdots&m_{(k-1)n}&0\\\
m_{(k+1)1}&m_{(k+1)2}&\cdots&m_{(k+1)n}&0\\\ \vdots&\vdots&&\vdots&\vdots\\\
m_{m1}&m_{m2}&\cdots&m_{mn}&0\par\end{bmatrix},$

is an $(m-1)\times(n+1)$ binary matrix, then $G(M)$ is isomorphic to $G(N)$.

###### Proof.

Let $M^{*}$ be the matrix obtained from $M$ by making the $k^{th}$ row be the
first row. That is,

$M^{*}=\begin{bmatrix}1&1&\cdots&1\\\ m_{11}&m_{12}&\cdots&m_{1n}\\\
m_{21}&m_{22}&\cdots&m_{2n}\\\ \vdots&\vdots&&\vdots\\\
m_{(k-1)1}&m_{(k-1)2}&\cdots&m_{(k-1)n}\\\
m_{(k+1)1}&m_{(k+1)2}&\cdots&m_{(k+1)n}\\\ \vdots&\vdots&&\vdots\\\
m_{m1}&m_{m2}&\cdots&m_{mn}\end{bmatrix}.$

Since $M^{*}$ is obtained by reordering rows of $M$, $G(M^{*})$ is obtained by
relabeling the vertices of $G(M)$, and thus $G(M^{*})$ is isomorphic to
$G(M)$. Note that $S(M^{*})=S(N)$, and so $G(M^{*})$ and $G(N)$ are the same
graph. Hence $G(M)$ is isomorphic to $G(N)$. ∎

It is known [5] that there are no non-word-representable graphs of order less
than 6 and the only non-word-representable graph on 6 vertices is the wheel
graph $W_{5}$, which is not a split graph. Thus, $G(M)$ is word-representable
if $M$ is an $m\times n$ matrix and $m+n\leq 6$. In [7], it is shown that any
split graph $S$ with maximum clique $K_{4}$ is word-representable if and only
if $S$ does not contain the graphs $T_{1}$, $T_{2}$, $T_{3}$ and $T_{4}$ shown
in Figure 3 as induced subgraphs. As a corollary to this result, we have the
following theorem.

$T_{1}=$ | $T_{2}=$
---|---
$T_{3}=$ | $T_{4}=$
Figure 3:  Non-word-representable split graphs $T_{1},T_{2},T_{3},T_{4}$.

######  Theorem 13.

Let $A$ be an $m\times 4$ binary matrix without all $1$’s rows. Then, $G(A)$
is word-representable if and only if the rows and columns of $A$ cannot be
permuted to be a matrix containing ${\tiny\begin{bmatrix}1&1&0&0\\\ 1&0&1&0\\\
0&1&1&0\end{bmatrix}}$, ${\tiny\begin{bmatrix}1&1&0&0\\\ 1&0&1&0\\\
1&0&0&1\end{bmatrix}}$, ${\tiny\begin{bmatrix}1&0&1&1\\\ 1&1&0&1\\\
1&1&1&0\end{bmatrix}}$ or ${\tiny\begin{bmatrix}1&1&1&0\\\ 1&1&0&0\\\
1&0&0&1\\\ 1&0&1&1\end{bmatrix}}$ as a submatrix.

Let $x^{n}$ denotes $xx\cdots x$ where $x$ is repeated $n$ times. The next
theorem gives a sufficient condition for word-representability of a given
graph $G(M)$.

######  Theorem 14.

Let $M$ be an $m\times n$ binary matrix. If there is a sequence of column
permutations of $M$ giving the matrix such that each row of $M$ is of the form
$0^{r}1^{s}0^{t}$ for some non-negative integers $r,s,t$, then $G(M)$ is word-
representable.

###### Proof.

Assume that $M^{*}$ is the matrix obtained from a sequence of column
permutations of $M$ and each row of $M^{*}$ is of the form $0^{r}1^{s}0^{t}$
where $r,s,t$ are non-negative integers. Let the $i^{th}$ row/column of the
adjacency matrix $S(M^{*})$ correspond to vertex $i$ in $G(M^{*})$. So the
clique $C$ in $G(M^{*})$ contains vertices $1,2,\dots,n$ and the independent
set $I$ in $G(M^{*})$ contains vertices $n+1,n+2,\dots,n+m$. Assign the
orientation of edges in $G(M^{*})$ as $i\rightarrow j$ if and only if $i<j$.
We have that $1\rightarrow 2\rightarrow\cdots\rightarrow n$ is the longest
path in the transitively oriented $C$, and the edges between $C$ and $I$ are
oriented from $C$ to $I$. Thus, each edge in the independent set is of type B,
and we are done by Theorems 1 and 5. ∎

We have the following important generalization of Theorem 14.

######  Theorem 15.

Let $M$ be an $m\times n$ binary matrix without all $1$’s rows. The split
graph $G(M)$ is word-representable if and only if $M$ satisfies the following
conditions:

  * (i)

there is a sequence of column permutations of $M$ giving a matrix $M^{*}$
where every row is of the form $0^{r}1^{s}0^{t}$ or $1^{r}0^{s}1^{t}$ for some
nonnegative integers $r$, $s$, $t$, and

  * (ii)

for any row of $M^{*}$ of the form $1^{a}0^{b}1^{c}$ for some positive integer
$a,b,c$, there is no other row not of the form $1^{a}0^{b}1^{c}$ in which the
entries in positions $a$ and $a+b+1$ are $1$’s.

###### Proof.

“$\Leftarrow$.” Assign the orientation of edges in $G(M^{*})$ as $i\rightarrow
j$ if $i<j$ except if $j>n$ (i.e. $j$ is a vertex in the independent set) and
the row in $M^{*}$ corresponding to $j$ is of the form $1^{r}0^{s}1^{t}$, in
which case we still orient $i\rightarrow j$ for $1\leq i\leq r$ but
$j\rightarrow i$ for $r+s+1\leq i\leq n$. The vertices in the independent set
will then be of types B and C, and taking into account condition (ii),
Theorems 1 and 5 can be applied to see that $G(M^{*})$ is word-representable,
and thus $G(M)$ is word-representable by Lemma 11.

“$\Rightarrow$.” By Theorem 1, $G(M)$ admits a semi-transitive orientation. By
Theorem 5, under this orientation the clique is oriented transitively, and we
can rename the vertices of the clique, if necessary so that the longest path
would be formed by $1\rightarrow 2\rightarrow\cdots\rightarrow n$. Note that
renaming vertices in the clique corresponds to permuting columns in $M$ giving
$M^{*}$. But then, conditions (ii) and (iii) in Theorem 5 give conditions (i)
and (ii) in this theorem. ∎

######  Remark 16.

If $M$ has an all $1$’s row, we can see that Theorems 13 and 15 cannot be
applied. However, we can use Theorem 12 to change $M$ into an
$(m-1)\times(n+1)$ matrix $N$ which does not contain all $1$’s row. So we can
apply the theorems to matrix $N$ instead of $M$ because $G(N)$ is isomorphic
to $G(M)$. This observation also applies to Corollary 23 below.

We can see that Theorem 15 allows us to answer the question on word-
representability of $G(M)$ by looking at permutations of columns in $M$. Let
$M=\left[m_{ij}\right]_{m\times n}$ be an $m\times n$ matrix and
$\rho=\rho_{1}\rho_{2}\cdots\rho_{n}$ is a permutation of $\\{1,2,\ldots,n\\}$
written in one-line notation. We say that

$M^{*}=\begin{bmatrix}m_{1\rho_{1}}&m_{1\rho_{2}}&\cdots&m_{1\rho_{n}}\\\
m_{2\rho_{1}}&m_{2\rho_{2}}&\cdots&m_{2\rho_{n}}\\\
\vdots&\vdots&\ddots&\vdots\\\
m_{m\rho_{1}}&m_{m\rho_{2}}&\cdots&m_{m\rho_{n}}\\\ \end{bmatrix}$

is the matrix obtained from reordering columns of $M$ in the order given by
$\rho$. The key approach given by Theorem 15 is finding a permutation $\rho$
that turns each row of $M^{*}$ into the form $0^{r}1^{s}0^{t}$ or
$1^{r}0^{s}1^{t}$ (so, all 1’s in $M^{*}$ are cyclically consecutive).
Interestingly, to prove word-representability results in this paper, only rows
of the form $0^{r}1^{s}0^{t}$ are used, so that condition (ii) in Theorem 15
is not applicable.

######  Example 17.

In the matrix $M=\begin{bmatrix}1&0&0&1&0&1&1&0\\\ 0&0&0&0&0&0&0&0\\\
1&0&1&0&1&0&1&0\\\ 0&0&0&0&0&0&0&0\\\ 0&1&1&0&0&1&1&0\\\ 0&0&0&0&0&0&0&0\\\
1&0&0&1&0&1&0&1\\\ 0&0&0&0&0&0&0&0\end{bmatrix}$
we can ignore rows $2,4,6$ and $8$ because all entries in these rows are zero.
Then we need to find a permutation $\rho=\rho_{1}\rho_{2}\cdots\rho_{8}$
making

  * •

columns $1,4,6$ and $7$ be (cyclically) consecutive in rows $1$;

  * •

columns $1,3,5$ and $7$ be (cyclically) consecutive in row $3$ and $7$;

  * •

columns $2,3,6$ and $7$ be (cyclically) consecutive in row $5$.

It can be implied from the first and the second bullet points that 1 and 7
must be consecutive in $\rho$ and then, w.l.o.g., 4 and 6 are next to the left
of these numbers and 3 and 5 are next to the right of them (cyclically). Hence
$\rho$ contains

$\\{4,6\\},\\{1,7\\},\\{3,5\\}$

where numbers in $\\{\\}$ are consecutive in $\rho$ but are in some unknown to
us order. But then, we get a contradiction with the second bullet point.
Hence, there is no such $\rho$ and $G(M)$ is non-word-representable by Theorem
15.

##  3 General results on split graphs generated by morphisms

In this section, we discuss rather general results on split graphs generated
by morphisms, thus preparing ourselves for a classification of the case of
$2\times 2$ matrices coming in the next section.

######  Definition 18.

Let $A,B$ be $m\times n$ binary matrices. The matrix $M^{k}(A,B)$ is said to
be the $k^{th}$-iteration of the $2$-dimensional morphism applied to the
$1\times 1$ matrix $\left[0\right]$ which maps $\left[0\right]\rightarrow A$
and $\left[1\right]\rightarrow B$. Moreover, we write $S^{k}(A,B)$ for the
matrix $S(M^{k}(A,B))$ and $G^{k}(A,B)$ for the graph with the adjacency
matrix $S^{k}(A,B)$.

######  Example 19.

Let $A=\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$ and $B=\begin{bmatrix}0&1\\\
1&0\end{bmatrix}$. Then we have

$M^{0}(A,B)=\begin{bmatrix}0\end{bmatrix}$, |  $M^{1}(A,B)=\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$, |  $M^{2}(A,B)=\begin{bmatrix}0&1&1&0\\\ 1&0&0&1\\\ 1&0&0&1\\\ 0&1&1&0\end{bmatrix}$.
---|---|---

Then, $S^{2}(A,B)=\begin{bmatrix}0&1&1&1&0&1&1&0\\\ 1&0&1&1&1&0&0&1\\\
1&1&0&1&1&0&0&1\\\ 1&1&1&0&0&1&1&0\\\ 0&1&1&0&0&0&0&0\\\ 1&0&0&1&0&0&0&0\\\
1&0&0&1&0&0&0&0\\\ 0&1&1&0&0&0&0&0\end{bmatrix}$ and $G^{2}(A,B)$ is shown in
Figure 4.

Figure 4:  The split graph $G^{2}(A,B)$ corresponding to the adjacency matrix
$S^{2}(A,B)$ in Example 19.

######  Remark 20.

If $A$ is a zero matrix, then $M^{k}(A,B)$ is always a zero matrix for any
$m\times n$ matrix $B$ and positive integer $k$. So, by Remark 8, $G^{k}(A,B)$
is word-representable.

###  3.1 The case of $A=B$

In this case, both $\left[0\right]$ and $\left[1\right]$ are mapped to the
same matrix $A$, so if $A$ is an $m\times n$ binary matrix, then

$S^{k}(A,A)=\left[{\begin{array}[]{cc}L_{n^{k}}&A_{k}^{T}\\\
A_{k}&O_{m^{k}}\end{array}}\right]\text{~{}~{}~{}~{}where~{}~{}}A_{k}=\underbrace{\left[\begin{array}[]{cccc}A&A&\cdots&A\\\
A&A&\cdots&A\\\ \vdots&\vdots&\ddots&\vdots\\\
A&A&\cdots&A\end{array}\right]}_{n^{k}\text{~{}columns}}.$

Clearly, $A_{k}$ is an $n^{k}\times m^{k}$ matrix and $S^{k}(A,A)=S(A_{k})$,
so $G^{k}(A,A)$ is isomorphic to $G(A_{k})$.

######  Theorem 21.

Let $A$ be an $m\times n$ binary matrix. For $k\geq 1$, $G^{k}(A,A)$ is word-
representable if and only if $G(A)$ is word-representable.

###### Proof.

Firstly, we label a vertex of $G^{k}(A,A)$ by $i$ if it is represented by the
$i^{th}$ column/row in $S^{k}(A,A)$. Note that rows
$i,m+i,2m+i,\dots,(m^{k-1}-1)m+i$ in $A_{k}$ are identical for any
$i\in\\{1,2,\dots,m\\}$, and columns $j,n+j,2n+j,\dots,(n^{k-1}-1)n+j$ in
$A_{k}$ are also identical for any $j\in\\{1,2,\dots,n\\}$. So, for any
$i\in\\{1,2,\dots,m\\}$, the vertices of $G^{k}(A,A)$ in
$R_{i}:=\\{i+n^{k},m+i+n^{k},2m+i+n^{k},\dots,(m^{k-1}-1)m+i+n^{k}\\}$ have
the same neighborhoods. Similarly, any two vertices of $G^{k}(A,A)$ in
$C_{j}:=\\{j,n+j,2n+j,\dots,(n^{k-1}-1)n+j\\}$ are connected to the same
vertices in the independent set for any $j\in\\{1,2,\dots,n\\}$. Thus, by
Lemma 9, $G^{k}(A,A)$ is word-representable if and only if the graph $G$
obtained by deleting all vertices but the smallest one in $R_{i}$ and $C_{j}$
for all $i,j\in\\{1,2,\ldots,n\\}$ is word-representable. But $G$ is exactly
$G(A)$, which complete the proof. ∎

######  Corollary 22.

If $A$ is an $m\times n$ binary matrix such that $m+n\leq 6$, then
$G^{k}(A,A)$ is word-representable for any $k\geq 0$.

###### Proof.

Since the smallest non-word-representable split graph is of order $7$, all
split graphs of orders less than $7$ are word-representable. Hence
$G^{k}(A,A)$ is word-representable for any $m\times n$ matrix $A$ where
$m+n\leq 6$. ∎

Moreover, together with Theorem 13, we have the following result.

######  Corollary 23.

Let $A$ be an $m\times 4$ binary matrix with no all $1$’s row. For any integer
$k$, the graph $G^{k}(A,A)$ is word-representable if and only if the rows and
columns of $A$ cannot be permuted to be the matrix containing
${\tiny\begin{bmatrix}1&1&0&0\\\ 1&0&1&0\\\ 0&1&1&0\end{bmatrix}}$,
${\tiny\begin{bmatrix}1&1&0&0\\\ 1&0&1&0\\\ 1&0&0&1\end{bmatrix}}$,
${\tiny\begin{bmatrix}1&0&1&1\\\ 1&1&0&1\\\ 1&1&1&0\end{bmatrix}}$ or
${\tiny\begin{bmatrix}1&1&1&0\\\ 1&1&0&0\\\ 1&0&0&1\\\ 1&0&1&1\end{bmatrix}}$
as a submatrix.

###  3.2 The case of $A\neq B$

In what follows, $A$ and $B$ can be distinct.

######  Proposition 24.

If every row, or every column, in $m\times n$ matrices $A$ and $B$ is either
$0^{n}$ or $1^{n}$, then $G^{k}(A,B)$ is word-representable for any $k\geq 0$.

###### Proof.

If every row (resp., column) in $A$ and $B$ is either $0^{n}$ or $1^{n}$, then
every row (resp., column) in $M^{k}(A,B)$ is either $0^{n^{k}}$ or
$1^{n^{k}}$, so by Proposition 10, $G^{k}(A,B)$ is word-representable. ∎

######  Theorem 25.

Let $A$ and $B$ be $m\times n$ binary matrices. Suppose that $A^{*}$ and
$B^{*}$ are the matrices obtained from reordering columns of $A$ and $B$,
respectively, in order given by a permutation
$\sigma=\sigma_{1}\sigma_{2}\cdots\sigma_{n}$. Then $G^{k}(A,B)$ is word-
representable if and only if $G^{k}(A^{*},B^{*})$ is word-representable for
any $k\geq 0$.

###### Proof.

The case $k=0$ is trivial, so assume that $k\geq 1$. We claim that
$M^{k}(A^{*},B^{*})$ is obtained from a permutation of columns in
$M^{k}(A,B)$. We will prove the claim by induction on $k$. Note that
$M^{1}(A,B)=A$ and $M^{1}(A^{*},B^{*})=A^{*}$. So $M^{1}(A^{*},B^{*})$ is the
matrix obtained from reordering columns of $M^{1}(A,B)$. Suppose that $l$ is a
positive integer and $M^{l}(A^{*},B^{*})$ is the matrix obtained from
reordering columns of $M^{l}(A,B)$ in order given by a permutation
$\tau=\tau_{1}\tau_{2}\cdots\tau_{n^{l}}$. Let
$M^{l}(A,B)=\begin{bmatrix}C_{1}&C_{2}&\cdots&C_{n^{l}}\end{bmatrix}$ where
$C_{i}$ is the $i^{th}$ column of $M^{l}(A,B)$. Then
$M^{l}(A^{*},B^{*})=\begin{bmatrix}C_{\tau_{1}}&C_{\tau_{2}}&\cdots&C_{\tau_{n^{l}}}\end{bmatrix}$.
For the next iteration of morphism, each column $C_{i}$ of $M^{l}(A,B)$ is
mapped to $n$ columns $C_{i,1},C_{i,2},\ldots,C_{i,n}$, and each column
$C_{\tau_{i}}$ of $M^{l}(A^{*},B^{*})$ is mapped to $n$ columns
$C_{\tau_{i},\sigma_{1}},C_{\tau_{i},\sigma_{2}},\ldots,C_{\tau_{i},\sigma_{n}}$.
So we have

$M^{l+1}(A,B)=\left[C_{1,1}~{}C_{1,2}~{}\cdots
C_{1,n}~{}\cdots~{}C_{n^{l},1}~{}C_{n^{l},2}~{}\cdots~{}C_{n^{l},n}\right]$

and

$\displaystyle M^{l+1}(A^{*},B^{*})=[$
$\displaystyle~{}C_{\tau_{1},\sigma_{1}}~{}C_{\tau_{1},\sigma_{2}}~{}\cdots~{}C_{\tau_{1},\sigma_{n}}~{}\cdots~{}C_{\tau_{n^{l}},\sigma_{1}}$
$\displaystyle
C_{\tau_{n^{l}},\sigma_{2}}~{}\cdots~{}C_{\tau_{n^{l}},\sigma_{n}}~{}].$

A group of columns $C_{i,1},C_{i,2},\ldots,C_{i,n}$ is called block $B_{i}$.
Firstly, we can see that reordering the blocks $B_{1},B_{2},\ldots,B_{n^{l}}$
of $M^{l+1}(A,B)$ in order given by $\tau$, and then reordering columns in
every block $B_{i}$ in order given by $\sigma$, yields the matrix
$M^{l+1}(A^{*},B^{*})$. Thus, $M^{l+1}(A^{*},B^{*})$ is obtained by a column
permutation of $M^{l+1}(A,B)$ and our claim is true. Hence, by Lemma 11,
$G^{k}(A,B)$ is word-representable if and only if $G^{k}(A^{*},B^{*})$ is
word-representable for any positive integer $k$. ∎

Next theorem is a natural extension of Theorem 25 to the case of row
permutations, and it can be proved in a similar way to the proof of Theorem
25, so we omit the proof.

######  Theorem 26.

Let $A$ and $B$ be $m\times n$ binary matrices. Suppose that $A^{*}$ and
$B^{*}$ are the matrices obtained from reordering rows of $A$ and $B$,
respectively, in order given by the same permutation. Then $G^{k}(A,B)$ is
word-representable if and only if $G^{k}(A^{*},B^{*})$ is word-representable
for any $k\geq 0$.

So, we can reorder rows and columns of given matrices $A$ and $B$ while
preserving the word-representability of $G^{k}(A,B)$. If $A$ contains at least
one $0$, we can reorder rows and columns of $A$ to make the leftmost bottom
entry be a $0$ (the matrix $B$ will be changed by the same permutation of rows
and columns as those applied to $A$). Thus, in what follows, if $A$ is not
all-one matrix, w.l.o.g. we can assume that the leftmost bottom entry of $A$
is always 0. Then, the $m\times n$ leftmost bottom submatrix of $M^{2}(A,B)$
is $A$ since $M^{1}(A,B)=A$. Moreover, the $m^{k-1}\times n^{k-1}$ leftmost
bottom submatrix of $M^{k}(A,B)$ is $M^{k-1}(A,B)$. Thus, the limit
$\lim_{k\to\infty}M^{k}(A,B)$, called a fixed point of the morphism, is well-
defined. So, we have that $G^{i}(A,B)$ is an induced subgraph of $G^{k}(A,B)$
if $i\leq k$ and the notion of the infinite split graph $G(A,B)$ is well-
defined in the case when $A$ has a 0 as the leftmost bottom entry. So we are
interested in the smallest integer $l$ (possibly non-existing) that
$G^{l}(A,B)$ is non-word-representable for given $A$ and $B$ (then
$G^{i}(A,B)$ is non-word-representable for $i\geq l$).

######  Definition 27.

Suppose that a matrix $A$ has a $0$ as the leftmost bottom entry. The index of
word-representability $\rm IWR$$(A,B)$ of an infinite split graph $G(A,B)$ is
the smallest integer $l$ such that $G^{l}(A,B)$ is non-word-representable. If
such $l$ does not exist, that is, if $G^{l}(A,B)$ is word-representable for
all $l$, then $l:=\infty$. If the leftmost bottom entry of $A$ is $1$ (so that
the $\lim_{k\to\infty}M^{k}(A,B)$ may not be well-defined as the sequence of
graphs $G^{k}(A,B)$, for $k\geq 0$, may not be a chain of induced subgraphs)
then $\rm IWR$$(A,B)$ is still defined in the same way even though $G(A,B)$
may not be defined.

Note that since $G^{0}(A,B)$ is a graph with one vertex, we have $\rm
IWR$$(A,B)\geq 1$. Even though Definition 27 is very similar to the respective
definition of the index of word-representability of an infinite Toeplitz graph
in [2] (where the index in our context would be the maximum $l$ such that
$G^{l}(A,B)$ is word-representable), it is more flexible as it makes sense in
the situation when the leftmost bottom entry of $A$ is 1.

######  Theorem 28.

Let $A=\left[a_{ij}\right]$ and $B=\left[b_{ij}\right]$ be $m\times n$ binary
matrices, and

$C=\begin{bmatrix}a_{p_{1}q_{1}}&a_{p_{1}q_{2}}&\cdots&a_{p_{1}q_{t}}\\\
a_{p_{2}q_{1}}&a_{p_{2}q_{2}}&\cdots&a_{p_{2}q_{t}}\\\
\vdots&\vdots&\ddots&\vdots\\\
a_{p_{s}q_{1}}&a_{p_{s}q_{2}}&\cdots&a_{p_{s}q_{t}}\end{bmatrix}$ and
$D=\begin{bmatrix}b_{p_{1}q_{1}}&b_{p_{1}q_{2}}&\cdots&b_{p_{1}q_{t}}\\\
b_{p_{2}q_{1}}&b_{p_{2}q_{2}}&\cdots&b_{p_{2}q_{t}}\\\
\vdots&\vdots&\ddots&\vdots\\\
b_{p_{s}q_{1}}&b_{p_{s}q_{2}}&\cdots&b_{p_{s}q_{t}}\end{bmatrix}$

be $s\times t$ submatrices of $A$ and $B$, respectively, where $1\leq
p_{1}<p_{2}<\cdots<p_{s}\leq m$ and $1\leq q_{1}<q_{2}<\cdots<q_{t}\leq n$.
For any positive integer $k$, if $G^{k}(C,D)$ is non-word-representable, then
$G^{k}(A,B)$ is non-word-representable.

###### Proof.

First, we will prove by induction that $M^{k}(C,D)$ is a submatrix of
$M^{k}(A,B)$ for any positive integer $k$. It is obvious that $M^{1}(C,D)=C$
is a submatrix of $M^{1}(A,B)=A$. Let $l$ be a positive integer such that
$M^{l}(C,D)$ is a submatrix of $M^{l}(A,B)$ on the columns
$c_{1},c_{2},\ldots,c_{t^{l}}$ and rows $r_{1},r_{2},\ldots,r_{s^{l}}$. For
the next iteration of morphism, $M^{l+1}(A,B)$ is formed by replacing each
entry of $M^{l}(A,B)$ with either $A$ or $B$. So the columns
$(c_{i}-1)n+p_{j}$ for $1\leq i\leq t^{l},1\leq j\leq s$, and rows
$(r_{i}-1)m+q_{j}$ for $1\leq i\leq s^{l}$, $1\leq j\leq t$, form the matrix
$M^{l+1}(C,D)$. Hence $M^{k}(C,D)$ is a submatrix of $M^{k}(A,B)$ for any
$k\geq 1$. Therefore, $G^{k}(A,B)$ contains $G^{k}(C,D)$ as an induced
subgraph for $k\geq 1$. As the property of word-representability is
hereditary, we have that non-word-representability of $G^{k}(C,D)$ implies
non-word-representability of $G^{k}(A,B)$. ∎

Theorem 28 gives a useful tool to study non-word-representability of
$G^{k}(A,B)$ for larger $A$ and $B$. Indeed, a starting point to justify
suspected non-word-representability of $G^{k}(A,B)$ can be analysis of smaller
submatrices of $A$ and $B$. This is one of our motivation points to conduct a
systematic study of $\rm IWR$$(A,B)$ for $2\times 2$ matrices, to be done in
the next section, as they are smallest submatrices that can be used to show
non-word-representability of $G^{k}(A,B)$ for some $A$, $B$ and $k$.

##  4 Classification of word-representable split graphs defined by iteration
of morphisms using two $2\times 2$ matrices

A summary of our classification of word-representability of $G^{k}(A,B)$ for
$2\times 2$ matrices $A$ and $B$ can be found in Tables 1 and 2, where the
index of word-representability $\rm IWR$$(A,B)$ is given along with a
reference, or a comment to the respective result.

###  4.1 The case of $A$ is not all-one matrix

For any $2\times 2$ matrices $A$ and $B$, the graph $G^{1}(A,B)$ is a split
graph of order 4 which is always word-representable. Then, $\rm IWR$$(A,B)\geq
2$. However, $2\times 2$ matrices $A$ and $B$ such that $G^{2}(A,B)$ is non-
word-representable can be found.

######  Proposition 29.

For $A=\begin{bmatrix}1&0\\\ 0&0\end{bmatrix}$ and $B=\begin{bmatrix}0&1\\\
1&1\end{bmatrix}$, $\rm IWR$$(A,B)=2$.

###### Proof.

We have $M^{2}(A,B)=\begin{bmatrix}0&1&1&0\\\ 1&1&0&0\\\ 1&0&1&0\\\
0&0&0&0\end{bmatrix}$. Reordering columns of $M^{2}(A,B)$ in order given by
the permutation $2314$ yields the matrix $\begin{bmatrix}1&1&0&0\\\ 1&0&1&0\\\
0&1&1&0\\\ 0&0&0&0\end{bmatrix}$. So, by Theorem 13, $G^{2}(A,B)$ is non-word-
representable ($G^{2}(A,B)$ contains $T_{1}$ as an induced subgraph). ∎

######  Remark 30.

Permuting rows or/and columns in $A$ and $B$ similarly to Proposition 29, we
see that $\rm IWR$$(A,B)=2$ for $A$ and $B$ in Cases 31, 45, 81 and 101 in
Tables 1 and 2 (in Case 81 $G^{2}(A,B)$ contains $T_{3}$, and in the other
cases $G^{2}(A,B)$ contains $T_{1}$).

######  Proposition 31.

For $A=\begin{bmatrix}1&0\\\ 0&0\end{bmatrix}$ and $B=\begin{bmatrix}0&1\\\
0&0\end{bmatrix}$, $\rm IWR$$(A,B)=3$.

###### Proof.

We have

$M^{2}(A,B)=\begin{bmatrix}0&1&1&0\\\ 0&0&0&0\\\ 1&0&1&0\\\
0&0&0&0\end{bmatrix}\text{~{}and~{}}M^{3}(A,B)=\begin{bmatrix}1&0&0&1&0&1&1&0\\\
0&0&0&0&0&0&0&0\\\ 1&0&1&0&1&0&1&0\\\ 0&0&0&0&0&0&0&0\\\ 0&1&1&0&0&1&1&0\\\
0&0&0&0&0&0&0&0\\\ 1&0&0&1&0&1&0&1\\\ 0&0&0&0&0&0&0&0\end{bmatrix}.$

Reordering columns of $M^{2}(A,B)$ in order given by the permutation $4231$
yields the matrix $\begin{bmatrix}0&1&1&0\\\ 0&0&0&0\\\ 0&0&1&1\\\
0&0&0&0\end{bmatrix}$. By Theorem 14, we have $G^{2}(A,B)$ is word-
representable. However, we have shown in Example 17 that $G^{3}(A,B)$ is non-
word-representable. So $\rm IWR$$(A,B)=3$. ∎

######  Remark 32.

Proposition 31 gives Case 4 in Tables 1. In each of Cases 5, 10, 11, 12, 14,
15, 17, 57, 66, 67, 68, 71, 72, 77, 78, 89, 99, 102, 104, 106, 108, 109, 111
and 112 in Tables 1 and 2, $M^{2}(A,B)$ has a permutation satisfying the
conditions of Theorem 25 and $M^{3}(A,B)$ does not (similarly to Proposition
31). So $\rm IWR$$(A,B)=3$ for $A$ and $B$ in these cases. Moreover, by
Theorem 25, column and row permutations of $A$ and $B$ give the same $\rm
IWR$. Consequently, we also have $\rm IWR$$(A,B)=3$ for $A$ and $B$ in Cases
19, 22, 24, 25, 28, 29, 32, 33, 36, 37, 39, 40, 42, 46, 47, 49, 58, 69, 70,
75, 76, 79, 80 and 90.

######  Proposition 33.

For $A=\begin{bmatrix}1&0\\\ 0&0\end{bmatrix}$ and $B=\begin{bmatrix}0&0\\\
0&1\end{bmatrix}$, $\rm IWR$$(A,B)=4$.

###### Proof.

We have

$M^{3}(A,B)=\begin{bmatrix}1&0&1&0&0&0&1&0\\\ 0&0&0&0&0&1&0&0\\\
1&0&0&0&1&0&1&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&1&0&0&0&1&0\\\ 0&1&0&0&0&1&0&0\\\
1&0&1&0&1&0&1&0\\\ 0&0&0&0&0&0&0&0\end{bmatrix}.$

Reordering columns of $M^{3}(A,B)$ in order given by the permutation
$51732648$ yields the matrix $\begin{bmatrix}0&1&1&1&0&0&0&0\\\
0&0&0&0&0&1&0&0\\\ 1&1&1&0&0&0&0&0\\\ 0&0&0&0&0&0&1&0\\\ 0&0&1&1&0&0&0&0\\\
0&0&0&0&1&1&0&0\\\ 1&1&1&1&0&0&0&0\\\ 0&0&0&0&0&0&0&0\end{bmatrix}$.
By Theorem 14, we have $G^{3}(A,B)$ is word-representable. For

$M^{4}(A,B)=\setcounter{MaxMatrixCols}{16}\begin{bmatrix}0&0&1&0&0&0&1&0&1&0&1&0&0&0&1&0\\\
0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0\\\ 1&0&1&0&1&0&1&0&1&0&0&0&1&0&1&0\\\
0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0\\\ 0&0&1&0&1&0&1&0&0&0&1&0&0&0&1&0\\\
0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0\\\ 1&0&1&0&1&0&0&0&1&0&1&0&1&0&1&0\\\
0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0\\\ 1&0&1&0&0&0&1&0&1&0&1&0&0&0&1&0\\\
0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0\\\ 1&0&0&0&1&0&1&0&1&0&0&0&1&0&1&0\\\
0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0\\\ 0&0&1&0&0&0&1&0&0&0&1&0&0&0&1&0\\\
0&1&0&0&0&1&0&0&0&1&0&0&0&1&0&0\\\ 1&0&1&0&1&0&1&0&1&0&1&0&1&0&1&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\end{bmatrix},$

suppose that a reordering of columns $\rho=\rho_{1}\rho_{2}\cdots\rho_{16}$
exists showing word-representability of $G^{4}(A,B)$ by Theorem 14. Then,

  * •

from row 3, columns 1, 3, 5, 7, 9, 13 and 15 must be (cyclically) consecutive;

  * •

from row 5, columns 3, 5, 7, 11 and 15 must be (cyclically) consecutive;

  * •

from row 7, columns 1, 3, 5, 9, 11, 13 and 15 must be (cyclically)
consecutive.

But then, from the first and the third bullet points, columns 1, 3, 5, 9, 13
and 15 must be consecutive and then column 7 or 11 is next to the left of them
and the other one is next to the right of them. This contradicts to the second
bullet point. So there is no such $\rho$ and $G^{4}(A,B)$ is non-word-
representable. Therefore, $\rm IWR$$(A,B)=4$. ∎

######  Remark 34.

Proposition 33 gives Case 6 in Table 1. In each of Cases 53, 63, 83, 87, 93,
98 and 105 in Tables 1 and 2, $M^{3}(A,B)$ has a permutations satisfying
condition in Theorem 25 but $M^{4}(A,B)$ does not (similarly to Proposition
33). So $\rm IWR$$(A,B)=4$ for $A$ and $B$ in these cases. Moreover, by
Theorem 25, column and row permutations of $A$ and $B$ give the same $\rm
IWR$. Consequently, we also have $\rm IWR$$(A,B)=3$ for $A$ and $B$ in Cases
21, 35, 54, 64, 85, 92 and 95.

By Remarks 30, 32 and 34, we can see that in many cases the index of word-
representability is 2, 3 or 4. Next, we will introduce certain definitions and
theorems to present the cases where the index of word-representability is
infinity.

Let $M$ be an $m\times n$ binary matrix. For convenience, we will represent
rows of $M$ by binary strings of length $n$. For example, we will represent
three rows of ${\tiny\begin{bmatrix}1&1&0&1\\\ 0&1&0&0\\\
0&0&0&1\end{bmatrix}}$ by 1101, 0100 and 0001.

######  Definition 35.

Let $A$ and $B$ be $m\times n$ binary matrices. Define $R^{k}(A,B)$ to be the
set of binary strings representing rows of $M^{k}(A,B)$. So every element of
$R^{k}(A,B)$ is a binary string of length $n^{k}$. Each element of
$R^{k}(A,B)$ is called a row pattern of $M^{k}(A,B)$.

######  Definition 36.

Let $A=\begin{bmatrix}a&b\\\ c&d\end{bmatrix}$ and $B=\begin{bmatrix}e&f\\\
g&h\end{bmatrix}$ be $2\times 2$ binary matrices and $B^{n}$ be the set of
binary strings of length $n$. We define functions
$u_{A,B}:\\{0,1\\}\rightarrow B^{2}$ and $l_{A,B}:\\{0,1\\}\rightarrow B^{2}$
by

$u_{A,B}(0)=ab,l_{A,B}(0)=cd,u_{A,B}(1)=ef\text{~{}~{}and~{}~{}}l_{A,B}(1)=gh.$

Moreover, if $v=v_{1}v_{2}\cdots v_{k}\in B^{k}$, $k\geq 2$, we extend the
definition of the functions $u_{A,B}$ and $l_{A,B}$ to the case of
$B^{k}\rightarrow B^{2k}$ by

$u_{A,B}(v)=u_{A,B}(v_{1})u_{A,B}(v_{2})\cdots u_{A,B}(v_{k})$

and

$l_{A,B}(v)=l_{A,B}(v_{1})l_{A,B}(v_{2})\cdots l_{A,B}(v_{k}).$

When $A$ and $B$ are clear from the context, we can omit the subscript and
write $u$ and $l$ instead of $u_{A,B}$ and $l_{A,B}$, respectively.

######  Example 37.

Let $A=\begin{bmatrix}1&1\\\ 0&0\end{bmatrix}$ and $B=\begin{bmatrix}1&0\\\
1&0\end{bmatrix}$. Then we have

$M^{3}(A,B)=\begin{bmatrix}1&0&1&1&1&0&1&1\\\ 1&0&0&0&1&0&0&0\\\
1&0&1&1&1&0&1&1\\\ 1&0&0&0&1&0&0&0\\\ 1&0&1&0&1&0&1&0\\\ 1&0&1&0&1&0&1&0\\\
1&1&1&1&1&1&1&1\\\ 0&0&0&0&0&0&0&0\end{bmatrix}$

and $R^{4}(A,B)=\\{10111011,10001000,10101010,11111111,00000000\\}$. In fact,
we can find $R^{4}(A,B)$ by using the functions $u_{(A,B)}$ and $l_{A,B}$. As
we start with $M^{0}(A,B)=\begin{bmatrix}0\end{bmatrix}$, we have
$R^{0}(A,B)=\\{0\\}$. Then we apply the functions $u_{A,B}$ and $l_{A,B}$ to
all elements in $R^{0}(A,B)$ to get all elements in $R^{1}(A,B)$:

$\displaystyle u_{A,B}(0)=11\text{~{}~{}and~{}~{}}l_{A,B}(0)=00.$

So, $R^{1}(A,B)=\\{11,00\\}$. Now,

$\displaystyle u_{A,B}(11)=1010$
$\displaystyle\text{~{}~{}and~{}~{}}l_{A,B}(11)=1010$ $\displaystyle
u_{A,B}(00)=1111$ $\displaystyle\text{~{}~{}and~{}~{}}l_{A,B}(00)=0000$

so $R^{2}(A,B)=\\{1010,1111,0000\\}$. Repeating the procedure one more time
yields

$\displaystyle u_{A,B}(1010)=10111011$
$\displaystyle\text{~{}~{}and~{}~{}}l_{A,B}(1010)=10001000$ $\displaystyle
u_{A,B}(1111)=10101010$
$\displaystyle\text{~{}~{}and~{}~{}}l_{A,B}(1111)=10101010$ $\displaystyle
u_{A,B}(0000)=11111111$
$\displaystyle\text{~{}~{}and~{}~{}}l_{A,B}(0000)=00000000,$

and so $R^{3}(A,B)=\\{10111011,10001000,10101010,11111111,00000000\\}$ which
is the same as $R^{4}(A,B)$.

So, all elements in $R^{k}(A,B)$ are obtained by applying $u_{A,B}$ and
$l_{A,B}$ to every element in $R^{k-1}(A,B)$. The next theorem generalizes
this observation, and it can be proved easily by induction.

######  Theorem 38.

Let $A$ and $B$ be $2\times 2$ binary matrices. Then

$R^{k}(A,B)=\\{f_{k}(\cdots
f_{2}(f_{1}(0))\cdots)|f_{i}\in\\{u_{A,B},l_{A,B}\\}\\}\text{~{}for~{}any~{}}k\geq
1.$

######  Definition 39.

Let $v=v_{1}v_{2}\cdots v_{k}\in B^{k}$. Then,
$\Gamma(v):=\\{m\in\\{1,2,\ldots,k\\}|v_{m}=1\\}$.

In order to study row patterns, we introduce a relation $\leq$ on $B^{n}$. Let
$x=x_{1}x_{2}\cdots x_{k}$ and $y=y_{1}y_{2}\cdots y_{k}$ be in $B^{k}$. We
say that $x\leq y$ if and only if $x_{i}=1$ implies $y_{i}=1$ for every
$i\in\\{1,2,\ldots,k\\}$. In other words, $x\leq y$ if and only if
$\Gamma(x)\subseteq\Gamma(y)$. It is easy see that $\leq$ is reflexive,
antisymmetric and transitive, and thus $\leq$ is a partial order.

######  Theorem 40.

Let $A$ and $B$ be $m\times n$ binary matrices. For any $k>1$, if
$(R^{k}(A,B),\leq)$ is a total order, then $G^{k}(A,B)$ is word-representable.

###### Proof.

Let $R^{k}(A,B)=\\{x_{1},x_{2},\ldots,x_{l}\\}$ where $l\geq 1$ and
$x_{1},x_{2},\ldots,x_{l}$ are binary strings of length $n^{k}$. Since
$(R^{k}(A,B),\leq)$ is a total order, w.l.o.g., we assume that $x_{1}\leq
x_{2}\leq\cdots\leq x_{l}$. That is
$\Gamma(x_{1})\subseteq\Gamma(x_{2})\subseteq\cdots\subseteq\Gamma(x_{l})$.
Let

$\displaystyle D_{1}$ $\displaystyle:=\Gamma(x_{1}),$ $\displaystyle D_{2}$
$\displaystyle:=\Gamma(x_{2})\setminus\Gamma(x_{1}),$ $\displaystyle D_{3}$
$\displaystyle:=\Gamma(x_{3})\setminus\Gamma(x_{2}),$
$\displaystyle\text{~{}~{}}\vdots$ $\displaystyle D_{l}$
$\displaystyle:=\Gamma(x_{l})\setminus\Gamma(x_{l-1})\text{~{}~{}~{}~{}and}$
$\displaystyle D_{l+1}$
$\displaystyle:=\\{1,2,\ldots,n^{k}\\}\setminus\Gamma(x_{l}).$

If $D_{j}=\\{i_{j,1},i_{j,2},\ldots,i_{j,|D_{j}|}\\}$ for
$i_{j,1}<i_{j,2}<\cdots<i_{j,|D_{j}|}$, then

$\rho=i_{1,1}i_{1,2}\cdots i_{1,|D_{1}|}i_{2,1}i_{2,2}\cdots
i_{2,|D_{2}|}\cdots i_{l,1}i_{l,2}\cdots i_{l,|D_{l}|}$

is a $n^{k}$-permutation. Let $M^{*}$ be the matrix obtained by reordering
columns of $M^{k}(A,B)$ according to the order given by $\rho$. Then we want
to prove that every row of $M^{*}(A,B)$ is of the form $1^{s}0^{t}$ for some
$s,t\geq 0$. Let $y=y_{1}y_{2}\cdots y_{n^{k}}$ be a row pattern of
$M^{k}(A,B)$ and $y^{*}=y_{1}^{*}y_{2}^{*}\cdots y_{n^{k}}^{*}$ be the row
pattern after reordering $y$. Since $y\in R^{k}(A,B)$, then $y=x_{q}$ for some
$q\in\\{1,2,\ldots,l\\}$. So $y_{i}=1$ for all $i\in\Gamma(x_{q})$ and
$y_{i}=0$ for all $i\notin\Gamma(x_{q})$. That is, $\Gamma(y)$ is

$\\{i_{1,1},i_{1,2},\ldots,i_{1,|D_{1}|},i_{2,1},i_{2,2},\ldots,i_{2,|D_{2}|},\ldots,i_{q,1},i_{q,2},\ldots,i_{l,|D_{q}|}\\}.$

Hence $y^{*}=1^{s}0^{t}$ where $s=|D_{1}|+|D_{2}|+\cdots+|D_{q}|$ and
$t=n^{k}-|D_{1}|-|D_{2}|-\cdots-|D_{q}|$. Therefore every row of $M^{*}(A,B)$
is of the form $1^{s}0^{t}$. By Theorem 14, we have that $G^{k}(A,B)$ is word-
representable. ∎

######  Theorem 41.

Let $A$ and $B$ be $2\times 2$ binary matrices. If $x\leq y$ implies
$\\{u_{A,B}(x),l_{A,B}(x),u_{A,B}(y),l_{A,B}(y)\\}$ is comparable under $\leq$
for binary strings $x$ and $y$ of the same length, then $G^{k}(A,B)$ is word-
representable for any $k\geq 0$.

###### Proof.

We will prove by induction that $R^{k}(A,B)$ is comparable under $\leq$.
Because $0\leq 0$, we have $\\{u_{A,B}(0),l_{A,B}(0)\\}=R^{1}(A,B)$ is
comparable under $\leq$. Suppose that $R^{l}(A,B)$ is comparable under $\leq$
for some $l\geq 1$. Let $v,w\in R^{l+1}(A,B)$. Then

$\displaystyle
v=u_{A,B}(x)\text{~{}~{}or~{}~{}}v=l_{A,B}(x)\text{~{}~{}for~{}some~{}~{}}x\in
R^{l}(A,B)$

and

$\displaystyle
w=u_{A,B}(y)\text{~{}~{}or~{}~{}}w=l_{A,B}(y)\text{~{}~{}for~{}some~{}~{}}y\in
R^{l}(A,B).$

By induction hypothesis, w.l.o.g., we can assume that $x\leq y$. So,
$\\{u_{A,B}(x),l_{A,B}(x),u_{A,B}(y),l_{A,B}(y)\\}$ is comparable and $v$ and
$w$ belong to this set. Thus we have that $v$ and $w$ are comparable. Hence
$R^{k}(A,B)$ is comparable under $\leq$ for any $k\geq 0$. Hence, by Theorem
40, $G^{k}(A,B)$ is word-representable for any $k\geq 0$. ∎

######  Theorem 42.

Let $A$ and $B$ be $2\times 2$ binary matrices. If $\\{u_{A,B}(100),$
$l_{A,B}(100),u_{A,B}(101),l_{A,B}(101)\\}$ is comparable under $\leq$, then
$G^{k}(A,B)$ is word-representable for any $k\geq 0$.

###### Proof.

For convenience, we write $u$ and $l$ instead of $u_{A,B}$ and $l_{A,B}$,
respectively. Suppose that $\\{u(100),l(100),u(101),l(101)\\}$ is comparable
under $\leq$. Let $x=x_{1}x_{2}\cdots x_{m}$ and $y=y_{1}y_{2}\cdots y_{m}$ be
binary strings of length $m$ such that $x\leq y$. Also, let

$\displaystyle R$ $\displaystyle:=\\{i|x_{i}=0,y_{i}=0\\},$ $\displaystyle S$
$\displaystyle:=\\{i|x_{i}=1,y_{i}=1\\}\text{~{}and}$ $\displaystyle T$
$\displaystyle:=\\{i|x_{i}=0,y_{i}=1\\}.$

Note that $R,S,T$ partition the set $\\{1,2,\ldots,m\\}$. Since $u(100)$ and
$l(100)$ are comparable, we have two cases to consider.

If $u(100)\leq l(100)$, then $u(1)\leq l(1)$ and $u(0)\leq l(0)$. So we have
$u(101)\leq l(101)$ and it is impossible that $l(101)\leq u(100)$ and
$l(100)\leq u(101)$. So there are four possible cases here, which are

$\displaystyle u(100)\leq u(101)\leq l(100)\leq l(101),$ $\displaystyle
u(100)\leq u(101)\leq l(101)\leq l(100),$ $\displaystyle u(101)\leq u(100)\leq
l(101)\leq l(100)\text{~{}and}$ $\displaystyle u(101)\leq u(100)\leq
l(100)\leq l(101).$

Similarly, in the case of $l(100)\leq u(100)$, we have $l(1)\leq u(1)$ and
$l(0)\leq u(0)$. So $l(101)\leq u(101)$ and $u(100)\nleq l(100)$ and
$u(101)\nleq l(100)$. So we have four more cases, which are

$\displaystyle l(100)\leq u(100)\leq l(101)\leq u(101),$ $\displaystyle
l(100)\leq l(101)\leq u(101)\leq u(100),$ $\displaystyle l(101)\leq l(100)\leq
u(101)\leq u(100)\text{~{}and}$ $\displaystyle l(101)\leq l(100)\leq
u(100)\leq u(101).$

Next, we will consider comparability of the set $\\{u(x),l(x),u(y),$ $l(y)\\}$
in each case.

  * •

$u(100)\leq u(101)\leq l(100)\leq l(101)$. So we have $u(0)\leq u(1)\leq
l(0)\leq l(1)$. Note that $u(x_{i})\leq u(y_{i})$ and $l(x_{i})\leq l(y_{i})$
for any $i\in T$. Then $u(x)\leq u(y)$ and $l(x)\leq l(y)$. Since
$u(y_{i})\leq l(x_{i})$ where $i$ belongs to R, S or T, so $u(y)\leq l(x)$.
Hence, $u(x)\leq u(y)\leq l(x)\leq l(y)$.

  * •

$u(100)\leq u(101)\leq l(101)\leq l(100)$. So we have $u(0)\leq u(1)\leq
l(1)\leq l(0)$. Note that $u(x_{i})\leq u(y_{i})$ and $l(y_{i})\leq l(x_{i})$
for any $i\in T$. Then $u(x)\leq u(y)$ and $l(y)\leq l(x)$. Since
$u(y_{i})\leq l(y_{i})$ where $i$ belongs to R, S or T, so $u(y)\leq l(y)$.
Hence, $u(x)\leq u(y)\leq l(y)\leq l(x)$.

  * •

$u(101)\leq u(100)\leq l(101)\leq l(100)$. So we have $u(1)\leq u(0)\leq
l(1)\leq l(0)$. Note that $u(y_{i})\leq u(x_{i})$ and $l(y_{i})\leq l(x_{i})$
for any $i\in T$. Then $u(y)\leq u(x)$ and $l(y)\leq l(x)$. Since
$u(x_{i})\leq l(y_{i})$ where $i$ belongs to R, S or T, so $u(x)\leq l(y)$.
Hence, $u(y)\leq u(x)\leq l(y)\leq l(x)$.

  * •

$u(101)\leq u(100)\leq l(100)\leq l(101)$. So we have $u(1)\leq u(0)\leq
l(0)\leq l(1)$. Note that $u(y_{i})\leq u(x_{i})$ and $l(x_{i})\leq l(y_{i})$
for any $i\in T$. Then $u(y)\leq u(x)$ and $l(x)\leq l(y)$. Since
$u(x_{i})\leq l(x_{i})$ where $i$ belongs to R, S or T, so $u(x)\leq l(x)$.
Hence, $u(y)\leq u(x)\leq l(x)\leq l(y)$.

  * •

$l(100)\leq l(101)\leq u(100)\leq u(101)$. So we have $l(0)\leq l(1)\leq
u(0)\leq u(1)$. Note that $l(x_{i})\leq l(y_{i})$ and $u(x_{i})\leq u(y_{i})$
for any $i\in T$. Then $l(x)\leq l(y)$ and $u(x)\leq u(y)$. Since
$l(y_{i})\leq u(x_{i})$ where $i$ belongs to R, S or T, so $l(y)\leq u(x)$.
Hence, $l(x)\leq l(y)\leq u(x)\leq u(y)$.

  * •

$l(100)\leq l(101)\leq u(101)\leq u(100)$. So we have $l(0)\leq l(1)\leq
u(1)\leq u(0)$. Note that $l(x_{i})\leq l(y_{i})$ and $u(y_{i})\leq u(x_{i})$
for any $i\in T$. Then $l(x)\leq l(y)$ and $u(y)\leq u(x)$. Since
$l(y_{i})\leq u(y_{i})$ where $i$ belongs to R, S or T, so $l(y)\leq u(y)$.
Hence, $l(x)\leq l(y)\leq u(y)\leq u(x)$.

  * •

$l(101)\leq l(100)\leq u(101)\leq u(100)$. So we have $l(1)\leq l(0)\leq
u(1)\leq u(0)$. Note that $l(y_{i})\leq l(x_{i})$ and $u(y_{i})\leq u(x_{i})$
for any $i\in T$. Then $l(y)\leq l(x)$ and $u(y)\leq u(x)$. Since
$l(x_{i})\leq u(y_{i})$ where $i$ belongs to R, S or T, so $l(x)\leq u(y)$.
Hence, $l(y)\leq l(x)\leq u(y)\leq u(x)$.

  * •

$l(101)\leq l(100)\leq u(100)\leq u(101)$. So we have $l(1)\leq l(0)\leq
u(0)\leq u(1)$. Note that $l(y_{i})\leq l(x_{i})$ and $u(x_{i})\leq u(y_{i})$
for any $i\in T$. Then $l(y)\leq l(x)$ and $u(x)\leq u(y)$. Since
$l(x_{i})\leq u(x_{i})$ where $i$ belongs to R, S or T, so $l(x)\leq u(x)$.
Hence, $l(y)\leq l(x)\leq u(x)\leq u(y)$.

We can see that $\\{u(x),l(x),u(y),$ $l(y)\\}$ is comparable in every case. By
Theorem 41, $G^{k}(A,B)$ is word-representable for any $k\geq 0$. ∎

######  Remark 43.

Theorem 42 can be applied to check word-representability of $G^{k}(A,B)$. We
can see that $\\{u_{A,B}(100),l_{A,B}(100),u_{A,B}(101),l_{A,B}(101)\\}$ is
comparable under $\leq$ in Cases 2, 7, 8, 13, 51, 56, 61, 84, 94, 100, 103,
107 and 113 in Tables 1 and 2. Then $\rm IWR$$(A,B)=\infty$ for $A$ and $B$ in
these cases. By Theorem 25, column and row permutations of $A$ and $B$ in
these cases preserve the index of word-representability. So we also have $\rm
IWR$$(A,B)=\infty$ for $A$ and $B$ in Cases 18, 23, 27, 30, 34, 43, 44, 48,
52, 59, 62, 86 and 96.

######  Proposition 44.

Let $A=\begin{bmatrix}1&0\\\ 0&0\end{bmatrix}$ and $B=\begin{bmatrix}1&0\\\
0&1\end{bmatrix}$. Then $G^{k}(A,B)$ is word-representable for any $k\geq 0$.

###### Proof.

The case of $k=0$ is trivial. For $k\geq 1$, we let $S^{k}_{0}:=\emptyset$,

$S^{k}_{j}:=\\{s\in\\{1,2,\ldots,2^{k}\\}|s\equiv
2^{j-1}\pmod{2^{j}}\\}\text{~{}for~{}}j\in\\{1,2,\ldots,k\\}$

and

$\displaystyle T^{k}:=\\{x_{1}x_{2}\cdots
x_{2^{k}}|x_{i}=\begin{cases}0\text{~{}if~{}}i\notin S^{k}_{j},\\\
1\text{~{}if~{}}i\in
S^{k}_{j}\end{cases}\text{~{}for~{}some~{}}j\in\\{0,1,\ldots,2^{k}\\}\\}.$

We claim that $R^{k}(A,B)=T^{k}$ for any $k\geq 1$ and prove it by induction
on $k$. It is obvious in the case of $k=1$ because $R^{1}(A,B)=\\{00,10\\}$
while $S_{0}=\emptyset$ and $S_{1}=\\{1\\}$. Suppose $l$ is a positive integer
such that $R^{l}(A,B)=T^{l}$. Let $y\in R^{l+1}(A,B)$, then $y=u_{A,B}(z)$ or
$y=l_{A,B}(z)$ for some $z\in R^{l}(A,B)$. Since $R^{l}(A,B)=T^{l}$, we have

$z=z_{1}z_{2}\cdots
z_{2^{l}}\text{~{}where~{}}z_{i}=\begin{cases}0\text{~{}if~{}}i\notin
S^{l}_{j},\\\ 1\text{~{}if~{}}i\in S^{l}_{j}.\end{cases}$

If $y=u_{A,B}(z)$, then $y=1010\cdots 10$. That is,
$y_{i}=\begin{cases}0\text{~{}if~{}}i\notin S^{l+1}_{1},\\\
1\text{~{}if~{}}i\in S^{l+1}_{1}\end{cases}$, and so $y\in T^{l+1}$. If
$y=l_{A,B}(z)$, the number of $1$’s in $y$ and $z$ is identical because $0$ is
mapped to $00$ and $1$ is mapped to $01$. We can see that $y_{2i}=1$ if and
only if $x_{i}=1$. Hence,

$y_{i}=\begin{cases}0\text{~{}if~{}}i\notin S^{l+1}_{r+1},\\\
1\text{~{}if~{}}i\in S^{l+1}_{r+1}.\end{cases}$

So $R^{l+1}(A,B)\subseteq T^{l+1}$. Conversely, let $v=v_{1}v_{2}\cdots
v_{2^{l+1}}$ where

$v_{i}=\begin{cases}0\text{~{}if~{}}i\notin S^{l+1}_{t},\\\
1\text{~{}if~{}}i\in S^{l+1}_{t}\end{cases}$

for some $t\in\\{0,1,\ldots,l+1\\}$. If $t=0$, note that $v=000\cdots
0=l_{A,B}(000\cdots 0)$ and $000\cdots 0\in R^{l}(A,B)$, and so $v\in
R^{l+1}(A,B)$. If $t=1$, we have $v=1010\cdots 10=u_{A,B}(\bar{v})$ for any
$\bar{v}\in R^{l}(A,B)$. That is $v\in R^{l+1}(A,B)$. Suppose
$t\in\\{2,3,\cdots l+1\\}$ and $w=w_{1}w_{2}\cdots w_{2^{l}}$ be an element of
$T^{l}$ such that

$w_{i}=\begin{cases}0\text{~{}if~{}}i\notin S^{l}_{t-1},\\\
1\text{~{}if~{}}i\in S^{l}_{t-1}.\end{cases}$

By induction hypothesis, $w\in R^{l}(A,B)$. Note that $v=l_{A,B}(w)$ and then
$v\in R^{l+1}(A,B)$. So we have $T^{l+1}\subseteq R^{l+1}(A,B)$. Hence we have
already proved the claim.

Note that $\\{1,2,\ldots,2^{k}-1\\}$ is a disjoint union of
$S_{1},S_{2},\ldots,S_{k}$. If
$S^{k}_{j}=\\{i_{j,1},i_{j,2},\ldots,i_{j,|S^{k}_{j}|}\\}$ for
$i_{j,1}<i_{l,2}<\cdots<i_{j,|S^{k}_{j}|}$, then we can let $\rho$ be the
permutation

$i_{1,1}i_{1,2}\cdots i_{1,|S^{k}_{1}|}i_{2,1}i_{2,2}\cdots
i_{2,|S^{k}_{2}|}\cdots i_{k,1}i_{k,2}\cdots i_{k,|S^{k}_{k}|}2^{k}.$

Since $R^{l}(A,B)=Tt^{k}$, then all $1$’s in each row pattern in $R^{k}(A,B)$
is in columns $i_{j,1},i_{j,2},\ldots,i_{1,|S^{k}_{j}|}$ for some $1<j<k$.
Therefore we can see that every row of the matrix obtained by reordering
columns of $M^{k}(A,B)$ according to the order given by $\rho$ is of the form
$0^{a}1^{b}0^{c}$ for some non-negative integers $a,b$ and $c$. By Theorem 14,
$G^{k}(A,B)$ is word-representable for ant $k\geq 1$. ∎

######  Remark 45.

Proposition 44 gives $\rm IWR$$(A,B)=\infty$ for $A$ and $B$ in Case 9 in
Tables 1. By Theorem 25, column and row permutations of $A$ and $B$ give the
same $\rm IWR$. Consequently, we also have $\rm IWR$$(A,B)=\infty$ for $A$ and
$B$ in Cases 26 and 41.

######  Proposition 46.

Let $A=\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$ and $B=\begin{bmatrix}0&1\\\
1&0\end{bmatrix}$. Then $G^{k}(A,B)$ is word-representable for any $k\geq 0$.

###### Proof.

The case of $k=0$ is trivial. For any binary string $x$, we define $\bar{x}$
to be the binary string obtained by changing digits of $x$ from 0 to 1 and
from 1 to 0. We claim that, for $k\geq 1$, $R^{k}(A,B)=\\{x,\bar{x}\\}$ for
some $x\in B^{2^{k}}$ and prove it by induction on $k$. As
$R^{1}(A,B)=\\{10,01\\}$ and $01=\overline{10}$, the case of $k=1$ is done.
Suppose that $k>1$ is a positive integer such that
$R^{k}(A,B)=\\{x,\bar{x}\\}$ for some $x\in B^{2^{k}}$. Then
$R^{k+1}(A,B)=\\{u_{A,B}(x),l_{A,B}(x),u_{A,B}(\bar{x}),l_{A,B}(\bar{x})\\}$.
Note that $u_{A,B}(0)=l_{A,B}(1)$ and $u_{A,B}(1)=l_{A,B}(0)$. Then
$u_{A,B}(x)=l_{A,B}(\bar{x})$ and $l_{A,B}(x)=u_{A,B}(\bar{x})$. So we have
$R^{k}(A,B)=\\{u_{A,B}(x),l_{A,B}(x)\\}$. Since
$u_{A,B}(0)=\overline{l_{A,B}(0)}$ and $u_{A,B}(1)=\overline{l_{A,B}(1)}$, we
have $u_{A,B}(x)=\overline{l_{A,B}(x)}$. That is,
$R^{k}(A,B)=\\{u_{A,B}(x),\overline{u_{A,B}(x)}\\}$. Hence we have proved the
claim by induction.

So, for any $k\geq 1$, $R^{k}(A,B)=\\{x,\overline{x}\\}$ for some binary
string $x$. Suppose that there are $s$ $1$’s in $x$. Let $\rho$ be a
permutation such that reordering $\begin{bmatrix}x\end{bmatrix}$ according to
the order giving by $\rho$ make all $1$’s in $x$ be together in the first $s$
columns. Then reordering $\begin{bmatrix}\bar{x}\end{bmatrix}$ according to
the order giving by $\rho$ makes all $1$’s in $x$ be together in the last
$2^{k}-s$ columns. Hence each row of the matrix obtained by reordering
$M^{k}(A,B)$ according to the order giving by $\rho$ is $1^{s}0^{2^{k}-s}$ or
$0^{s}1^{2^{k}-s}$. By Theorem 14, $G^{k}(A,B)$ is word-representable for any
$k\geq 0$. ∎

###  4.2 The case when A is the all-one matrix

There are only 16 cases when $A=\begin{bmatrix}1&1\\\ 1&1\end{bmatrix}$. If
$B=\begin{bmatrix}1&1\\\ 1&1\end{bmatrix}$, we have
$M^{0}(A,B)=\begin{bmatrix}0\end{bmatrix}$ and $M^{k}(A,B)$ is all-one matrix
for any $k\geq 1$ which is word-representable by Theorem 14. The rest of this
paper, except Theorem 47, deals with the cases when $B$ has at least one 0.

######  Theorem 47.

Let $A=\begin{bmatrix}1\end{bmatrix}_{m\times n}$ and $B$ be an $m\times n$
binary matrix. Then, $M^{k}(A,B)$ is a submatrix of $M^{k+2}(A,B)$, and
$G^{k}(A,B)$ is an induced subgraph of $G^{k+2}(A,B)$, for any $k\geq 0$.

###### Proof.

Since the case of $B$ being an all-one matrix is trivial, we assume that $B$
is not an all-one matrix. Let $B=\begin{Bmatrix}b_{ij}\end{Bmatrix}_{m\times
n}$ and $b_{rs}=0$ for some $1\leq r\leq m$ and $1\leq s\leq n$. We will prove
by induction on $k$ that $M^{k}(A,B)$ is contained in $M^{k+2}(A,B)$ as a
submatrix by rows $(r-1)m^{k}+1,(r-1)m^{k}+2,\ldots,rm^{k}$ and columns
$(s-1)n^{k}+1,(s-1)n^{k}+2,\ldots,sn^{k}$ for any $k\geq 0$.

Note that $M^{0}(A,B)=\begin{bmatrix}0\end{bmatrix}$,
$M^{1}(A,B)=\begin{bmatrix}1\end{bmatrix}_{m\times n}$ and

$M^{2}(A,B)=\begin{bmatrix}B&B&\cdots&B\\\ B&B&\cdots&B\\\
\vdots&\vdots&\ddots&\vdots\\\ B&B&\cdots&B\\\ \end{bmatrix}.$

Let $M^{2}(A,B)=\begin{bmatrix}m_{ij}\end{bmatrix}$, then $m_{rs}=0$. So
$M^{0}(A,B)$ is a submatrix of $M^{2}(A,B)$ by row $(r-1)m^{0}+1$ and column
$(s-1)n^{0}+1$.

Let $l\geq 1$ be an integer such that $M^{l}(A,B)$ is a submatrix of
$M^{l+2}(A,B)$ by rows $(r-1)m^{k}+1,(r-1)m^{k}+2,\ldots,rm^{k}$ and columns
$(s-1)n^{k}+1,(s-1)n^{k}+2,\ldots,sn^{k}$. For the next iteration of morphism
applied to $M^{l+2}(A,B)$, it is easy to see that $M^{l}(A,B)$ in the rows
$(r-1)m^{k}+1,(r-1)m^{k}+2,\ldots,rm^{k}$ and the columns
$(s-1)n^{k}+1,(s-1)n^{k}+2,\ldots,sn^{k}$ $M^{l+2}(A,B)$ is mapped to
$M^{l+1}(A,B)$ in the rows $(r-1)m^{k+1}+1,(r-1)m^{k+1}+2,\ldots,rm^{k+1}$ and
columns $(s-1)n^{k+1}+1,(s-1)n^{k+1}+2,\ldots,sn^{k+1}$ of $M^{l+3}(A,B)$.
Hence, $M^{k}(A,B)$ is a submatrix of $M^{k+2}(A,B)$ for any $k\geq 0$.
Consequently, $G^{k}(A,B)$ is an induced subgraph of $G^{k+2}(A,B)$ for any
$k\geq 0$. ∎

We know from Theorem 47 that $G^{0}(A,B)\preceq G^{2}(A,B)\preceq
G^{4}(A,B)\preceq\cdots$ and $G^{1}(A,B)\preceq G^{3}(A,B)\preceq
G^{5}(A,B)\preceq\cdots$ where $G\preceq H$ means $G$ is an induced subgraph
of $H$. So we are interested in investigating the smallest integer $l$ such
that $G^{l}(A,B)$ is non-word-representable in both cases of $l$ being even
and $l$ being odd. The cases 114, 119, 120, 123, 124 and 129 in Table 2 are
given by using Proposition 24. Theorem 42 can be applied to Cases 125, 126,
127 and 128, and the index of word-representability in these cases is
infinity. The following propositions discuss the remaining cases.

######  Proposition 48.

For $A=\begin{bmatrix}1&1\\\ 1&1\end{bmatrix}$ and $B=\begin{bmatrix}1&0\\\
0&1\end{bmatrix}$, $\rm IWR$$(A,B)=3$. Moreover, $G^{k}(A,B)$ is not word-
representable for $k\geq 3$.

###### Proof.

Note that $M^{2}(A,B)=\begin{bmatrix}1&0&1&0\\\ 0&1&0&1\\\ 1&0&1&0\\\
0&1&0&1\end{bmatrix}$ and

$M^{3}(A,B)=\begin{bmatrix}1&0&1&1&1&0&1&1\\\ 0&1&1&1&0&1&1&1\\\
1&1&1&0&1&1&1&0\\\ 1&1&0&1&1&1&0&1\\\ 1&0&1&1&1&0&1&1\\\ 0&1&1&1&0&1&1&1\\\
1&1&1&0&1&1&1&0\\\ 1&1&0&1&1&1&0&1\end{bmatrix}.$

Reordering columns of $M^{2}(A,B)$ in order given by 1324 yields the matrix
$\begin{bmatrix}1&1&0&0\\\ 0&0&1&1\\\ 1&1&0&0\\\ 0&0&1&1\end{bmatrix}$. By
Theorem 14, $G^{2}(A,B)$ is word-representable. Let $M^{*}$ be a matrix
obtained from reordering columns of $M^{3}(A,B)$ and every rows of $M^{*}$ are
of the form $0^{r}1^{s}0^{t}$ or $0^{r}1^{s}0^{t}$. Since every rows of
$M^{3}(A,B)$ has 2 zero entries, there is a row of $M^{*}$ of the form
$1^{a}0^{2}1^{6-a}$ where $1\leq a\leq 5$. Note that there exist a row of
$M^{*}$ having $1$’s in the columns $a$ and $a+2+1$. So $M^{*}$ cannot satisfy
the second condition of Theorem 15. Hence $G^{3}(A,B)$ is non-word-
representable, and so $\rm IWR$$(A,B)=3$.

Now we consider the word-representability of $G^{4}(A,B)$. We have

$\displaystyle R^{4}(A,B)=\\{$ $\displaystyle
1011101010111010,0111010101110101,1110101011101010,$ $\displaystyle
1101010111010101,1010101110101011,0101011101010111,$ $\displaystyle
1010111010101110,0101110101011101\\}.$

In order to apply Theorem 15, we assume the existence of an order
$\rho=\rho_{1}\rho_{2}\cdots\rho_{16}$ with the following properties:

  * •

from $1011101010111010\in R^{4}(A,B)$, columns 2, 6, 8, 10, 14 and 16 must be
cyclically consecutive;

  * •

from $1110101011101010\in R^{4}(A,B)$, columns 4, 6, 8, 12, 14 and 16 must be
cyclically consecutive;

  * •

from $1010101110101011\in R^{4}(A,B)$, columns 2, 4, 6, 10, 12 and 14 must be
cyclically consecutive.

It follows from the first and the second bullet points that 6, 8, 14, and 16
must be consecutive and then, w.l.o.g., 2 and 10 is next to the left of them
and then 4 and 12 is next to the right them That means that 2 and 4 cannot be
cyclically consecutive, which contradicts the second bullet point. So there is
no such $\rho$ and $G^{4}(A,B)$ is non-word-representable. As $G^{3}(A,B)$ is
non-word-representable, and the class of word-representable graphs is
hereditary, by Theorem 47, $G^{2k+1}(A,B)$ is non-word-representable for any
$k\geq 1$. Similarly, $G^{2k}(A,B)$ is non-word-representable for any $k\geq
2$ because $G^{4}(A,B)$ is non-word-representable. Therefore, $G^{k}(A,B)$ is
not word-representable for $k\geq 3$.∎

######  Remark 49.

Proposition 48 gives Case 121 in Tables 1, and we obtain $\rm IWR$$(A,B)=3$ in
Case 122 by a column and row permutation of $A$ and $B$.

######  Proposition 50.

For $A=\begin{bmatrix}1&1\\\ 1&1\end{bmatrix}$ and $B=\begin{bmatrix}0&0\\\
1&0\end{bmatrix}$, $\rm IWR$$(A,B)=5$. Moreover, $G^{k}(A,B)$ is not word-
representable for $k\geq 5$.

###### Proof.

It is easy to see that $G^{0}(A,B)$, $G^{1}(A,B)$ and $G^{2}(A,B)$ are word-
representable. Since reordering columns of $M^{3}(A,B)$ in order given by the
permutation 26153748 yields a matrix satisfying the condition in Theorem 14,
$G^{3}(A,B)$ is word-representable. Further, reordering columns of
$M^{4}(A,B)$ in order given by the permutation

$2(10)4(12)3(11)195(13)7(15)6(14)(16)$

also yields a matrix satisfying the condition in Theorem 14, so $G^{4}(A,B)$
is word-representable.

Next, we consider $G^{5}(A,B)$. We use $u$ and $l$ instead of $u_{A,B}$ and
$l_{A,B}$, respectively. In order to apply Theorem 15, we assume the existence
of an order $\rho=\rho_{1}\rho_{2}\cdots\rho_{32}$ proving word-
representability of $G^{5}(A,B)$.

  * •

$l(l(l(u(u(0)))))=10111011101110111011101110111011\in R^{5}(A,B)$ so columns
2, 6, 10, 14, 18, 22, 26 and 30 must be cyclically consecutive in $\rho$.

  * •

$l(u(u(l(l(0)))))=10101010111111111010101011111111\in R^{5}(A,B)$ so columns
2, 4, 6, 8, 18, 20, 22 and 24 must be cyclically consecutive in $\rho$.

  * •

$l(u(l(l(u(0)))))=11111010111111111111101011111111\in R^{5}(A,B)$ so columns
6, 8, 22 and 24 must be cyclically consecutive in $\rho$.

  * •

$u(u(l(l(u(0)))))=11110000111111111111000011111111\in R^{5}(A,B)$ so columns
5, 6, 7, 8, 21, 22, 23 and 24 must be cyclically consecutive in $\rho$.

It follows from the first and the second bullet points that 2, 6, 18, and 22
must be consecutive and then, w.l.o.g., 10, 14, 26 and 30 are next to the left
of these numbers and 4, 8, 20 and 24 are next to the right them. Hence $\rho$
contains

$\\{10,14,26,30\\},\\{2,6,18,22\\},\\{4,8,20,24\\}$

where numbers in $\\{\\}$ are consecutive in $\rho$ but are in some unknown to
us order. From the third bullet point, $\rho$ contains

$\\{10,14,26,30\\},\\{2,18\\},\\{6,22\\},\\{8,24\\},\\{4,20\\}.$

We obtain a contradiction with the fourth bullet point. So there is no such
$\rho$ and $G^{5}(A,B)$ is non-word-representable.

Next, we consider word-representability of $G^{6}(A,B)$. In order to apply
Theorem 15, we assume that there exist a permutation
$\tau=\tau_{1}\tau_{2}\cdots\tau_{64}$ proving word-representability of
$G^{6}(A,B)$.

  * •

$l(u(u(u(u(u(0))))))\in R^{6}(A,B)$ is
1010101010101010101010101010101010101010101010101010101010101010\.
So, all odd columns must be cyclically consecutive in $\tau$.

  * •

$u(u(u(u(l(l(0))))))\in R^{6}(A,B)$ is
111111111111111110000000000000000111111111111111110000000000000000\.
So, columns in $\\{1,2,\ldots,16,33,34,\ldots 48\\}$ must be cyclically
consecutive in $\tau$.

  * •

$u(l(l(u(u(u(0))))))\in R^{6}(A,B)$ is
0011000000110000001100000011000000110000001100000011000000110000\.
So, columns in $\\{3,4,11,12,19,20,27,28,35,36,43,44,51,52,59,60\\}$ must be
cyclically consecutive in $\tau$.

Since all odd columns must be cyclically consecutive in $\tau$, there is a
unique $s\in\\{1,2,\ldots,64\\}$ such that $\tau_{s}$ is odd and $\tau_{s+1}$
is even, where for $s=64$, $s+1:=1$. From the second bullet point, we have

$\displaystyle\\{\tau_{s},\tau_{s-1},\ldots,\tau_{s-15}\\}=\\{1,3,5,\ldots,15,33,35,37,\ldots,47\\}$
and
$\displaystyle\\{\tau_{s+1},\tau_{s+2},\ldots,\tau_{s+16}\\}=\\{2,4,6,\ldots,16,34,36,38,\ldots,48\\}$

where for $i\geq 0$, $\tau_{-i}:=\tau_{64-i}$ and for $s+i\geq 65$,
$s+i:=s+i-64$. On the other hand, from the third bullet point, we have

$\displaystyle\\{\tau_{s},\tau_{s-1},\ldots,\tau_{s-7}\\}=\\{3,11,19,27,35,43,51,59\\}$
and
$\displaystyle\\{\tau_{s+1},\tau_{s+2},\ldots,\tau_{s+8}\\}=\\{4,12,20,28,36,44,52,60\\}$

where the indices less than 1 and larger than 64 are treated as above. We
obtain a contradiction because
$19\notin\\{\tau_{s},\tau_{s-1},\ldots,\tau_{s-15}\\}$ but
$19\in\\{\tau_{s},\tau_{s-1},\ldots,\tau_{s-7}\\}$. Hence, there is no such
$\tau$ and $G^{6}(A,B)$ is non-word-representable. Since the graphs
$G^{5}(A,B)$ and $G^{6}(A,B)$ are not word-representable and the class of
word-representable graphs is hereditary, by Theorem 47, $G^{k}(A,B)$ is non-
word-representable for any $k\geq 5$. ∎

######  Remark 51.

Proposition 50 is Case 117 in Table 1. By Theorem 25, column and row
permutations of $A$ and $B$ give the same $\rm IWR$. Consequently, we also
have $\rm IWR$$(A,B)=5$ for $A$ and $B$ in Cases 115, 116 and 117.

##  5 Concluding remarks

This paper is a major contribution to the study of word-representability of
split graphs. Two key achievements in the paper are as follows:

  * •

Theorem 15 can be used to study word-representability of split graphs via
adjacency matrices, which is a novel approach.

  * •

Necessary conditions for word-representability of split graphs obtained by
iteration of morphism can be checked in polynomial time. Indeed, for a given
such graph defined by matrices $A$ and $B$, we can go through all of $2\times
2$ submatrices in $A$, and the respective submatrices in $B$, and then use our
classification results in Tables 1 and 2 to detect non-word-representability.

As for open directions of research, it would be useful to provide a
classification, similar to that we provided for $2\times 2$ matrices in Tables
1 and 2, for larger matrices, for example, for $2\times 3$ matrices, or
$3\times 3$ matrices, etc. This would enlarge our knowledge of word-
representable split graphs obtained by iteration of morphisms, and hopefully,
will eventually lead to a complete classification of such graphs.

For another research question, we noted in Tables 1 and 2 that if $G^{4}(A,B)$
is word-representable, then $IWR(A,B)=\infty$. In other words, the largest
finite IWR in the case of $2\times 2$ matrices is 4. Is there a reason for
that? Does there exist a positive integer $t$ (a constant, or a function of
$n$ and $m$) making the following statement true “If $A,B$ are $n\times m$
matrices and $G^{t}(A,B)$ is word-representable, then $IWR(A,B)=\infty$”?

Finally, recall that if the leftmost bottom entry of $A$ is $1$ then
$\lim_{k\to\infty}M^{k}(A,B)$ may not be well-defined as the sequence of
graphs $G^{k}(A,B)$, for $k\geq 0$, may not be a chain of induced subgraphs.
In all such cases, for $2\times 2$ matrices, we still have that non-word-
representability of $G^{k}(A,B)$ implies non-word-representability of
$G^{k+1}(A,B)$. Is it always the case for $m\times n$ matrices $A$ and $B$? If
not, then how do we characterize the situations when it is the case?

## References

  * [1] H. Z.Q. Chen, S. Kitaev, A. Saito. Representing split graphs by word, Discussiones Mathematicae Graph Theory, to appear 2020.
  * [2] G.-S. Cheon, M. Kim, J. Kim, S. Kitaev. Word-representable of Toeplitz graphs. Disc. Appl. Math. 270 (2019) 96–105.
  * [3] S. Foldes, P. L. Hammer. Split graphs. In Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, 1977), pages 311–315. Congressus Numerantium, No. XIX.
  * [4] M. Halldórsson, S. Kitaev, A. Pyatkin. Semi-transitive orientations and word-representable graphs. Discr. Appl. Math. 201 (2016) 164–171.
  * [5] S. Kitaev. A Comprehensive Introduction to the Theory of Word-Representable Graphs, In: Developments in Language Theory: 21st International Conference, DLT, Liege, Aug 7–11, 2017. Lecture Notes in Comp. Sci. 10396 (2017) 36–67.
  * [6] S. Kitaev, V. Lozin. Words and Graphs, Springer, 2015.
  * [7] S. Kitaev, Y. Long, J. Ma, H. Wu. Word-representability of split graphs, arXiv:1709.09725.
  * [8] M. Lothaire. Combinatorics on words, Encyclopedia of Mathematics and its Applications, 17, Addison-Wesley Publishing Co., Reading, Mass, 1983.