1 Introduction

A word-representable graph is a graph which can be encoded linearly by a word where the nodes of the graph are the word’s letters. For each two adjacent nodes in the graph, the associated letters must alternate in the word, and for each two nodes not connected by an edge, the associated letters must not alternate, e.g., the triangle graph, i.e. the complete graph with three nodes \(\texttt {a}\), \(\texttt {f}\), and \(\texttt {l}\), is for instance represented by the word alfalfa since all three letters alternate pairwise with each other witnessed by the projections alala, afafa, and lflf. Here, the projection of a word onto a set of letters is the word obtained by deleting all other letters. Two letters alternate if none of them occurs at consecutive positions in the appropriate projection of the word. The word banana also represents a graph with three nodes (it has three different letters), but only \(\texttt {a}\) and \(\texttt {n}\) are connected by an edge; \(\texttt {b}\) and \(\texttt {a}\) (and \(\texttt {b}\), \(\texttt {n}\) resp.) are not adjacent since \(\texttt {a}\texttt {a}\) (and \(\texttt {n}\texttt {n}\) resp.) occurs in the projection \(\texttt {b}\texttt {a}\texttt {a}\texttt {a}\) (and \(\texttt {b}\texttt {n}\texttt {n}\) resp.). See Fig. 1 for depictions of the two examples.

Fig. 1
figure 1

The graphs represented by \(\texttt {alfalfa}\) and \(\texttt {banana}\) resp

Full size image

The theory of word-representable graphs was introduced in 2008 by Kitaev and Pyatkin [20] intended as a tool for semigroup theory (cf. [22]). By now, word-representable graphs have applications in periodic scheduling [13, 17], topology [25], and the power domination problem from physics [2]. From a theoretical point of view they are of interest since they generalise several important classes of graphs such as circle graphs, 3-colourable graphs, and comparability graphs. An introduction to word-representable graphs can be found in [17, 18]. There are also several generalisations of word-representable graphs in the literature. Graphs representable by pattern-avoiding words have been heavily investigated in e.g. [15, 19]. Other generalisations were presented in [3, 16].

However, not all graphs are word-representable, witnessed by a pentagon with an additional node connected to all of the pentagon’s nodes [20] (cf. Fig. 2).

Fig. 2
figure 2

Smallest non-representable graph

Full size image

Thus, a line of research started to determine the graphs which are word-representable. A fundamental result was shown by Halldórsson et al. in [14], where they proved that a graph is word-representable iff it admits a semi-transitive orientation. For results about operations preserving word-representability, see [4, 17] and the references therein. An asymptotic result about the number of word-representable graphs can be found in [5]. There is a lot of research about the word-representability of specific graph classes like grid graphs (cf. [11] and the references therein) and split graphs (cf. [21] and the references therein). From an algorithmic point of view it is important to note that deciding word-representability is NP-complete, and classical graph problems like vertex colouring remain NP-hard. An exception to this is the maximum clique problem, which is solvable in polynomial time (cf. [17]).

Still from the graphs perspective but with a focus on words, the minimal length representation of a graph is of interest. While Gaetz and Ji investigated this in the general case in [10], the research is often restricted to k-uniform words (each letter occurs exactly k times). Graphs that can be represented by a k-uniform word are called k-representable. For \(k=1\) and \(k=2\), k-representable graphs are well studied and coincide with the classes of complete graphs and circle graphs (cf. [17]). For higher values of k, no characterisation is known.

Our Contribution. First, we solve the open problem about a characterisation of k-representability by introducing the notion of circle-representation and investigating the cuts of edges. Afterwards, we investigate word-representable graphs from the perspective of combinatorics on words. Rotating a word gives the class of conjugate words, which is well studied, e.g., since the lexicographically smallest word in this class is the Lyndon word. We characterise, given a word, how the represented graphs change on rotating the word and present an efficient algorithm to compute them. Then, we show that palindromes present exactly a form of star graphs. Based on this result, we look in detail at the set of k-local words [1, 7, 9] and the graphs they represent. Here, we focus mainly on 1-local words since they are tightly related to palindromes, and we prove that every graph represented by a 1-local word is a comparability graph, respectively. Lastly, we show that all words representing the same graph form a regular language.

Structure of the Work. In Sect. 2 we introduce the basic definitions and notations. In Sect. 3 we present the characterisation for k-representability. The next two sections contain the results on the graphs represented by rotations of a given word and by k-local words. The proof of the regularity of the language of all words representing a graph can be found in Sect. 6. Finally, in Sect. 7 we provide concluding remarks.

2 Preliminaries

Let \({\mathbb {N}}\) denote the set of natural numbers \(\{1, 2, 3, \dots \}\), and let \({\mathbb {N}}_0 {:}{=} {\mathbb {N}}\cup \{0\}\). We define \([i,j] {:}{=} \{n\in {\mathbb {N}}\mid i\le n\le j \}\) for \(i,j\in {\mathbb {N}}\), and set \([n] {:}{=} [1,n]\) for \(n\in {\mathbb {N}}\) and \([n]_0 {:}{=} [0,n]\). For a set M and \(k\in {\mathbb {N}}_0\), let \(\left( {\begin{array}{c}M\\ k\end{array}}\right) \) be the set of all of M’s subsets of cardinality k. By \(\dot{\cup }\) we denote the disjoint union of sets. We first introduce the notations from combinatorics on words and graph theory before we present the basic definitions from the domain of word-representable graphs.

An alphabet is a finite set \(\Sigma = \{\texttt {a}_1,\ldots , \texttt {a}_{\ell }\}\) of \(\ell \in {\mathbb {N}}\) symbols, called letters. \(\Sigma ^*\) denotes the set of all finite words over \(\Sigma \), i.e., the free monoid over \(\Sigma \). The empty word is denoted by \(\varepsilon \) and \(\Sigma ^+ = \Sigma ^* \setminus \{\varepsilon \}\). The length of a word w is denoted by |w|. Define \(\Sigma ^k {:}{=} \{w \in \Sigma ^* \mid |w| = k\}\) for a \(k \in {\mathbb {N}}\). The number of occurrences of a letter \(\texttt {a}\in \Sigma \) in a word \(w \in \Sigma ^*\) is denoted by \(|w|_\texttt {a}\), and w is called k-uniform for some \(k\in {\mathbb {N}}\) if \(|w|_{\texttt {a}}=k\) for all \(\texttt {a}\in \Sigma \). Define the set of letters occurring in \(w \in \Sigma ^*\) by \({{\,\textrm{alph}\,}}(w) = \{\texttt {a}\in \Sigma \mid |w|_\texttt {a}> 0\}\). The \(i^{\text {th}}\) letter of a word w is given by w[i] for \(i \in [|w|]\). For a given word \(w \in \Sigma ^n\), the reversal of w is defined by \(w^R = w[n]w[n - 1]\cdots w[2]w[1]\). The powers of \(w \in \Sigma ^*\) are defined recursively by \(w^0 = \varepsilon , w^n = ww^{n-1}\) for \(n \in {\mathbb {N}}\). A word \(u \in \Sigma ^*\) is a factor of \(w \in \Sigma ^*\), if \(w = xuy\) holds for some words \(x, y \in \Sigma ^*\). Here, u is a suffix of w if \(y = \varepsilon \) holds. The set of factors of w is denoted by \({{\,\textrm{Fact}\,}}(w)\). The factor \(w[i]w[i + 1]\cdots w[j]\) of w is denoted by w[i..j] for \(1 \le i \le j \le |w|\). A letter square in w is a factor u of length 2 with \(u[1]=u[2]\). A word w is a palindrome if \(w=w^R\). A function \(f:\Sigma ^{*}\rightarrow \Sigma ^{*}\) is called a morphism, if \(f(xy)=f(x)f(y)\) for all \(x,y\in \Sigma ^{*}\) (notice that for a morphic function it suffices to have the images of all letters from \(\Sigma \)). We define the projective morphism \(\pi _{\Gamma }: \Sigma ^* \rightarrow \Sigma ^*\) onto \(\Gamma \subseteq \Sigma \) by \(\pi _{\Gamma }(\texttt {a})=\texttt {a}\) if \(\texttt {a}\in \Gamma \) and \(\pi _{\Gamma }(\texttt {a})=\varepsilon \) otherwise for all \(\texttt {a}\in \Sigma \). Two words \(w_1,w_2\in \Sigma ^{*}\) are called conjugate (\(w_1\sim w_2\)) if there exist \(x,y\in \Sigma ^{*}\) such that \(w_1=xy\) and \(w_2=yx\). For further definitions from combinatorics on words, we refer to [23].

An undirected graph is a tuple \(G=(V,E)\) with a finite set V of nodes and a set \(E \subseteq \left( {\begin{array}{c}V\\ 2\end{array}}\right) \) of edges. A graph \(G=(V,E)\) is directed, if \(E \subseteq \{(v_1,v_2) \in V^2\mid v_1 \ne v_2\}\). The set \(\left( {\begin{array}{c}V\\ 2\end{array}}\right) \backslash E\) is called the set of anti-edges of a given undirected graph. The vertex set of a graph G is denoted by V(G) and the edge set by E(G). An orientation of an undirected graph is a directed graph that results from assigning a direction to each edge. An orientation of a graph is transitive if for all edges (u, v) and (v, z) there is also an edge (u, z). A graph is a comparability graph if it admits a transitive orientation. A star graph is a graph \((V\dot{\cup } \{x\},\{\{x,v\}\mid v \in V\})\), i.e., there is a node x called the centre with edges to all other vertices, and there are no other edges in the graph. A graph \(G=(V,E)\) is an extended star graph, if there exists \(U\subseteq V\) such that (U, E) is a star graph, i.e., in addition to the star graph, we can have isolated (not incident with any edge) nodes. A complete graph is a graph without anti-edges. Given \(k\in {\mathbb {N}}\), a k-colouring of a graph \(G=(V,E)\) is a function \(f:V \rightarrow [k]\) with \(f(a)\ne f(b)\) for all \(\{a,b\} \in E\). A graph is k-colourable if there is a k-colouring for it.

Definition 1

Two distinct letters \(\texttt {a},\texttt {b}\in \Sigma \) alternate in a word \(w\in \Sigma ^{*}\) if \(\pi _{\{\texttt {a},\texttt {b}\}}(w)\) is \((\texttt {a}\texttt {b})^n\), \((\texttt {a}\texttt {b})^n\texttt {a}\), \((\texttt {b}\texttt {a})^n\), or \((\texttt {b}\texttt {a})^n\texttt {b}\) for some \(n \in {\mathbb {N}}\).

In other words, \(\texttt {a},\texttt {b}\in {{\,\textrm{alph}\,}}(w)\) alternate in w if no letter occurs at consecutive positions in the projection to \(\texttt {a}\) and \(\texttt {b}\). For example, consider the word rotator. All letters (but \(\texttt {a}\) itself) alternate with \(\texttt {a}\), but every other pair of letters does not, since we have, e.g., \(\pi _{\{\texttt {r},\texttt {t}\}}(\texttt {rotator})=\texttt {r}\texttt {t}\texttt {t}\texttt {r}\).

Definition 2

A graph \(G = (V, E)\) is represented by a word \(w\in \Sigma ^{*}\) if \({{\,\textrm{alph}\,}}(w)=V\) and for all \(\texttt {a},\texttt {b}\in V\), \(\texttt {a}\) and \(\texttt {b}\) alternate in w iff \(\{\texttt {a},\texttt {b}\} \in E\). A graph is word-representable iff there is a word representing it. A graph is k-representable for some \(k \in {\mathbb {N}}\) iff there exists a k-uniform word representing it. The graph represented by a word w is denoted by G(w).

Since \(\texttt {a}\) alternates with every other letter and no other pair of letters alternates, the word rotator represents the graph depicted in Fig. 3.

Fig. 3
figure 3

The graph represented by the word rotator

Full size image

The computational model we use is the standard unit-cost RAM with logarithmic word size (cf. [6]).

3 k-Circle representation

In this short section, we present a classical result on word-representable graphs. So far, there are well-known characterisations of k-representable graphs for \(k\le 2\) but none for \(k\ge 3\). It is known that 2-representable graphs are exactly the 2-polygon-circle graphs, better known as circle graphs. However, this cannot be generalised to k-representable graphs being k-polygon-circle-graphs, as shown in [8]. In order to give a characterisation for \(k\ge 3\), we take a different but similar approach to [8] and define the notion of a k-circle representation.

Definition 3

For \(k\in {\mathbb {N}}\), a k-circle representation of a graph G is a circle with an inscribed k-gon (i.e. a k-gon with all the vertices being on the circle) for every vertex of G such that the sides of any two k-gons intersect 2k times iff there is an edge between the related vertices in the graph.

An example of a graph and a 3-circle-representation of it can be found in Fig. 4. In this graph there is an edge \(\{\texttt {a},\texttt {b}\}\), and as illustrated by Fig. 5 the triangles for \(\texttt {a}\) and \(\texttt {b}\) have 6 intersections. The same applies for \(\{\texttt {a},\texttt {c}\}\). Since there is no edge \(\{\texttt {a},\texttt {c}\}\), the corresponding triangles have only four intersections.

Fig. 4
figure 4

A graph and a 3-circle-representation of it

Full size image
Fig. 5
figure 5

Intersections of the triangles from Fig. 4

Full size image

Lemma 1

The sides of two k-gons inscribed into a circle cannot have more than 2k intersections.

Proof

The polygons are convex because they are inscribed into a circle. That means a line cannot have more than two intersections with any of the k-gons. Thus, every side of the first k-gon has not more than 2 intersections with the sides of the second k-gon. Because there are k sides, the sides of the two k-gons have not more than 2k intersections. \(\square \)

By Lemma 1, we get a characterisation for k-representability for all \(k\ge 3\).

Theorem 2

For \(k \ge 3\), a graph is k-representable iff there is a k-circle representation of it.

Proof

Let \(k \ge 3\). Let \(G=(V,E)\) be k-representable by the k-uniform word \(w\in V^{*}\). We choose \(k \cdot |V|\) distinct points on the circle. Starting at any of them, we go around the circle clockwise and label each point with a letter in w such that the order of the word’s letters is preserved. Let \(\texttt {a}_i\) be the \(i^{\text {th}}\) point labelled with \(\texttt {a}\) for every \(\texttt {a}\in V\) and \(i \in [k]\). Connecting every point \(\texttt {a}_i\) with \(\texttt {a}_{i+1}\) and \(\texttt {a}_k\) with \(\texttt {a}_1\) for \(i \in [k-1]\) yields an inscribed k-gon for every vertex. Let \(\texttt {a},\texttt {b}\in V\) and let A, B be the polygons related to \(\texttt {a}\) and \(\texttt {b}\). First, consider \(\{\texttt {a},\texttt {b}\}\in E\), i.e., \(\texttt {a}\) and \(\texttt {b}\) alternate in w. Let \(i \in [k]\) and \(j=(i+1) {{\,\textrm{mod}\,}}k\). There is exactly one point \(\texttt {b}_l\) between \(\texttt {a}_i\) and \(\texttt {a}_j\), i.e., it was labelled after \(\texttt {a}_i\) and before \(\texttt {a}_j\). Thus, both of B’s sides connected with \(\texttt {b}_l\) intersect the side between \(\texttt {a}_i\) and \(\texttt {a}_j\). Because there are k pairs \(\texttt {a}_i\) and \(\texttt {a}_j\), there are 2k intersections. Now, consider \(\{\texttt {a},\texttt {b}\} \notin E\), i.e, \(\texttt {a}\) and \(\texttt {b}\) do not alternate in w. There exists \(i \in [k]\) with \(j=(i+1) {{\,\textrm{mod}\,}}k\) such that there is no \(\texttt {b}_l\) between \(\texttt {a}_i\) and \(\texttt {a}_j\). This means the line from \(\texttt {a}_i\) to \(\texttt {a}_j\) does not intersect with any side of B. Because every of the k sides of A cannot have more than 2 intersections with B, A and B have less than 2k intersections. This concludes that we have a k-circle representation of G.

For the other direction, assume \(G=(V,E)\) has a k-circle representation. Now, we pick some point on the circle. We start with the empty word, go clockwise around the circle, and for any corner we pass, we append the graph’s vertex related to the corner’s polygon. Once we reach our starting point we have a k-uniform word w with \({{\,\textrm{alph}\,}}(w)=V\). For the same reason as above we have 2k intersections between the polygons A, B iff the related letters \(\texttt {a}\) and \(\texttt {b}\) alternate in w. Therefore, w represents G. \(\square \)

By Theorem 2, we can construct a k-circle representation of G(w) given a k-uniform word w by writing the letters on a circle and connecting all occurrences of the same letters as an inscribed polygon. Also, given a k-circle-representation we can determine a word representing the associated graph by reading the letters on the circle, starting with any letter. For example, the graph from Fig. 4 is represented by the word cabcacbab and all of its conjugates.

4 Graphs of conjugate words

Motivated by the k-circle representation in the last section, in this section we mainly investigate the graphs represented by the conjugates of a given word. These conjugacy classes are a very well studied part of combinatorics on words since for instance the lexicographically smallest words in such a class are the famous Lyndon words [24]. All words in a conjugacy class can be obtained by writing the letters of the given word on a circle (cf. Sect. 3) and reading the words from each possible starting point. Thus, now our goal is to investigate the class of graphs represented by the conjugates of a given word w. Notice that for some \(k\in {\mathbb {N}}\) two k-uniform conjugates always represent the same graph, cf. [20]. However in the general case, two conjugates do not necessarily represent the same graph, since by rotating the word, letter squares may appear or disappear. Consider for instance \(w=\texttt {abcba}\) representing a graph with the edges \(\{\texttt {a},\texttt {c}\}\), \(\{\texttt {b},\texttt {c}\}\). The conjugate \(u=\texttt {bcbaa}\) has still the edge \(\{\texttt {b},\texttt {c}\}\) but not the edge \(\{\texttt {a},\texttt {c}\}\).

We start this section with an extended example for motivation.

Example 1

Consider the word decide not having a letter square. Here, we have the projections

$$\begin{aligned} \texttt {dede},\texttt {dcd},\texttt {did},\texttt {ece},\texttt {eie},\texttt {ci} \end{aligned}$$

leading to the following complete graph.

figure a

Rotating the first letter to the end, gives us \(\texttt {ecided}\). Since we have now the projections \(\texttt {cdd}\) and \(\texttt {idd}\), we lose two edges.

figure b

The next rotation leads to \(\texttt {cidede}\). Only edges incident with \(\texttt {e}\) can be removed in this step and indeed, we lose again two edges.

figure c

Since \(\texttt {c}\) and \(\texttt {i}\) only occur each once in \(\texttt {decide}\), the next two rotations represent the same graph as before. The next change occurs for the last rotation \(\texttt {edecid}\). By the projections \(\texttt {did}\) and \(\texttt {dcd}\), we get two new edges.

figure d

Before we further investigate conjugates, we start with a straightforward result following directly from the previous definitions about a representative with all letter squares moved to the right end.

Remark 1

Let \(w \in \Sigma ^{*}\) with \(\texttt {a}\texttt {a}\in {{\,\textrm{Fact}\,}}(w)\) for a letter \(\texttt {a}\in \Sigma \). Then, w and \(\pi _{\Sigma {\setminus } \{\texttt {a}\}}(w)\texttt {a}\texttt {a}\) represent the same graph.

Remark 1 guarantees that the following definition is well-defined, and the proposition afterwards shows that we can compute this representative in linear time in w’s length if the alphabet’s size is smaller than the word’s length.

Definition 4

Let \(w\in \Sigma ^{*}\) and \(S=\{\texttt {a}\in \Sigma \mid \texttt {a}\texttt {a}\in {{\,\textrm{Fact}\,}}(w)\}\). Set \(w'=\prod _{s\in S}s^2\) as the concatenation of all letters from S squared obeying some fixed order on S. Define the separated representative of w by \({{\,\textrm{sep}\,}}(w)=\pi _{\Sigma \backslash S}(w)w'\).

The following remark captures some immediate results about \({{\,\textrm{sep}\,}}(w)\).

Remark 2

By Remark 1, \({{\,\textrm{sep}\,}}(w)\) represents the same graph as w and can be computed in time \(O(|w|+|\Sigma |)\). Moreover, we have \(|{{\,\textrm{sep}\,}}(w)|\le |w|-\sum _{\texttt {a}\in \Sigma ,\texttt {a}^2\in {{\,\textrm{Fact}\,}}(w)}(|w|_{\texttt {a}}-2)\).

The representative \({{\,\textrm{sep}\,}}(w)\) makes the letter squares in a word explicit by stating them grouped at the end of the word. As mentioned above, conjugates of words may have letter squares while the word itself does not contain any. This can only occur if there is a conjugate yx of xy such that \(x[1]=y[|y|]\) for some \(x,y\in \Sigma ^{*}\). To capture this property, we define the notion of a circular square.

Definition 5

A pair \((\texttt {a},i)\) is a circular square in \(w\in \Sigma ^{*}\) with \(|{{\,\textrm{alph}\,}}(w)|>1\) if \(w[i]=w[1+i {{\,\textrm{mod}\,}}|w|]=\texttt {a}\).

Consider again the word \(w=\texttt {rotator}\) having the circular square \((\texttt {r},7)\). Besides w itself the conjugacy class contains the words \(\texttt {otatorr}\), \(\texttt {tatorro}\), \(\texttt {atorrot}\), \(\texttt {torrota}\), \(\texttt {orrotat}\), \(\texttt {rrotato}\) all having only \(\texttt {r}\) as a square at different positions. This leads to the immediate remark.

Remark 3

The number of circular squares in \(w\in \Sigma ^{*}\) is the same as in every conjugate of w. Moreover, (w[|w|], |w|) is the only possibility for a circular square which is not a letter square. Note that for each letter square there exists exactly one conjugate of w such that the letter square becomes a circular square which is not a letter square: \(\texttt {lossless}\) has two letter squares, and the conjugates \(\texttt {slesslos}\) and \(\texttt {slossles}\) have circular squares which are not letter squares.

The following theorem characterises exactly for each given pair of letters \(\texttt {a},\texttt {b}\in {{\,\textrm{alph}\,}}(w)\) whether there are conjugates of w representing graphs with and without the edge \(\{\texttt {a},\texttt {b}\}\).

Theorem 3

Let \(w\in \Sigma ^{*}\) and \(\texttt {a},\texttt {b}\in {{\,\textrm{alph}\,}}(w)\) with \(\texttt {a}\ne \texttt {b}\). Set \(u=\pi _{\{\texttt {a},\texttt {b}\}}(w)\). Let k be the number of circular squares in u.

1. There is a conjugate of w representing a graph with an edge \(\{\texttt {a},\texttt {b}\}\) iff \(k \le 1\).

2. There is a conjugate of w representing a graph without an edge \(\{\texttt {a},\texttt {b}\}\) iff \(k \ge 1\).

Proof

First, let \(w'\) be a conjugate of w representing a graph with an edge \(\{\texttt {a},\texttt {b}\}\). Choose \(x,y\in \Sigma ^{*}\) with \(w'=xy\) and \(w=yx\). Set \(u'=\pi _{\{\texttt {a},\texttt {b}\}}(w')\), which is a conjugate of u. We know that \(\texttt {a}\) and \(\texttt {b}\) alternate in xy, which means there is no letter square and at most one circular square in \(u'\). Therefore, we have \(k \le 1\). For the other direction, assume \(k\le 1\). If there is no letter square in u, \(\texttt {a}\) and \(\texttt {b}\) alternate and there is an edge \(\{\texttt {a},\texttt {b}\}\) in G(w). Otherwise, we can assume \(\texttt {a}\texttt {a}\) is a factor of u w.l.o.g. There are \(x,y \in \Sigma ^{*}\) with \(w=xy\) such that \((\texttt {a},|u'|)\) is a circular square in \(u'=\pi _{\{\texttt {a},\texttt {b}\}}(yx)\). Since \(k \le 1\), there is no letter square in \(u'\), and \(\texttt {a}\) and \(\texttt {b}\) alternate in yx. It follows that G(yx) has an edge \(\{\texttt {a},\texttt {b}\}\).

For the second claim, let \(w'\) be a conjugate of w representing a graph without the edge \(\{\texttt {a},\texttt {b}\}\). Define \(u'=\pi _{\{\texttt {a},\texttt {b}\}}(w')\), which is a conjugate of u. We know that \(\texttt {a}\) and \(\texttt {b}\) do not alternate in \(w'\), which means there is a letter square in \(u'\). Therefore, we have \(k \ge 1\). For the other direction, assume \(k \ge 1\). If there is a letter square in u, the word w is a conjugate of itself, and there is no edge \(\{\texttt {a},\texttt {b}\}\) in G. Otherwise, we have \(u[1]=u[|u|]\). There are \(x,y \in \Sigma ^{*}\) with \(xy=w\) such that \(\texttt {a}\texttt {a}\) is factor of \(u'=\pi _{\{\texttt {a},\texttt {b}\}}(yx)\) w.l.o.g. Hence, yx is a conjugate of w representing a graph without the edge \(\{\texttt {a},\texttt {b}\}\). \(\square \)

In order to further investigate the set of graphs represented by the conjugates of a given word \(w\in \Sigma ^{*}\), we introduce the notion of optional edges. These edges are exactly the edges in G that can be removed or added by the conjugates of w.

Definition 6

Let \(w\in \Sigma ^{*}\) and \(\texttt {a},\texttt {b}\in {{\,\textrm{alph}\,}}(w)\) with \(\texttt {a}\ne \texttt {b}\). We say that \(\{\texttt {a},\texttt {b}\}\) is an optional edge of w if there is exactly one circular square in \(\pi _{\{\texttt {a},\texttt {b}\}}(w)\).

Fig. 6
figure 6

Graph with optional edges in the word decide (the non-optional edges are dotted lines)

Full size image

In Fig. 6 the graph with optional edges for the word decide is depicted. Notice that we are investigating conjugates of words and obtain their graphs. Thus, we are talking about optional edges in words since representatives of the same graph can have different optional edges, e.g., the words \(\texttt {a}\texttt {a}\texttt {b}\) and \(\texttt {a}\texttt {a}\texttt {b}\texttt {b}\) both represent the same graph, but the edge \(\{\texttt {a},\texttt {b}\}\) is only optional in \(\texttt {a}\texttt {a}\texttt {b}\). Thus, an optional edge \(\{\texttt {a},\texttt {b}\}\) does not have to be an edge in the graph and can hence be an anti-edge. This leads to the following observation.

Remark 4

If \((\texttt {a},i)\) is the only circular square in a word w with \({{\,\textrm{alph}\,}}(w)=\{\texttt {a},\texttt {b}\}\), we have \(|w|_\texttt {a}=|w|_\texttt {b}+1\).

Proposition 4

Let \(w\in \Sigma ^{*}\) be a word representing the graph \(G=({{\,\textrm{alph}\,}}(w),E)\) and \(E'\) be the set of optional edges of w. Then, \(({{\,\textrm{alph}\,}}(w),E')\) is 2-colourable.

Proof

Define the colouring \(f:V\rightarrow \{0,1\}\) by \(f(v)=|w|_v {{\,\textrm{mod}\,}}2\). Let \(\texttt {a},\texttt {b}\in {{\,\textrm{alph}\,}}(w)\) and \(\{\texttt {a},\texttt {b}\} \in E'\). Since \(\{\texttt {a},\texttt {b}\}\) is an optional edge of w, we have by Remark 4\(|w|_\texttt {a}=|w|_\texttt {b}\pm 1\). Thus, \(f(\texttt {a})=|w|_\texttt {a}{{\,\textrm{mod}\,}}2 \ne |w|_\texttt {b}{{\,\textrm{mod}\,}}2 = f(\texttt {b})\). \(\square \)

Corollary 5

For a graph G, there is a word \(w\in \Sigma ^{*}\) representing G with every edge and anti-edge of G being an optional edge of w iff G has at most two nodes.

Proof

Let w be a word representing a graph \(G=({{\,\textrm{alph}\,}}(w),E)\) with every edge and anti-edge being an optional edge of w, and let \(E'\) be the set of optional edges of w. This means \((V,E')\) is the complete graph, which needs to be 2-colourable by Proposition 4. The complete graph is only 2-colourable if it has at most two nodes. For the other direction, let G be a graph with at most two nodes. If G has less than two nodes, there is nothing to show. If G has exactly two nodes \(\texttt {a}\) and \(\texttt {b}\), then \(\texttt {a}\texttt {a}\texttt {b}\) or \(\texttt {a}\texttt {b}\texttt {a}\) represents G with \(\{a,b\}\) being optional. \(\square \)

Before we present an algorithm that computes the graphs represented by the conjugates of a word, we investigate in more detail which conjugate contains a particular edge. For \(w\in \Sigma ^{*}\), \(i\in [|w|]\), and \(\texttt {a},\texttt {b}\in \Sigma \) with \(\texttt {a}\ne \texttt {b}\), define the set of w’s indices such that the rotation \(w[i+1..|w|]w[1..i]\) contains the edge \(\{\texttt {a},\texttt {b}\}\) by \(I_w(\{\texttt {a},\texttt {b}\})=\{i\in [|w|]\mid \{\texttt {a},\texttt {b}\} \in E(G(w[i+1..|w|]w[1..i]))\}\). For all \(u,v \in \Sigma ^{*}\) with \(\texttt {a},\texttt {b}\in {{\,\textrm{alph}\,}}(uv)\) and \(\texttt {a}\ne \texttt {b}\), we have immediately \(\{\texttt {a},\texttt {b}\} \in E(G(vu))\) iff \(|u|\in I_{uv}(\{\texttt {a},\texttt {b}\})\). On the other hand, given \(w \in \Sigma ^{*}\) and \(G=({{\,\textrm{alph}\,}}(w),E)\), there is a conjugate of w representing G iff there is \(i \in [|w|]\) with \(\{a,b\} \in E\) exactly for all \(i \in I_w(\{\texttt {a},\texttt {b}\})\). This leads to the following theorem.

Theorem 6

Let \(w\in \Sigma ^{*}\) represent \(G=({{\,\textrm{alph}\,}}(w),E)\), \(\texttt {a},\texttt {b}\in {{\,\textrm{alph}\,}}(w)\) with \(\texttt {a}\ne \texttt {b}\), and \(u=\pi _{\{\texttt {a},\texttt {b}\}}(w)\). Let k be the number of circular squares in u.

1. If \(k=0\), \(I_w(\{\texttt {a},\texttt {b}\})=[|w|]\) holds.

2. If \(k=1\), there exist \(n,m\in [|w|]\) with \(w[n]=w[m]\) and either \(\pi _{\{\texttt {a},\texttt {b}\}}(w[n..m])=w[n]w[m]\) or \(\pi _{\{\texttt {a},\texttt {b}\}}(w[n..|w|]w[1..m])=w[n]w[m]\). In the former case \(I_w(\{\texttt {a},\texttt {b}\})=[n,m-1]\) holds, else \(I_w(\{\texttt {a},\texttt {b}\})=[n,|w|]\cup [1,m-1]\).

3. If \(k>1\), \(I_w(\{\texttt {a},\texttt {b}\})=\emptyset \) holds.

Proof

If \(k=0\), there is no circular square in u. Thus, there is an edge \(\{\texttt {a},\texttt {b}\}\) in every graph represented by a conjugate of w, i.e., we have \(I_w(\{\texttt {a},\texttt {b}\})=[|w|]\).

Let \(k=1\). Because there is a circular square in u, we can choose n, m such that \(w[n]=w[m]\) and either

$$\begin{aligned} \pi _{\{\texttt {a},\texttt {b}\}}(w[n..m])=w[n]w[m]\quad \text{ or }\quad \pi _{\{\texttt {a},\texttt {b}\}}(w[n..|w|]w[1..m])=w[n]w[m] \end{aligned}$$

holds. Let \(i \in [|w|]\) and define \(w'=w[i+1..|w|]w[1..i]\) and \(u'=\pi _{\{\texttt {a},\texttt {b}\}}(w')\). First, assume \(\pi _{\{\texttt {a},\texttt {b}\}}(w[n..m])=w[n]w[m]\). If \(i \in [n,m-1]\), we have \(u'[|u'|]=u'[1]\) and thus, there is no letter square in \(u'\). This means \(\{\texttt {a},\texttt {b}\} \in E(G(w'))\). If \(i \in [|w|] {\setminus } [n,m-1]\), there is a letter square in \(u'\). This means \(\{\texttt {a},\texttt {b}\} \notin E(G(w'))\). It follows \(I_w(\{\texttt {a},\texttt {b}\})=[n,m-1]\). Now, assume \(\pi _{\{\texttt {a},\texttt {b}\}}(w[n..|w|]w[1..m])=w[n]w[m]\). If \(i \in [n,|w|]\cup [1,m-1]\), we have \(u'[|u'|]=u'[1]\) and thus, there is no letter square in \(u'\). This means \(\{\texttt {a},\texttt {b}\} \in E(G(w'))\). If \(i \in [|w|] {\setminus } ([n,|w|]\cup [1,m-1])\), there is a letter square in \(u'\). This means \(\{\texttt {a},\texttt {b}\} \notin E(G(w'))\). It follows \(I_w(\{\texttt {a},\texttt {b}\})=[n,|w|]\cup [1,m-1]\).

Lastly, let \(k>1\). Since there is more than one circular square in u, there is no edge \(\{\texttt {a},\texttt {b}\}\) in every graph represented by a conjugate of w. Thus, we have \(I_w(\{\texttt {a},\texttt {b}\})=\emptyset \). \(\square \)

Since every word representing the complete graph with two nodes has every edge and anti-edge as an optional edge, we investigate complete graphs in more detail from a word’s perspective.

Lemma 7

Every word w representing a complete graph with n nodes is of the form \((w[1]\ldots w[n])^kw[1]\ldots w[|w| {{\,\textrm{mod}\,}}n]\) for some \(k \in {\mathbb {N}}\).

Proof

Let \(G=(V,E)\) be a complete graph with \(|V|=n\) and \(w \in V^{*}\) representing G. This implies immediately \(|w|\ge n\). Let \(i \in [n]\). Because w[i] has an edge to every other vertex, w[i] alternates with every other letter in w. Therefore, every other letter has to occur exactly once between any two consecutive occurrences of w[i]. It follows \(w[j]=w[j+n]\) for all \(j\in [1,|w|-n]\) and thus \((w[1]\ldots w[n])^kw[1]\ldots w[|w| {{\,\textrm{mod}\,}}n]\) for some \(k \in {\mathbb {N}}\). \(\square \)

By Lemma 7, we can present a full characterisation of the graphs that are represented by the conjugates of a word representing a complete graph.

Theorem 8

Let \(w=uv\) with \(w,u,v\in \Sigma ^{*}\) and \(|u|>0\) represent the complete graph (V, E) with n nodes. For \(m=|w| {{\,\textrm{mod}\,}}n\), vu represents \((V,E \setminus E')\) with

1. \(E'=\{\{w[i],w[j]\}\mid i\in [|u|], j \in [m+1,n]\}\) if \(|u|<m\),

2. \(E'=\{\{w[i],w[j]\}\mid i\in [m], j \in [m+1,n]\}\) if \(m\le |u| \le |w|-m\),

3. \(E'=\{\{w[i],w[j]\}\mid i\in [|u|-|w|+m+1,m], j \in [m+1,n]\}\) if \(|w|-m<|u|\).

Proof

By Lemma 7, we know that \(w=(w[1]\ldots w[n])^kw[1]\ldots w[m]\) for some \(k \in {\mathbb {N}}\). For different \(i,j \in [n]\), define \(p=\pi _{\{w[i],w[j]\}}(w)\).

Assume \(i,j \in [m]\) or \(i,j \in [m+1,n]\) with \(i<j\). We have \(p=(w[i]w[j])^{k+1}\) or \(p=(w[i]w[j])^k\), which both contain no circular square. Hence, \(\{w[i],w[j]\} \in E(G(vu))\).

Assume \(i \in [m], j \in [m+1,n]\). We have \(p=(w[i]w[j])^kw[i]\) and thus exactly one circular square in p. We also have \(w[|w|-m+i]=w[i]\) and \(\pi _{\{w[i],w[j]\}}(w[|w|-m+i..|w|]w[1..i])=w[|w|-m+i]w[i]\). By Theorem 6, this means \(I_w(\{w[i],w[j]\})=[|w|-m+i,|w|]\cup [1,i-1]\).

1. If \(|u|<m\), \(|u| \notin I_w(\{w[i],w[j]\})\) iff \(i \in [|u|]\).

2. If \(m\le |u|\le |w|-m\), \(|u| \notin I_w(\{w[i],w[j]\})\).

3. If \(|w|-m <|u|\), \(|u| \notin I_w(\{w[i],w[j]\})\) iff \(i \in [|u|-|w|+m+1,m]\).

The claim follows by the definition of \(I_w\). \(\square \)

Due to Theorem 6, we can construct an efficient algorithm to compute \(I_w\). It uses a matrix C to save indices of possible circular squares and an array \({{\,\textrm{first}\,}}\) to save each letter’s first occurrence. This is needed to detect circular squares in the projection that are not letter squares.

Proposition 9

Let \(w\in \Sigma ^{*}\). \(I_w\) can be computed in \(O(|{{\,\textrm{alph}\,}}(w)||w|)\) time.

Proof

We start by initialising \(I_w(\{\texttt {a},\texttt {b}\})\) with [1, n], a matrix C with \(C[\texttt {a}][\texttt {b}]=-1\), and an array \({{\,\textrm{first}\,}}\) with \({{\,\textrm{first}\,}}[\texttt {a}]=-1\) for every \(\texttt {a},\texttt {b}\in {{\,\textrm{alph}\,}}(w)\) with \(\texttt {a}\ne \texttt {b}\). Then, we traverse w from left to right. Doing so, we save the position of each letter’s first occurrence in \({{\,\textrm{first}\,}}\), and for every \(i \in [|w|]\) we iterate over all other letters \(\texttt {b}\in {{\,\textrm{alph}\,}}(w) {\setminus } \{w[i]\}\). Let \(w[i]=\texttt {a}\). If \(C[\texttt {a}][\texttt {b}] \ne -1\), we check \(I_w(\{\texttt {a},\texttt {b}\})\). If \(I_w(\{\texttt {a},\texttt {b}\})=[1,n]\), we set \(I_w(\{\texttt {a},\texttt {b}\})=[C[\texttt {a}][\texttt {b}],i-1]\), else \(I_w(\{\texttt {a},\texttt {b}\})=\emptyset \). We set \(C[\texttt {a}][\texttt {b}]=i\) and \(C[\texttt {b}][\texttt {a}]=-1\) for every \(\texttt {b}\in {{\,\textrm{alph}\,}}(w) \setminus \{\texttt {a}\}\). After traversing w, we iterate over all \(\texttt {a}\in {{\,\textrm{alph}\,}}(w)\) and \(\texttt {b}\in {{\,\textrm{alph}\,}}(w) {\setminus } \{\texttt {a}\}\). If \(C[\texttt {a}][\texttt {b}] \ne -1\) and \({{\,\textrm{first}\,}}[\texttt {a}]<{{\,\textrm{first}\,}}[\texttt {b}]\), we check \(I_w(\{\texttt {a},\texttt {b}\})\). If \(I_w(\{\texttt {a},\texttt {b}\})=[1,n]\), we set \(I_w(\{\texttt {a},\texttt {b}\})=[C[\texttt {a}][\texttt {b}],|w|]\cup [1,i-1]\), else \(I_w(\{\texttt {a},\texttt {b}\})=\emptyset \). Altogether, this yields a run time in \(O(|{{\,\textrm{alph}\,}}(w)||w|)\). The correctness of the algorithm is implied by Theorem 6. \(\square \)

We conclude this section by presenting an algorithm for efficient computation of the graphs represented by a word’s conjugates.

Proposition 10

Let \(w=\texttt {a}w'\) with \(\texttt {a}\in \Sigma \) and \(w' \in \Sigma ^{*}\) represent the graph \(G=({{\,\textrm{alph}\,}}(w),E)\). \(G(w'\texttt {a})\) is computable in \(O(|{{\,\textrm{alph}\,}}(w)|)\) time given G and \(I_w\).

Proof

We have \(1 \in I_w(\{\texttt {a},\texttt {b}\})\) iff \(\{\texttt {a},\texttt {b}\}\) is an edge in \(G(w'\texttt {a})\). Only the edges \(\{\texttt {a},\texttt {b}\}\) with \(\texttt {b}\in {{\,\textrm{alph}\,}}(w){\setminus } \{\texttt {a}\}\) can differ between G and \(G(w'\texttt {a})\). Hence, we get \(E(G(w'\texttt {a}))\) by adding all \(\{\texttt {a},\texttt {b}\}\) with \(1 \in I_w(\{\texttt {a},\texttt {b}\})\) to E and removing all \(\{\texttt {a},\texttt {b}\}\) with \(1 \notin I_w(\{\texttt {a},\texttt {b}\})\) from E. This takes \(O({{\,\textrm{alph}\,}}(w))\) time. \(\square \)

It suffices to calculate \(I_w\) from Proposition 10 once for all conjugates. However, after the computation of a conjugate’s graph, \(I_w\) needs to be updated by reducing every entry by 1. This can be avoided by using an offset, which is applied to every entry. Since the computation of \(I_w\) takes \(O(|{{\,\textrm{alph}\,}}(w)||w|)\) time according to Proposition 9, we obtain the following theorem, which applies Proposition 10\(|w|-1\) times for a given \(w\in \Sigma ^{*}\) using an offset to update \(I_w\).

Theorem 11

Given \(w\in \Sigma ^{*}\) and G(w), all graphs represented by w’s conjugates can be computed in time \(O(|{{\,\textrm{alph}\,}}(w)||w|)\).

5 Graphs represented by k-local Words

In this section, we investigate the graphs represented by k-local words. The notion of k-locality was introduced in [7] in the context of pattern matching and further investigated on words in [9]. Here, we connect 1-local words with comparability graphs. Before we introduce the notion of k-locality and show that each graph represented by a k-local word is 2k-representable, we have a look at graphs represented by palindromes. Palindromes play an important role in 1-locality [7]. As a first result, we show that two letters in a palindrome can only alternate if one of them is in the palindrome’s centre, which is at \(\lceil \frac{1}{2}|w|\rceil \), implying that every non-empty palindrome represents an extended star graph.

Lemma 12

Let \(w\in \Sigma ^+\) be a palindrome and \(k=\lceil \frac{1}{2}|w|\rceil \). If \(\texttt {a},\texttt {b}\in \Sigma \) alternate in w, then \(w[k]\in \{\texttt {a},\texttt {b}\}\).

Proof

Let \(\texttt {a},\texttt {b}\in {{\,\textrm{alph}\,}}(w)\) with \(\texttt {a}\ne w[k] \ne \texttt {b}\). Then, either \(\texttt {a}^2\) or \(\texttt {b}^2\) is a factor of \(\pi _{\{\texttt {a},\texttt {b}\}}(w)\) since w is a palindrome. Thus, \(\texttt {a}\) and \(\texttt {b}\) do not alternate in w. \(\square \)

This implies that there are no alternating letters in words of even length.

Proposition 13

Let \(w\in \Sigma ^+\) be a palindrome, \(U\subseteq \Sigma \) be the set of letters alternating with w[k] for \(k=\lceil \frac{1}{2}|w|\rceil \), and let \(G=({{\,\textrm{alph}\,}}(w),E)\) be the graph represented by w. Then, \((U \dot{\cup } \{w[k]\},E)\) is a star graph with centre w[k].

Proof

\((U\dot{\cup } \{w[k]\},\{\{w[k],v\}\mid v \in U\})\) is a star graph with centre w[k]. According to Lemma 12, \(E=\{\{w[k],v\}\mid v \in U\}\) holds, because no other letters can alternate in w. \(\square \)

The next proposition characterises the palindromes representing star graphs.

Proposition 14

Let G be a star graph with centre \(\texttt {c}\) and vertex set \(U \dot{\cup } \{\texttt {c}\}\) for \(|U|>1\). The palindromes representing G are exactly the words

$$\begin{aligned} sw_{n-1}\texttt {c}...w_1\texttt {c}w_0 \texttt {c}(w_0)^R(w_1\texttt {c})^R...(w_{n-1}\texttt {c})^Rs^R \end{aligned}$$

with \(n\in {\mathbb {N}}\), \(w_0,...,w_n \in U^{*}\) 1-uniform, and \(s \in (U \dot{\cup } \{\texttt {c}\})^{*}\) being a suffix of \(w_n\texttt {c}\).

Proof

Let \(w_0,...,w_n \in U^{*}\) be 1-uniform for some \(n \in {\mathbb {N}}\), and let \(s \in (U \dot{\cup } \{\texttt {c}\})^{*}\) be a suffix of \(w_nc\). Define the palindrome

$$\begin{aligned} w=sw_{n-1}\texttt {c}...w_1\texttt {c}w_0 \texttt {c}(w_0)^R(w_1\texttt {c})^R...(w_{n-1}\texttt {c})^Rs^R. \end{aligned}$$

For all \(\texttt {a}\in U\), there is an occurrence of \(\texttt {c}\) between every two occurrences of \(\texttt {a}\) and an occurrence of \(\texttt {a}\) between every two occurrences of \(\texttt {c}\). Thus, U is the set of letters alternating with \(\texttt {c}\) in w. According to Proposition 13, w represents a star graph with centre \(\texttt {c}\) and vertex set \(U \dot{\cup } \{\texttt {c}\}\).

For the other direction, let \(w \in (U \dot{\cup } \{\texttt {c}\})^*\) be a palindrome representing G. We know \({{\,\textrm{alph}\,}}(w)=U \dot{\cup } \{\texttt {c}\}\). Because G is a star graph with centre \(\texttt {c}\), U is the set of letters alternating with \(\texttt {c}\) in w. Thus, between two subsequent occurrences of \(\texttt {c}\) in w every letter in U needs to occur exactly once. Since multiple letters alternate with \(\texttt {c}\) in w, we know \(w[k]=\texttt {c}\) for \(k=\lceil \frac{1}{2}|w|\rceil \) due to Lemma 12. Hence, w has to be of the claimed form, which finishes the proof. \(\square \)

Applying Proposition 13, we can characterise when two palindromes represent the same graph. As expected, the centres of the palindromes play the key role.

Proposition 15

Let \(w_1,w_2 \in \Sigma ^+\) be palindromes with \({{\,\textrm{alph}\,}}(w_1)={{\,\textrm{alph}\,}}(w_2)\). Let \(U_1,U_2\) be the sets of letters alternating wih \(w_1[k_1]\) and \(w_2[k_2]\) for \(k_1=\lceil \frac{1}{2}|w_1|\rceil \) and \(k_2=\lceil \frac{1}{2}|w_2|\rceil \). The words \(w_1\) and \(w_2\) represent the same graph iff

1. \(U_1=U_2\) and \(w_1[k_1]=w_2[k_2]\) or

2. \(U_1=\{w_2[k_2]\}\) and \(U_2=\{w_1[k_1]\}\) or

3. \(U_1=U_2=\emptyset \).

Proof

Let \(G=(V,E)\) be a graph represented by \(w_1\) and \(w_2\). Due to Proposition 13, we know that \(S_1=(U_1 \dot{\cup } \{w_1[k_1]\},E)\) is a star graph with centre \(w_1[k_1]\), and \(S_2=(U_2 \dot{\cup } \{w_2[k_2]\},E)\) is a star graph with centre \(w_2[k_2]\). Assume \(|U_1|>0\). Since the graphs’ edge sets are equal and there are no vertices without edges, \(S_1=S_2\) holds. Thus, if \(|U_1|>1\), 1. holds, and if \(|U_1|=1\), either 1. or 2. holds. If \(|U_1|=0\), no letters alternate in \(w_1\), and we have \(E=\emptyset \). It follows \(|U_2|=0\) proving the claim.

For the other direction, first assume 1. holds. The claim follows by Proposition 13. Now, assume 2. holds. By Proposition 13, \(w_1\) and \(w_2\) represent extended star graphs \(G_1\) and \(G_2\) containing star graphs \(S_1=(U_1\dot{\cup } \{w_1[k_1]\},\{\{w_1[k_1],v\}\mid v \in U_1\})\) and \(S_2=(U_2\dot{\cup } \{w_2[k_2]\},\{\{w_2[k_2],v\}\mid v \in U_2\})\). We have

$$\begin{aligned} S_1=(\{w_1[k_1],w_2[k_2]\},\{\{w_1[k_1],w_2[k_2]\}\})=S_2. \end{aligned}$$

It follows \(G_1=G_2\). If 3. holds, \(w_1\) and \(w_2\) represent the graph \(({{\,\textrm{alph}\,}}(w_1),\emptyset )\). \(\square \)

Theorem 16

Non-empty palindromes represent exactly extended star graphs.

Proof

Let \(G=(V \dot{\cup } U,E)\) with \(V=\{z_1,...,z_n\}\) be an extended star graph such that (U, E) is a star graph. Applying Proposition 14, we can construct a palindrome u representing (U, E). Define the palindrome \(w = z_1^2\cdots z_n^2uz_n^2\cdots z_1^2\) representing a graph \((V \dot{\cup } U,E')\). For every \(i \in [n]\), \(z_i^2\) is a factor of w, and thus, \(z_i\) does not have any edges in G. This means \(E=E'\), proving the claim.

The other direction directly follows from Proposition 13. \(\square \)

Now, we are investigating the graphs represented by k-local words. Before we introduce these words formally, we give an example to give an understanding. Consider \(w=\texttt {banana}\) and the enumeration \(s=(\texttt {b},\texttt {a},\texttt {n})\). Now, we mark letters: in a first step, we mark all occurrences of \(\texttt {b}\) and obtain \({\overline{\texttt {b}}}{} \texttt {anana}\). We call a consecutive factor of marked letters a block, and thus, we have one marked block. Now, we mark all occurrences of \(\texttt {a}\), resulting in \({\overline{\texttt {ba}}}{} \texttt {n}\overline{\texttt {a}}{} \texttt {n}\overline{\texttt {a}}\) having three marked blocks. In the last step, we mark the occurrences of \(\texttt {n}\) and get with \({\overline{\texttt {banana}}}\) one marked block. Since the highest number of marked blocks we saw is 3, we say that w is 3-local. Notice that \(\texttt {banana}\) is also 2-local, witnessed by \((\texttt {n},\texttt {a},\texttt {b})\). Now, we introduce these notions formally.

Definition 7

Let \({\overline{\Sigma }} = \{{\overline{x}} \mid x \in \Sigma \}\) be the set of marked letters. For a word \(w \in \Sigma ^*\), a marking sequence of the letters occurring in w is an enumeration \(s=(x_1, x_2,..., x_{|{{\,\textrm{alph}\,}}(w)|})\) of \({{\,\textrm{alph}\,}}(w)\). A letter \(x_i\) is called marked at stage \(k \in {\mathbb {N}}\) if \(i \le k\). Moreover, we define \(w_k\), the marked version of w at stage k, as the word obtained from w by replacing all \(x_i\) with \(i \le k\) by \(\overline{x_i}\). A factor of \(w_k\) is a marked block if it only contains elements from \({\overline{\Sigma }}\) and the letters to the left and right (if existing) are from \(\Sigma \). A word \(w \in \Sigma ^*\) is k-local for \(k\in {\mathbb {N}}_0\) if there exists a marking sequence \((x_1,..., x_{|{{\,\textrm{alph}\,}}(w)|})\) of \({{\,\textrm{alph}\,}}(w)\) such that for all \(i \le | {{\,\textrm{alph}\,}}(w)|\), we have that \(w_i\) has at most k marked blocks. A word is called strictly k-local if it is k-local but not \((k-1)\)-local.

Before we present the results on the graphs represented by k-local words, we need a property of k-local words.

Lemma 17

Let \(w\in \Sigma ^{*}\) be k-local with \(|w|_{\texttt {a}}>2k\) for some \(\texttt {a}\in \Sigma \) and \(k\in {\mathbb {N}}\). Then, \(\texttt {a}\texttt {a}\in {{\,\textrm{Fact}\,}}(w)\).

Proof

By [7, Lemma 5], we know that w contains at most 2k \(\texttt {a}\)-blocks. If all blocks were just a single \(\texttt {a}\), we would have \(|w|_\texttt {a}\le 2k\), contradicting the assumptions. Thus, we have that \(\texttt {a}\texttt {a}\) is a factor of w. \(\square \)

Our first results about k-local words connect k-locality and k-representability.

Proposition 18

For a given \(k\in {\mathbb {N}}\), a graph represented by a k-local word is 2k-representable.

Proof

Let \(G=(V,E)\) be representable by a k-local word w. Consider \({{\,\textrm{sep}\,}}(w)\). Each letter in w with \(\texttt {a}\texttt {a}\not \in {{\,\textrm{Fact}\,}}(w)\) occurs at most 2k times in w and thus in \({{\,\textrm{sep}\,}}(w)\) by Lemma 17. Each letter in w with \(\texttt {a}\texttt {a}\in {{\,\textrm{Fact}\,}}(w)\) occurs exactly twice in \({{\,\textrm{sep}\,}}(w)\) by definition. By [20], we know that a graph represented by a word with no letter occurring more than 2k times is 2k-representable. Since w and \({{\,\textrm{sep}\,}}(w)\) both represent G, G is 2k-representable. \(\square \)

Corollary 19

There is no k such that every word-representable graph can be represented by a k-local word.

Proof

Assume there is such k. By Proposition 18, this implies that every word-representable graph is 2k-representable. However, according to [12], there is no \(n \in {\mathbb {N}}\) such that every word-representable graph is n-representable, which is a contradiction. \(\square \)

Proposition 20

Let \(w \in \Sigma ^{*}\) with \(|{{\,\textrm{alph}\,}}(w)|>1\) be a strictly k-local word representing a graph G. There is a strictly \((k+1)\)-local word representing G.

Proof

Choose \(k=\max \{i\in [2,|w|]|w[i] \notin {{\,\textrm{Fact}\,}}(w[1..i-1])\}\). If \(\texttt {a}\in {{\,\textrm{alph}\,}}(w)\) does not alternate with w[k] in w, it neither does so in w[k]w. If \(\texttt {a}\) does alternate with w[k] in w, it also does in w[k]w since \(\pi _{\{w[k],\texttt {a}\}}(w)[1]=\texttt {a}\). Thus, w[k]w represents G. Because the number of w[k]-blocks is increased, we can repeat this until we get a strictly \((k+1)\)-local word representing G by [7]. \(\square \)

Now, we have a more detailed look into the graphs represented by 1-local words. These words have a specific palindromic-like structure shown in [7], e.g. \(\texttt {d}\texttt {c}\texttt {b}\texttt {a}\texttt {b}\texttt {d}\texttt {e}\). While in [7] they concluded that it suffices to look at the condensed form of a word (replacing every factor \(\texttt {a}^k\) by \(\texttt {a}\) for all \(\texttt {a}\in \Sigma \) and \(k>1\)), we here need to keep letter squares in the middle of the word since it indicates that we do not have an edge in the corresponding graph. Therefore, we define the notion of the 1-local normal form of a word.

Definition 8

A 1-local word \(w\in \Sigma ^{*}\) is in normal form (1l-NF) if we have either \(w=\varepsilon \) or if there exist \(\texttt {a}\in \Sigma \), \(n,m\in \{0,1\}\), and \(w'\in (\Sigma \backslash \{\texttt {a}\})^{*}\) in 1l-NF such that \(w=\texttt {a}^n w'\texttt {a}^m\).

Remark 5

Let \(w\in \Sigma ^{+}\) be in 1l-NF with a marking sequence s starting with \(\texttt {x}\in \Sigma \) witnessing the locality, i.e., \(w=w_1\texttt {x}w_2\) or \(w=w_1\texttt {x}\texttt {x}w_2\) for some \(w_1,w_2\in (\Sigma \backslash \{\texttt {x}\})^{*}\). From [9], we obtain inductively for all \(\texttt {y}\in \Sigma \backslash {{\,\textrm{alph}\,}}(w)\), that \(w_1\texttt {x}\texttt {y}\texttt {y}w_2\) or \(w_1\texttt {x}\texttt {y}\texttt {y}\texttt {x}w_2\) are also in 1l-NF. Also based on [9], we can assume \(w_1\) and \(w_2\) to be condensed, thus 1-uniform on their respective alphabets.

The following results connect 1-local words and word-representability by words in 1l-NF, leading to the main theorem of this section.

Proposition 21

Every graph representable by a 1-local word can be represented by a word in 1l-NF.

Proof

We want to show by induction that every graph representable by a 1-local word \(w\in \Sigma ^{*}\) can be represented by a word \(w'\) in 1l-NF such that \(|w|_\texttt {b}=1\) iff \(|w'|_\texttt {b}=1\) for every letter \(\texttt {b}\in \Sigma \). The base case is the empty graph, for which the statement holds. Let G be represented by a 1-local word \(w \in \Sigma ^{*}\). Since w is 1-local, by [7] there exist \(\texttt {a}\in \Sigma \), \(n,m\in {\mathbb {N}}_0\), and \(w_2\in (\Sigma {\setminus }\{\texttt {a}\})^{*}\) such that \(w=\texttt {a}^nw_2\texttt {a}^m\). Let by induction \(w_3\in (\Sigma \setminus \{\texttt {a}\})^{*}\) in 1l-NF represent the same graph as \(w_2\) with \(|w_2|_\texttt {b}=1\) iff \(|w_3|_\texttt {b}=1\) for every letter \(\texttt {b}\in \Sigma \).

If \(n,m \le 1\), \(\texttt {a}^nw_3\texttt {a}^m\) is in 1l-NF. Because \(|w_2|_\texttt {b}=1\) iff \(|w_3|_\texttt {b}=1\) for every letter \(\texttt {b}\in \Sigma \), \(\texttt {a}\) alternates with the same letters in w and \(\texttt {a}^nw_3\texttt {a}^m\). Thus, \(\texttt {a}^nw_3\texttt {a}^m\) represents G. Since \(|w_2|_\texttt {a}=|w_3|_\texttt {a}=0\), we have \(|w|_\texttt {a}=1\) iff \(|\texttt {a}^nw_3\texttt {a}^m|_\texttt {a}=1\) and thus \(|w|_\texttt {b}=1\) iff \(|\texttt {a}^nw_3\texttt {a}^m|_\texttt {b}=1\) for every \(\texttt {b}\in \Sigma \).

Otherwise if \(n>1\) or \(m>1\), \(\texttt {a}\) does not alternate with any letter in w. Then, by Remark 5, there exist \(u,v\in (\Sigma {\setminus } \{x\})^{*}\) and \(\texttt {x}\in \Sigma \) such that \(w_3=u\texttt {x}v\) or \(w_3=u\texttt {x}\texttt {x}v\). If \(w_3=u\texttt {x}v\), define \(w_4=u\texttt {x}\texttt {a}\texttt {a}v\), otherwise \(w_4=u\texttt {x}\texttt {a}\texttt {a}\texttt {x}v\). Also by Remark 5, \(w_4\) is in 1l-NF. Notice that \(\texttt {a}\) does not alternate with any letter in \(w_4\). Thus, \(w_4\) represents G. We have \(|w|_\texttt {a}=1\) iff \(|w_4|_\texttt {a}=1\). It follows \(|w|_\texttt {b}=1\) iff \(|w_4|_\texttt {b}=1\) for every \(\texttt {b}\in \Sigma \). \(\square \)

Lemma 22

Let \(w=w_1\texttt {a}w_2\texttt {a}w_3\in \Sigma ^+\) with \(\texttt {a}\in \Sigma \), \(w_1,w_2,w_3\in (\Sigma \backslash \{\texttt {a}\})^{*}\). If \(w_1w_3\) represents \(G=(V,E)\) and \(w_1\) and \(w_3\) are 1-uniform, then \(w_1\texttt {a}\texttt {a}w_3\) represents \((V \cup \{\texttt {a}\},E)\) and \(w_1\texttt {a}\) and \(\texttt {a}w_3\) are 1-uniform.

Proof

Let \(w_1w_3\) represent \(G=(V,E)\) with \(w_1\) and \(w_3\) being 1-uniform. Since \(\texttt {a}\) does not alternate with any letter in \(w_1 \texttt {a}\texttt {a}w_3\), \(w_1\texttt {a}\texttt {a}w_3\) represents \((V\cup \{\texttt {a}\},E)\). Also, since \(\texttt {a}\not \in {{\,\textrm{alph}\,}}(w_1w_3)\), \(w_1 \texttt {a}\) and \(\texttt {a}w_3\) are 1-uniform. \(\square \)

Lemma 23

Let \(w\in \Sigma ^{*}\) be 1-local with \(w=w_1\texttt {a}w_2w_3\) or \(w=w_1w_2\texttt {a}w_3\) for a letter \(\texttt {a}\in \Sigma \) and \(w_1,w_2,w_3\in (\Sigma \backslash \{\texttt {a}\})^{*}\). If \(w_1w_3\) represents \(G=(V,E)\) and \(w_1\) and \(w_3\) are 1-uniform, then \(w_1\texttt {a}w_3\) represents \((V \cup \{\texttt {a}\},E \cup \{ \{\texttt {a},v\}\mid v \in V \})\) and \(w_1\texttt {a}\) and \(\texttt {a}w_3\) are 1-uniform.

Proof

Let \(w_1w_3\) represent \(G=(V,E)\) with \(w_1\) and \(w_3\) being 1-uniform. Since \(\texttt {a}\not \in {{\,\textrm{alph}\,}}(w_1w_3)\), \(w_1\texttt {a}\) and \(\texttt {a}w_3\) are 1-uniform. Since every letter in V appears at most once on each side of \(\texttt {a}\) in \(w_1\texttt {a}w_3\), \(\texttt {a}\) alternates with all of them. Thus, \(w_1\texttt {a}w_3\) represents \((V \cup \{\texttt {a}\},E \cup \{ \{\texttt {a},v\}\mid v \in V \})\). \(\square \)

We finish this section with a characterisation of the graphs represented by 1-local words. Therefore, we define the notion of 1-local-representable graphs.

Definition 9

We inductively define 1-local-representable graphs as follows: the empty graph is 1-local-representable, and if (V, E) is 1-local-representable, then \((V\cup \{x\},E)\) and \((V\cup \{x\},E \cup \{\{x,v\}\mid v \in V\})\) are both 1-local-representable.

Theorem 24

1-local words represent exactly the 1-local-representable graphs.

Proof

Let \(w_1\in \Sigma ^{*}\) be a 1-local word representing the graph G. By Proposition 21, there is a word \(w_2\in ({{\,\textrm{alph}\,}}(w_1))^{*}\) in 1l-NF representing G. Thus, there exist a letter \(\texttt {a}\in {{\,\textrm{alph}\,}}(w_1)\) and a word \(w_3\in ({{\,\textrm{alph}\,}}(w_1)\backslash \{\texttt {a}\})^{*}\) in 1l-NF such that \( w_2\in \{\varepsilon ,\texttt {a}w_3\texttt {a},\texttt {a}w_3,w_3\texttt {a}\}\). Note that \(\varepsilon \) represents the empty graph, which is by definition 1-local-representable. Now, we can inductively apply Lemmas 22 and 23 and get that \(w_2\) represents a 1-local-representable graph.

For the other direction, let G be a 1-local-representable graph. In this part of the proof, we use \(\texttt {a}\circ s=(\texttt {a},s_1,\ldots ,s_r)\) for some letter \(\texttt {a}\in \Sigma \) and a sequence of letters \(s=(s_1,\ldots ,s_r)\) for some \(r\in {\mathbb {N}}\). If G is empty, it is represented by the 1-local empty word. Otherwise, there are a 1-local-representable graph (V, E) and \(\texttt {a}\) such that either \(G=(V\dot{\cup } \{\texttt {a}\},E)\) or \(G=(V\dot{\cup } \{\texttt {a}\},E \dot{\cup } \{\{\texttt {a},v\}\mid v \in V\})\). We can assume by induction that there is a 1-local word \(w \in V^{*}\) in 1l-NF that represents (V, E) and has a minimal marking sequence s starting with the letter \(\texttt {x}\). There are 1-uniform words \(w_1,w_2 \in (V {\setminus } \{x\})^{*}\) such that \(w=w_1\texttt {x}w_2\) or \(w=w_1\texttt {x}\texttt {x}w_2\). Consider first \(G=(V \dot{\cup } \{\texttt {a}\},E)\). If \(w=w_1\texttt {x}w_2\), then \(w_1\texttt {x}\texttt {a}\texttt {a}w_2\) represents G, since \(\texttt {a}\) does not alternate with any letter in this word. If \(w=w_1xxw_2\), \(w_1\texttt {x}\texttt {a}\texttt {a}\texttt {x}w_2\) represents G for the same reason. For both words \(\texttt {a}\circ s\) is a marking sequence witnessing the 1-locality. Secondly, consider \(G=(V\dot{\cup } \{\texttt {a}\},E \dot{\cup } \{\{\texttt {a},v\}\mid v \in V\})\). If \(w=w_1\texttt {x}w_2\), then \(w_1\texttt {x}\texttt {a}w_2\) represents G, since \(w_1, w_2\) are 1-uniform and \(\texttt {a}\) alternates with every letter in the word. Analogously, if \(w=w_1\texttt {x}\texttt {x}w_2\), then \(w_1\texttt {x}\texttt {a}\texttt {x}w_2\) represents G. Again, \(\texttt {a}\circ s\) is a witness for the 1-locality. \(\square \)

Corollary 25

Every 1-local-representable graph is a comparability graph.

Proof

If \(G=(V,E)\) is 1-local-representable, then \((V\cup \{x\},E \cup \{\{x,v\}\mid v \in V\})\) is also 1-local-representable and thus word-representable. The claim follows from [20]. \(\square \)

6 The language of a graph

In this section, we show that the language of all words representing a given graph G is regular by constructing a deterministic finite automaton accepting this language. We firstly introduce the needed notions of finite automata.

A deterministic finite automaton is a 5-tuple \(A=(Q,\Sigma ,\delta ,q_0,F)\) with a finite set of states Q, an alphabet \(\Sigma \), a transition function \(\delta : Q \times \Sigma \rightarrow Q\), an initial state \(q_0 \in Q\), and a set of accepting states \(F \subseteq Q\). A word \(w\in \Sigma ^{*}\) is accepted by A if there is a sequence of states \(q_0,q_1,q_2,...,q_{|w|}\) such that \(\delta (q_{i-1},w[i])=q_{i}\) for all \(i \in [|w|]\) and \(q_{|w|}\in F\). The language of words accepted by A is denoted by L(A). A language is regular if there is a deterministic finite automaton accepting it. We define \(\delta ^*:Q\times \Sigma ^* \rightarrow Q\) by \(\delta ^*(q,\varepsilon )=q\) and \(\delta ^*(q,\texttt {a}w')=\delta ^*(\delta (q,\texttt {a}),w')\) for \(\texttt {a}\in \Sigma \) and \(w'\in \Sigma ^*\).

In a first step, we construct a deterministic finite automaton \(A_{\{\texttt {a},\texttt {b}\}}\) accepting exactly the language of all words over \(\Sigma \) where \(\texttt {a},\texttt {b}\in \Sigma \) alternate or both occur at most once. In addition, we need a deterministic finite automaton \(A_{\texttt {a}}\) which accepts exactly the words containing an \(\texttt {a}\in \Sigma \).

Definition 10

For \(\texttt {a},\texttt {b}\in \Sigma \), define \(A_{\{\texttt {a},\texttt {b}\}}=(Q,\Sigma ,\delta ,q_0,Q\backslash \{q_3\})\) with \(Q=\{q_0,q_1,q_2,q_3\}\) as given by Fig. 7 on the left hand side with additional transitions \(\delta (q,\texttt {c})=q\) for all \(q\in Q\) and \(\texttt {c}\in \Sigma \backslash \{\texttt {a},\texttt {b}\}\). Moreover, define \(A_{\texttt {a}}=(Q',\Sigma ,\delta ',q_0',\{q_1'\})\) with \(Q'=\{q_0',q_1'\}\) as given by Fig. 7 on the right hand side with additional transitions \(\delta '(q',\texttt {c})=q'\) for all \(q'\in Q'\) and \(\texttt {c}\in \Sigma \backslash \{\texttt {a}\}\).

Fig. 7
figure 7

Left hand side: \(A_{\{\texttt {a},\texttt {b}\}}\) and \(\delta (q,\texttt {c})=q\) for all \(q\in Q\), \(\texttt {c}\in \Sigma \backslash \{\texttt {a},\texttt {b}\}\). Right hand side: \(A_{\texttt {a}}\) and \(\delta (q,\texttt {c})=q\) for all \(q\in Q'\), \(\texttt {c}\in \Sigma \backslash \{\texttt {a}\}\)

Full size image

This leads to the immediate equivalences (cf. Fig. 7).

Remark 6

Let \(w\in \Sigma ^{*}\). Then, \(w\in L(A_{\{\texttt {a},\texttt {b}\}})\) iff \(\texttt {a}\) and \(\texttt {b}\) alternate in w or both occur at most once, and \(w\in L(A_{\texttt {a}})\) iff \(\texttt {a}\in {{\,\textrm{alph}\,}}(w)\).

In the following theorem we combine these kinds of automata to construct an automaton accepting all words representing a given graph. Here, it is crucial that regular languages are closed under intersection and complement.

Theorem 26

The language of words representing a given graph is regular.

Proof

Let \(G=(V,E)\) be a graph and L the language of words representing it. Let \({\overline{E}}\) be the set of anti-edges in G. We know that \(w \in L\) iff

1. \({{\,\textrm{alph}\,}}(w)=V\),

2. \(\texttt {a}\) and \(\texttt {b}\) alternate in w for all \(\{\texttt {a},\texttt {b}\} \in E\), and

3. \(\texttt {a}\) and \(\texttt {b}\) do not alternate in w for all \(\{\texttt {a},\texttt {b}\} \in {\overline{E}}\).

Thus, we get \(w \in L\) iff

1. \(w \in L(A_{\texttt {a}})\) for all \(\texttt {a}\in V\),

2. \(w \in L(A_e)\) for all \(e \in E\), and

3. \(w \in V^* {\setminus } L(A_{e})\) for all \(e \in {\overline{E}}\).

This means \(L= \bigcap \limits _{\texttt {a}\in V} L(A_{\texttt {a}}) \cap \bigcap \limits _{e \in E} L(A_{e}) \cap \bigcap \limits _{e \in {\overline{E}}} V^* {\setminus } L(A_{e})\). Since regular languages are closed under intersection and complement, L is regular. \(\square \)

7 Conclusion

Our first result gives a geometrical characterisation of k-representability for \(k\ge 3\). For this we introduced the notion of a k-circle representation of a graph. This notion led to the investigation of the graphs represented by the conjugates of a word. Here, we were able to fully characterise the graphs by defining circular squares. We also gave an efficient algorithm which calculates all associated graphs. In a next step, we investigated the graphs represented by palindromes. Based on these results, we had a look into k-local words. For us, interestingly, representability by k-local words and k-representability are closely related. Also, we were able to characterise the graphs represented by 1-local words, which are tightly related to palindromes. This raises the hope that k-local words for an arbitrary \(k\in {\mathbb {N}}\) can also be characterised by a special form of graphs in order to understand k-local words better. Moreover, since it is proven to be NPC whether a word is k-local, fragments of these words may turn out to be determinable in P by using insights about graphs. We finished our work by showing that the language of words representing the same graph is regular. This might allow counting the number of words representing a given graph using automata theory. In future research several of our results could be transferred to generalisations of word-representable graphs.