$\lambda\colon\textsf{N}\to\textsf{Asg}(\mathcal{R},\Omega)\cup\\{\cup\\}$ is
a labeling function. For every node $\textsf{n}\in\textsf{N}$, if
$\lambda(\textsf{n})=\cup$, then both $\ell(\textsf{n})$ and $r(\textsf{n})$
are defined; if $\lambda(\textsf{n})$ is an assignment, then $r(\textsf{n})$
is not defined (i.e., $\ell(n)$ could be defined or not); and
$\lambda(\textsf{n})$ is an assignment and $\ell(n)=\bot$ iff
$\lambda(\textsf{n})$ is a valuation. Further, we assume that the directed
graph
$(\textsf{N},\\{(\textsf{n},\ell(\textsf{n})),(\textsf{n},r(\textsf{n}))\mid\textsf{n}\in\textsf{N}\\})$
is acyclic. Note that, by the previous definition, n is a bottom node in this
acyclic graph iff $\lambda(\textsf{n})$ is a valuation. We define the size of
$\mathcal{D}$ as $|\mathcal{D}|=|\textsf{N}|$.

For the analysis, it will be useful to distinguish between different type of
nodes. We will say that n is a union node (or $\cup$-node) if
$\lambda(\textsf{n})=\cup$, and an output node, otherwise. Between output
nodes, we will say that n is a _$\nu$ -node_ (or also a _bottom_ node) if
$\lambda(\textsf{n})$ is a valuation, a _$\gamma$ -node_ if
$\lambda(\textsf{n})$ is relabel, and a _$\sigma$ -node_ if neither a
valuation nor a relabel.

For each $\textsf{n}\in\textsf{N}$, we associate a bag of valuations
${\lsem{}{\mathcal{D}}\rsem}(\textsf{n})$ recursively as follows:
${\lsem{}{\mathcal{D}}\rsem}(\textsf{n})=\\{\\!\\!\\{\lambda(\textsf{n})\\}\\!\\!\\}$
whenever n is a $\nu$-node,
${\lsem{}{\mathcal{D}}\rsem}(\textsf{n})={\lsem{}{\mathcal{D}}\rsem}(\ell(\textsf{n}))\cup{\lsem{}{\mathcal{D}}\rsem}(r(\textsf{n}))$
whenever n is a union node, and
${\lsem{}{\mathcal{D}}\rsem}(\textsf{n})=\\{\\!\\!\\{\nu\circ\lambda(\textsf{n})\mid\nu\in{\lsem{}{\mathcal{D}}\rsem}(\ell(v))\\}\\!\\!\\}$
whenever $n$ is either a $\sigma$-node or a $\gamma$-node.

#### The enumeration problem

The plan is to use ECSA to encode a set of valuations of an NSST over a
string, and then enumerate the set of valuations efficiently. Specifically, we
consider the following enumeration problem:

Problem: EnumECSA Input: An ECSA
$\mathcal{D}=(\mathcal{R},\Omega,\textsf{N},\ell,r,\lambda)$ and
$\textsf{n}\in\textsf{N}$. Output: Enumerate all valuations in the bag
${\lsem{}{\mathcal{D}}\rsem}(\textsf{n})$.

As usual, we want to enumerate the set
${\lsem{}{\mathcal{D}}\rsem}(\textsf{n})$ with output-linear delay. However,
notice that we want to enumerate all valuations in
${\lsem{}{\mathcal{D}}\rsem}(\textsf{n})$, possibly with repetitions. In the
literature (see [43]), the usual goal is to enumerate the outputs without
repetitions. Nevertheless, we provide NSST with a bag semantics and,
therefore, it makes sense to enumerate all valuations with repetitions.

For solving this enumeration problem efficiently, we require to impose further
restrictions over ECSA. We call these restrictions _$k$ -bounded_ and
_garbage-free_ , respectively.

  1. 1.

We define the notion of _$k$ -bounded_ ECSA as follows. Given $\mathcal{D}$,
define the (left) output-depth of a node $\textsf{n}\in\textsf{N}$, denoted by
$\textsf{odepth}_{\mathcal{D}}(\textsf{n})$, recursively as follows:
$\textsf{odepth}_{\mathcal{D}}(\textsf{n})=0$ whenever n is a $\nu$-node or a
$\sigma$-node, and
$\textsf{odepth}_{\mathcal{D}}(\textsf{n})=\textsf{odepth}_{\mathcal{D}}(\ell(\textsf{n}))+1$
whenever $\lambda(v)$ is a union node or a $\gamma$-node. Then, for
$k\in\mathbb{N}$ we say that $\mathcal{D}$ is $k$-bounded if
$\textsf{odepth}_{\mathcal{D}}(v)\leq k$ for all $\textsf{n}\in\textsf{N}$.

  2. 2.

We say that $\mathcal{D}$ is _garbage-free_ if, for every $\sigma$-node or
$\gamma$-node n, it holds that
$\textsf{dom}(\nu)=\textsf{reg}(\lambda(\textsf{n}))$ for every
$\nu\in{\lsem{}{\mathcal{D}}\rsem}(\ell(\textsf{n}))$.

Similar as in [32], the intuition behind $k$-boundedness is that every node
has an output node close by following a constant number of left children.
Here, we have to distinguish between output nodes that are a relabel (i.e., a
$\gamma$-node) and those that are not (i.e., $\nu$\- or $\sigma$-nodes).
Intuitively, a relabel does not contribute to the size of an output;
therefore, it increases the size of the output depth in one. For this reason,
our goal will be to restrict contiguous sequences of relabels in the data
structure during node operations (see below). For the garbage-free
restriction, the intuition comes that one could have a node n that produces a
valuation $\nu\in{\lsem{}{\mathcal{D}}\rsem}(\textsf{n})$ whose content
$\nu(x)$ is not used by the parent node of n. This situation can generate
sequences of output nodes that later do not contribute to the size of an
output, increasing the delay. For this reason, garbage-free ECSA forces all
parent nodes to use all the registers of the child’s valuations, and then all
registers will contribute to the final output.

Algorithm 2 Enumeration over a node n from some garbage-free ECSA
$\mathcal{D}=(\mathcal{R},\Omega,\textsf{N},\ell,r,\lambda)$.

1:procedure enumerate(n)

2: $\iota\leftarrow\textsc{create}(\textsf{n})$

3: while $\iota.\textsc{next}=\bf{true}$ do

4: $\iota.\textsc{print}(\textsf{id})$

5:

6:$\triangleright$ $\nu$-node iterator $\iota_{\nu}$

7:procedure create(n) $\triangleright$ n is a $\nu$-node

8: $\textsf{m}\leftarrow\textsf{n}$

9: $\textsf{hasnext}\leftarrow{\bf true}$

10:

11:procedure next

12: if $\textsf{hasnext}=\bf{true}$ then

13: $\textsf{hasnext}\leftarrow\bf{false}$

14: return $\bf{true}$

15: return $\bf{false}$

16:

17:procedure print($\sigma$)

18: ${\bf print}:\lambda(\textsf{m})\circ\sigma$

19:

20:$\triangleright$ $\sigma$-node iterator $\iota_{\sigma}$

21:procedure create(n) $\triangleright$ n is a $\sigma$-node

22: $\textsf{m}\leftarrow\textsf{n}$

23: $\iota\leftarrow\textsc{create}(\ell(\textsf{m}))$

24:

25:procedure next

26: return $\iota.\textsc{next}$

27:

28:procedure print($\sigma$)

29: $\iota.\textsc{print}(\lambda(\textsf{m})\circ\sigma)$

30:$\triangleright$ Union/$\gamma$-node iterator $\iota_{\cup/\gamma}$

31:procedure create(n)

32: $\triangleright$ n is a $\cup$\- or $\gamma$-node

33: $\textsf{St}\leftarrow\text{\sf
push}(\textsf{St},(\textsf{n},\textsf{id})\,)$

34: $\textsf{St}\leftarrow\textsc{traverse}(\textsf{St})$

35: $\iota\leftarrow\textsc{create}(\text{\sf top}(\textsf{St}).\textsf{m})$

36:

37:procedure next

38: if $\iota.\textsc{next}=\bf{false}$ then

39: $\textsf{St}\leftarrow\text{\sf pop}(\textsf{St})$

40: if $\text{\sf length}(\textsf{St})=0$ then

41: return $\bf{false}$

42: else

43: $\textsf{St}\leftarrow\textsc{traverse}(\textsf{St})$

44: $\iota\leftarrow\textsc{create}(\text{\sf top}(\textsf{St}).\textsf{m})$

45: $\iota.\textsc{next}$

46: return $\bf{true}$

47:

48:procedure print($\sigma$)

49: $(\textsf{m},\gamma^{\prime})\leftarrow\text{\sf top}(\textsf{St})$

50: $\iota.\textsc{print}(\gamma^{\prime}\circ\sigma)$

51:

52:procedure traverse(St)

53: while $\text{\sf top}(\textsf{St}).\textsf{n}$ is a $\cup$\- or
$\gamma$-node do

54: $(\textsf{m},\gamma^{\prime})\leftarrow\text{\sf top}(\textsf{St})$

55: $\textsf{St}\leftarrow\text{\sf pop}(\textsf{St})$

56: if m is a $\gamma$-node then

57: $\gamma^{\prime}\leftarrow\lambda(\textsf{m})\circ\gamma^{\prime}$

58: $\textsf{St}\leftarrow\text{\sf
push}(\textsf{St},(\ell(\textsf{m}),\,\gamma^{\prime}))$

59: else

60: $\textsf{St}\leftarrow\text{\sf
push}(\textsf{St},(r(\textsf{m}),\gamma^{\prime})\,)$

61: $\textsf{St}\leftarrow\text{\sf
push}(\textsf{St},(\ell(\textsf{m}),\gamma^{\prime})\,)$

62: return St

As we show in the next proposition, if $\mathcal{D}$ is garbage-free and
$k$-bounded, then we can enumerate all valuations with output-linear delay.

######  Proposition D.1.

Assume that $k$ and $\mathcal{R}$ are fixed. Let
$\mathcal{D}=(\mathcal{R},\Omega,\textsf{N},\ell,r,\lambda)$ be a garbage-free
and $k$-bounded ECSA. Then one can enumerate the set
${\lsem{}{\mathcal{D}}\rsem}(\textsf{n})$ with output-linear delay for any
node $\textsf{n}\in\textsf{N}$.

###### Proof.

Let $\mathcal{D}=(\mathcal{R},\Omega,\textsf{N},\ell,r,\lambda)$ be a garbage-
free and $k$-bounded ECSA. We follow the same enumeration procedure for
Enumerable Compact Sets in [32, 33], adapted for our purposes. This strategy
follows a depth-first-search traversal of the data-structure, done in a
recursive fashion to ensure that after retrieving some output $u$, the next
one $u^{\prime}$ can be printed in $O(k\cdot(|u|+|u^{\prime}|))$ time. The
entire procedure is detailed in Algorithm 2.

For simplifying the presentation, we use an _iterator interface_ that, given a
node n, contains all information and methods to enumerate the outputs
${\lsem{}{\mathcal{D}}\rsem}(\textsf{n})$. Specifically, an iterator $\iota$
must implement the following three methods:

$\begin{array}[]{rclrclrcl}\textsc{create}(\textsf{n})&\\!\\!\\!\\!\rightarrow\\!\\!\\!\\!&\iota&\iota.\textsc{next}&\\!\\!\\!\\!\rightarrow\\!\\!\\!\\!&b&\iota.\textsc{print}(\sigma)&\\!\\!\\!\\!\rightarrow\\!\\!\\!\\!&\emptyset\end{array}$

where n is a node, $b$ is boolean, and $\emptyset$ means that the method does
not return an output. The first method, create, receives a node n and creates
an iterator $\iota$ of the type of n (e.g., $\nu$-node). We will implement
three types of iterators, one for $\nu$-nodes ($\iota_{\nu}$), one for
$\sigma$-nodes ($\iota_{\sigma}$), and one for $\cup$\- and $\gamma$-nodes
together ($\iota_{\cup/\gamma}$). The second method, $\iota.\textsc{next}$,
moves the iterator to the next output, returning true if, and only if, there
is an output to print. Then the last method, $\iota.\textsc{print}$, receives
any assignment $\sigma\in\textsf{Asg}(\mathcal{R},\Omega)$, and prints the
current valuation $\nu$ pointed by $\iota$ to the output registers after
composing it with $\sigma$, namely, it outputs $\nu\circ\sigma$. We assume
that one must first call $\iota.\textsc{next}$ to move to the first output
before printing. Furthermore, if $\iota.\textsc{next}$ outputs false, then the
behavior of $\iota.\textsc{print}$ is undefined. Note that one can call
$\iota.\textsc{print}$ several times, without calling $\iota.\textsc{next}$,
and the iterator will write the same output each time in the output registers.

Assume we can implement the iterator interface for each type. Then the
procedure $\textsc{Enumerate}(v)$ in Algorithm 2 (lines 1-4) shows how to
enumerate the set ${\lsem{}{\mathcal{D}}\rsem}(v)$ by using an iterator
$\iota$ for n. We assume here that id is the identity assignment, namely,
$\textsf{id}(r)=r$ for every $r\in\mathcal{R}$. In the following, we show how
to implement the iterator interface for each node type and how the size of the
next valuation bounds the delay between two outcomes.

We start by presenting the iterator $\iota_{\nu}$ for a $\nu$-node n (lines
6-18), called a _ $\nu$-node iterator_. We assume that each $\iota_{\nu}$ has
two internal values, denoted by m and hasnext, where m is a reference to n and
hasnext is a boolean variable. The purpose of a bottom node iterator is only
to print $\lambda(\textsf{n})\circ\sigma$ for some assignment $\sigma$.
Towards this goal, when we create $\iota_{\nu}$, we initialize m equal to n
and $\textsf{hasnext}={\bf true}$ (lines 8-9). When
$\iota_{\nu}.\textsc{next}$ is called for the first time, we swap hasnext from
true to false and output true (i.e., there is one output ready to be
returned). Then any following call to $\iota_{\nu}.\textsc{next}$ will be
false (line 15). Finally, the $\iota_{\nu}.\textsc{print}$ writes
$\lambda(\textsf{m})\circ\sigma$ to the output registers (lines 17-18).

For a $\sigma$-node, we present a _$\sigma$ -node iterator_ $\iota_{\sigma}$
in Algorithm 2 (lines 20-29). This iterator receives a $\sigma$-node n and
stores a reference of n, called m, and an iterator $\iota$ for iterating
through the valuations of $\ell(\textsf{n})$ (i.e.,
${\lsem{}{\mathcal{D}}\rsem}(\ell(n))$). The create method initializes m with
n and creates the iterator $\iota$ (lines 21-23). The purpose of
$\iota_{\sigma}.\textsc{next}$ is just to iterate over all outputs of
$\ell(\textsf{m})$ (lines 25-26). Then, for printing, we recursively call the
printing method of $\iota$ given as a parameter the compose assignment
$\lambda(\textsf{m})\circ\sigma$ (lines 28-29).

The most involved case is the _union/ $\gamma$-node iterator_
$\iota_{\cup/\gamma}$ (lines 30-50). This iterator receives either a union
node, or a $\gamma$-node. It keeps a _stack_ St and an iterator $\iota$. The
elements in the stack are pairs $(\textsf{m},\gamma^{\prime})$ where m is a
node and $\gamma^{\prime}$ is a relabel. We assume the standard implementation
of a stack with the native methods push, pop, top, and length: the first three
define the standard operations over stacks, and length counts the elements in
a stack. The purpose of the stack is to perform a _depth-first-search_
traversal of all union and $\gamma$-nodes below the input node n, reaching all
possible output nodes m such that there is a path of only union and
$\gamma$-nodes between n and m. At every point, if an element
$(\textsf{m},\gamma^{\prime})$ is in the stack, then $\gamma^{\prime}$ is
equal to the composition of all $\gamma$-nodes in the path from n to m. If the
top node of St is a pair $(\textsf{m},\gamma^{\prime})$ such that m is a non-
relabeling node, then $\iota$ is an iterator for m, which enumerates all their
valuations. If $p=(\textsf{m},\gamma^{\prime})$, we will use the notation
$p.\textsf{m}$ to refer to m.

To perform the _depth-first-search_ traversal of $\cup$\- and $\gamma$-nodes,
we use the auxiliary method called $\textsc{traverse}(\textsf{St})$ (lines
52-62). While the node m at the top of St is a $\cup$\- or $\gamma$-node, we
pop the top pair $(\textsf{m},\gamma^{\prime})$ from St. If m is a
$\gamma$-node (lines 56-58), we push the pair
$(\ell(\textsf{m}),\lambda(\textsf{m})\circ\gamma^{\prime})$ in the stack,
namely, we move to the next node and compose the old relabel $\gamma^{\prime}$
with the current relabel $\lambda(\textsf{m})$. Otherwise, if m is a union
node (lines 59-61), we first push the right pair
$(r(\textsf{m}),\gamma^{\prime})$ followed by the left pair
$(\ell(\textsf{m}),\gamma^{\prime})$ into the stack. The while-loop will
eventually reach a $\nu$\- or $\sigma$-node at the top of the stack and end.
It is important to note that $\textsc{traverse}(\textsf{St})$ takes
$\mathcal{O}(k)$ steps, given that the ECSA is $k$-bounded. Then if $k$ is
fixed, the traverse procedure takes constant time (assuming that
$|\mathcal{R}|$ is fixed).

The methods of a union/$\gamma$ node iterator $\iota_{\cup/\gamma}$ are then
straightforward. For create (lines 31-35), we push $(\textsf{n},\textsf{id})$
to the top of the stack (recall that id is the identity assignment) and then
$\textsc{Traverse}(\textsf{St})$, finding the first leftmost output node from
n (lines 33-34). Then we build the iterator $\iota$ of this output node for
being ready to start enumerating their outputs (line 35). For next, we consume
all outputs by calling $\iota.\textsc{next}$ (line 38). When there are no more
outputs, we pop the top node from St and check if the stack is empty or not
(lines 39-40). If this is the case, there are no more outputs and we output
false. Otherwise, we call the Travese method for finding the leftmost $\nu$\-
or $\sigma$-node from the top of the stack (lines 42-43). When the procedure
is done, we create an iterator and move to its first valuation (lines 44-45).
For $\textsc{print}(\sigma)$, we see the pair $(\textsf{m},\gamma^{\prime})$
at the top, where we remind that $\gamma^{\prime}$ represents the composition
of all $\gamma$-nodes on the way to m (line 49), and m is assumed to be a
$\nu$\- or $\sigma$-node. Then, we call the print method of $\iota$ which is
ready to write the current valuation, and over which we compose with
$\gamma^{\prime}\circ\sigma$ (line 50).

To prove the correctness of the enumeration procedure, one can verify that
$\textsc{Enumerate}(\textsf{n})$ in Algorithm 2 enumerates all the outputs in
the set ${\lsem{}{\mathcal{D}}\rsem}(\textsf{n})$ one by one (possibly with
repetitions). To bound the delay between outputs, we need some definitions and
assumptions. First, we define the size of an assignment $\sigma$ as
$|\sigma|=\sum_{X\in\textsf{dom}(\sigma)}|\sigma(X)|$. Second, we assume that,
given two assignments $\sigma$ and $\sigma^{\prime}$, we can perform the
composition $\sigma\circ\sigma^{\prime}$ in time $O(|\mathcal{R}|)$, namely,
in constant time assuming that $\mathcal{R}$ is fixed. One can do this by
representing the concatenation of strings symbolically, and then representing
$\sigma\circ\sigma^{\prime}$ in this fashion. Then, if we want the real
representation of $\sigma\circ\sigma^{\prime}$, we can enumerate each string
$\sigma\circ\sigma^{\prime}(X)$ with constant delay, and then
$\sigma\circ\sigma^{\prime}$ in linear time in $|\sigma\circ\sigma^{\prime}|$.
This will allow us to perform a concatenation
$\sigma_{1}\circ\ldots\circ\sigma_{n}=\sigma$ in time $O(n)$ to then construct
$\sigma$ in time $O(|\sigma|)$.

Coming back to delay, the fact that $\mathcal{D}$ is $k$-bounded and garbage-
free implies that the delay is bounded by $\mathcal{O}(k\cdot|\nu_{0}|)$ if
$\nu_{0}$ is the first output, or $O(k\cdot(|\nu|+|\nu^{\prime}|))$ if $\nu$
and $\nu^{\prime}$ are the previous and next outputs, respectively.
Specifically:

  * •

$\textsc{create}(\textsf{n})$ takes time $\mathcal{O}(k\cdot|\nu_{0}|)$,

  * •

next takes time $\mathcal{O}(k\cdot|\nu_{0}|)$ for the first call, and
$\mathcal{O}(k\cdot(|\nu|+|\nu^{\prime}|))$ for the next call, and

  * •

$\textsc{print}(\textsf{id})$ takes time $\mathcal{O}(k\cdot|\nu^{\prime}|)$
where $\nu^{\prime}$ is the current output to be printed.

It is important to note that each composition operation
$\sigma\circ\sigma^{\prime}$ between two assignments in Algorithm 2 (e.g.
lines 18, 29, or 50) takes linear time in the next valuation $\nu^{\prime}$,
given the assumption above and given that $\mathcal{D}$ is garbage-free and
then all the content of $\sigma$ and $\sigma^{\prime}$ will be used in
$\nu^{\prime}$. Instead, the compositions between relabels
$\gamma\circ\gamma^{\prime}$ (e.g., line 57) take time
$O(k\cdot|\mathcal{R}|)$, which is constant and do not affect the delay for
the next output $\nu^{\prime}$. Overall, $\textsc{Enumerate}(\textsf{n})$ in
Algorithm 2 requires $O(k\cdot(|\nu|+|\nu^{\prime}|))$ delay to write the next
valuation $\nu^{\prime}$ in the output register, after printing the previous
output $\nu$.

We end by noticing that the existence of an enumeration algorithm with delay
$O(k\cdot(|\nu|+|\nu^{\prime}|))$ between any consecutive outputs $\nu$ and
$\nu^{\prime}$, implies the existence of an enumeration algorithm with output-
linear delay as defined in Section 5 (see [32, 33]). ∎

Note that the delay on the previous proposition depends on $|\mathcal{R}|$
that we assume that it is fix. For this reason, we get output-linear delay
given that we assume that $|\mathcal{R}|$ is a constant value.

$\sigma$$\textsf{s}_{1}\colon$$\sigma$$\gamma$$\textsf{s}_{2}\colon$$\cup$$\textsf{s}_{3}\colon$$\sigma$$:\\!\textsf{m}$$\cup$$\textsf{s}_{4}\colon$$\gamma$$\sigma$$:\\!\textsf{m}$$\gamma$$\textsf{s}_{5}\colon$$\cup$$\sigma$$:\\!\textsf{m}$$\gamma$$\textsf{s}_{6}\colon$$\cup$$\gamma^{\prime}$$:\\!\textsf{m}$$\sigma$
Figure 1: Nodes $\textsf{s}_{1},\ldots,\textsf{s}_{6}$ are the six possible
cases for a node to be safe, where we assume that the rounded node labeled by
m is any node such that $\textsf{odepth}_{\mathcal{D}}(\textsf{m})\leq 2$. We
use $\gamma$ and $\gamma^{\prime}$ for a relabel and $\sigma$ for a non-
relabeling assignment. Solid arrow is used for the $\ell$-edge and dashed
arrow is used for the $r$-edge. Also, $\textsf{s}_{1}$ and $\textsf{s}_{2}$
are safe output-nodes, and $\textsf{s}_{3}$ and $\textsf{s}_{4}$ are safe
union-nodes.

#### The operations

The next step is to provide a set of operations that allow extending a ECSA
$\mathcal{D}$ in a way that maintains $k$-boundedness. Fix an ECSA
$\mathcal{D}=(\mathcal{R},\Omega,\textsf{N},\ell,r,\lambda)$. For any
valuation $\nu\in\textsf{Val}(\mathcal{R},\Omega)$, any assignment
$\sigma\in\textsf{Asg}(\mathcal{R},\Omega)$, and any nodes n,
$\textsf{n}_{1}$, and $\textsf{n}_{2}$, we define the operations:

$\begin{array}[]{rclrclrcl}\textsf{add}(\nu)\\!\\!\\!&\to&\\!\\!\\!\textsf{n}^{\prime}\text{\hskip
28.45274pt}&\textsf{extend}(\textsf{n},\sigma)\\!\\!\\!&\to&\\!\\!\\!\textsf{n}^{\prime}&\text{\hskip
28.45274pt}\textsf{union}(\textsf{n}_{1},\textsf{n}_{2})\\!\\!\\!&\to&\\!\\!\\!\textsf{n}^{\prime}\end{array}$

such that
${\lsem{}{\mathcal{D}}\rsem}(\textsf{n}^{\prime}):=\\{\\!\\!\\{\nu\\}\\!\\!\\}$;
${\lsem{}{\mathcal{D}}\rsem}(\textsf{n}^{\prime}):=\\{\\!\\!\\{\nu^{\prime}\circ\sigma\mid\nu^{\prime}\in{\lsem{}{\mathcal{D}}\rsem}(\textsf{n})\\}\\!\\!\\}$;
and
${\lsem{}{\mathcal{D}}\rsem}(\textsf{n}^{\prime}):={\lsem{}{\mathcal{D}}\rsem}(\textsf{n}_{1})\cup{\lsem{}{\mathcal{D}}\rsem}(\textsf{n}_{2})$,
respectively. For extend and union we impose some prerequisites to ensure that
the results is always garbage-free. Specifically, for extend we assume that
$\textsf{dom}(\nu^{\prime})=\textsf{reg}(\sigma)$ for every
$\nu^{\prime}\in{\lsem{}{\mathcal{D}}\rsem}(\textsf{n})$ and for union we
assume that $\textsf{dom}(\nu_{1})=\textsf{dom}(\nu_{2})$ for every
$\nu_{1}\in{\lsem{}{\mathcal{D}}\rsem}(\textsf{n}_{1})$ and
$\nu_{2}\in{\lsem{}{\mathcal{D}}\rsem}(\textsf{n}_{2})$. Both restrictions
force that, if $\mathcal{D}$ is garbage-free, then the resulting ECSA after
union or extend is garbage-free as well. Finally, we suppose that these
operations extend the data structure with new nodes and that old nodes are
immutable after each operation.

Following the same recipe as in [32], we define a notion of _safe node_ for
ECSA that will aid for maintaining the $k$-boundedness property after each
operation. For the sake of presentation, we present the notion of safeness by
first introducing two additional notions, namely, safe output-node and safe
union-node. We say that an node n is a _safe output-node_ iff n is a
$\nu$-node or a $\sigma$-node, or if n is a $\gamma$-node, then
$\ell(\textsf{n})$ is a $\nu$-node or a $\sigma$-node. Instead, we say that n
is a _safe union-node_ iff n is a union, $\ell(\textsf{n})$ is a safe output-
node, and $\textsf{odepth}_{\mathcal{D}}(r(\textsf{n}))\leq 2$. Finally, we
say that s is a _safe node_ iff s is either a safe output-node, a safe union-
node, or s is a $\gamma$-node and $\ell(\textsf{s})$ is a safe union-node. In
Figure 1, we display the six possible case for a node to be safe.

The goal now is to implement add, extend, and union such that the operations
receive as input safe nodes and return safe nodes maintaining $\mathcal{D}$
$k$-bounded. For $\textsf{add}(\nu)$, we can create a fresh node
$\textsf{n}^{\prime}$ such that $\lambda(\textsf{n}^{\prime})=\nu$ and then
output $\textsf{n}^{\prime}$ who is safe. For
$\textsf{extend}(\textsf{n},\sigma)$, assume that n is safe and $\mathcal{D}$
is $k$-bounded. We have to distinguish two cases: whether $\sigma$ is a
relabel or not. If $\sigma$ is not a relabel, then create a fresh node
$\textsf{n}^{\prime}$ such that $\lambda(\textsf{n}^{\prime})=\sigma$ and
$\ell(\textsf{n}^{\prime})=\textsf{n}$. We can check that
$\textsf{n}^{\prime}$ meets the semantics of extend, $\textsf{n}^{\prime}$ is
safe, and $\mathcal{D}$ remains $k$-bounded. Instead, if $\sigma$ is a
relabel, we have to consider two more cases: whether n is a $\gamma$-node or
not. If n is not a $\gamma$-node (i.e., cases $\textsf{s}_{1}$,
$\textsf{s}_{3}$, and $\textsf{s}_{4}$ in Figure 1), then add a fresh node
$\textsf{n}^{\prime}$ such that $\lambda(\textsf{n}^{\prime})=\sigma$ and link
$\textsf{n}^{\prime}$ with n (i.e., $\ell(\textsf{n}^{\prime})=\textsf{n}$).
Otherwise, if n is a $\gamma$-node with $\lambda(\textsf{n})=\gamma$ (i.e.,
cases $\textsf{s}_{2}$, $\textsf{s}_{5}$, and $\textsf{s}_{6}$ in Figure 1),
then define the fresh node $\textsf{n}^{\prime}$ such that
$\lambda(\textsf{n}^{\prime})=\sigma\circ\gamma$, and connect
$\textsf{n}^{\prime}$ with $\ell(\textsf{n})$, namely,
$\ell(\textsf{n}^{\prime})=\ell(\textsf{n})$. One can check that in both
scenarios, $\textsf{n}^{\prime}$ is safe, it satisfies the extend-semantics,
and $\mathcal{D}$ is $k$-bounded as expected.

For $\textsf{union}(\textsf{n}_{1},\textsf{n}_{2})$, the construction is a bit
more involved. For the sake of simplification, we will only present the case
when $\textsf{n}_{1}$ and $\textsf{n}_{2}$ has the form of $\textsf{s}_{6}$
like in Figure 1. The other cases are variations or simplifications of this
case. Assume then that $\textsf{n}_{1}$ and $\textsf{n}_{2}$ have the form of
$\textsf{s}_{6}$, specifically, like in Figure 2 (left). The result of
$\textsf{union}(\textsf{n}_{1},\textsf{n}_{2})$ is the node
$\textsf{n}^{\prime}$ at Figure 2 (right). In this gadget, all nodes are fresh
nodes, except $\textsf{n}_{1}^{\prime}$, $\textsf{n}_{2}^{\prime}$,
$\textsf{m}_{1}$, and $\textsf{m}_{2}$ that are reused (i.e., seven fresh
nodes in total). First, we can easily check by inspection that
${\lsem{}{\mathcal{D}}\rsem}(\textsf{n})={\lsem{}{\mathcal{D}}\rsem}(\textsf{n}_{1})\cup{\lsem{}{\mathcal{D}}\rsem}(\textsf{n}_{2})$.
Second, $\textsf{n}^{\prime}$ is safe. Indeed, it has the form of
$\textsf{s}_{4}$ in Figure 1 since $\textsf{n}^{\prime}$ is a safe union-node
where $\ell(\textsf{n}^{\prime})$ is a safe output-node and
$\textsf{odepth}_{\mathcal{D}}(\textsf{u}_{1})\leq 2$ with
$\textsf{u}_{1}=r(\textsf{n}^{\prime})$. Finally, the resulting ECSA is
$k$-bounded if we choose $k=4$: nodes $\textsf{n}^{\prime}$ and
$\textsf{u}_{1}$ are $2$-bounded, and $\textsf{u}_{2}$ and $r(\textsf{u}_{2})$
are $4$-bounded and $3$-bounded, respectively.

$\gamma_{1}$$\textsf{n}_{1}\colon$$\cup$$\gamma_{1}^{\prime}$$:\\!\textsf{m}_{1}$$\sigma_{1}$$\textsf{n}_{1}^{\prime}\colon$$\gamma_{2}$$\textsf{n}_{2}\colon$$\cup$$\gamma_{2}^{\prime}$$:\\!\textsf{m}_{2}$$\sigma_{2}$$\textsf{n}_{2}^{\prime}\colon$$\cup$$\textsf{n}^{\prime}\colon$$\gamma_{1}^{\prime}\circ\gamma_{1}$$\sigma_{1}$$\textsf{n}_{1}^{\prime}\colon$$\cup$$\colon\\!\textsf{u}_{1}$$\gamma_{2}^{\prime}\circ\gamma_{2}$$\sigma_{2}$$\textsf{n}_{2}^{\prime}\colon$$\cup$$\colon\\!\textsf{u}_{2}$$\gamma_{1}$$\textsf{m}_{1}\colon$$\gamma_{2}$$\colon\\!\textsf{m}_{2}$
Figure 2: On the left, the structure of input nodes $\textsf{n}_{1}$ and
$\textsf{n}_{2}$ and, on the right, the node $\textsf{n}^{\prime}$ that
represents $\textsf{union}(\textsf{n}_{1},\textsf{n}_{2})$. In this
construction, nodes $\textsf{n}_{1}^{\prime}$, $\textsf{n}_{2}^{\prime}$,
$\textsf{m}_{1}$, $\textsf{m}_{2}$ are reused and all other nodes are fresh
nodes.

We can conclude that, if we start with a $4$-bounded ECSA $\mathcal{D}$ and we
apply add, extend, and union operators between safe nodes, then the operations
retrieve safe nodes and the ECSA remains $4$-bounded as well. If we add that
the resulting ECSA is always garbage-free, then
${\lsem{}{\mathcal{D}}\rsem}(\textsf{n})$ can be enumerated with output-linear
delay for every n. Further, we can note that the data structure is fully-
persistent [18] in the sense that ${\lsem{}{\mathcal{D}}\rsem}(\textsf{n})$ is
immutable after each operation for every node n in $\mathcal{D}$. This last
property will be important for the preprocessing of our algorithm. Summing up,
we have proved the following result.

######  Theorem D.2.

Assume that $\mathcal{R}$ is a fixed set. The operations add, extend, and
union take constant time and are fully persistent. Furthermore, if we start
from an empty $\mathcal{D}$ and apply these operations over safe nodes, the
result node $\textsf{n}^{\prime}$ is always a safe node and
${\lsem{}{\mathcal{D}}\rsem}(\textsf{n})$ can be enumerated with output-linear
delay for every node n.

#### The evaluation algorithm

In Algorithm 3, we present an evaluation algorithm for EnumNSST when the input
NSST is garbage-free. By Theorem 5.2, we can convert any NSST into an
equivalent garbage-free NSST and, therefore, Algorithm 3 works also for any
NSST (after a preprocessing step). The main procedure is Evaluation that
receives as input a garbage-free NSST
$\mathcal{T}=(Q,\Sigma,\Omega,\mathcal{R},\Delta,I,F)$ and a string
$w=a_{1}\ldots a_{n}$ and enumerates all the strings
${\lsem{}{\mathcal{T}}\rsem}(w)$. Recall that ${\lsem{}{\mathcal{T}}\rsem}(w)$
is a bag, and that these these may have repetitions during the enumeration
phase.

Algorithm 3 The evaluation algorithm for garbage-free NSST. It receives as
input a garbage-free NSST
$\mathcal{T}=(Q,\Sigma,\Omega,\mathcal{R},\Delta,I,F)$ and a string
$w=a_{1}\ldots a_{n}$, and enumerates all the strings in
${\lsem{}{\mathcal{T}}\rsem}(w)$ (with repetitions).

1:procedure Evaluation($\mathcal{T},w$)

2: $\mathcal{D}\leftarrow\emptyset$

3: $T_{\textsf{old}}\leftarrow\textsc{InitialStates}(I)$

4: for $i=1$ to $n$ do

5: $T_{\textsf{new}}\leftarrow\emptyset$

6: for each $p\in\textsf{dom}(T_{\textsf{old}})$ do

7: for each $(p,a_{i},\sigma,q)\in\Delta$ do

8:
$T_{\textsf{new}}\leftarrow\textsc{UpdateLT}(T_{\textsf{new}},q,T_{\textsf{old}}[p],\sigma)$

9: $T_{\textsf{old}}\leftarrow T_{\textsf{new}}$

10: $\textsc{Enumerate}(T_{\textsf{old}},F)$

11:

12:procedure InitialStates($I$)

13: $T\leftarrow\emptyset$

14: for each $p\in\textsf{dom}(I)$ do

15: $T[p]\leftarrow\mathcal{D}.\textsf{add}(I(p))$

16: return $T$

17:procedure UpdateLT($T,q,\textsf{n},\sigma$)

18:
$\textsf{n}^{\prime}\leftarrow\mathcal{D}.\textsf{extend}(\textsf{n},\sigma)$

19: if $T[q]=\bot$ then

20: $T[q]\leftarrow\textsf{n}^{\prime}$

21: else

22: $T[q]\leftarrow\mathcal{D}.\textsf{union}(T[q],\textsf{n}^{\prime})$

23: return $T$

24:

25:procedure Enumerate($T,F$)

26: for each $p\in\textsf{dom}(F)\cap\textsf{dom}(T)$ do

27: for each $\nu\in{\lsem{}{\mathcal{D}}\rsem}(T[p])$ do

28: print $\hat{\nu}(F(p))$

Intuitively, the algorithm evaluates $\mathcal{T}$ over $w$ in one pass, by
simulating all runs of $\mathcal{T}$ on-the-fly. It reads each symbol $a_{i}$
sequentially and keeps a set of _active states_. A state $q\in Q$ is _active_
after reading letter $a_{i}$ if there exists a run of $\mathcal{T}$ over
$a_{1}\ldots a_{i}$ that reaches $q$. Then for each active state $q$ we
maintain a node $\textsf{n}_{q}$ that represents all the valuations of runs
that reach $q$. After reading $w$ completely, we can retrieve the outputs from
the nodes whose corresponding active states are also final states. In the
following, we explain this algorithm more in detail and discuss its
correctness.

In Algorithm 3, we use two data structures: (1) an Enumerable Compact Set with
Assignments (ECSA)
$\mathcal{D}=(\mathcal{R},\Omega,\textsf{N},\ell,r,\lambda)$ and (2) lookup
tables for storing nodes in N. For the ECSA $\mathcal{D}$, we use the methods
add, extend, and union explained in the previous subsections. By Theorem D.2,
we assume that each such operations takes constant time. Additionally, we will
write $\mathcal{D}\leftarrow\emptyset$ to denote that we initialize
$\mathcal{D}$ as empty. We will assume that $\mathcal{D}$ is globally
available by all procedures and subprocedures of Algorithm 3.

To remember the set of active states, we use _lookup tables_ , usually denoted
by $T$, whose entries are states (i.e., active states) and each entry stores a
node n from $\mathcal{D}$. Formally, we can define a lookup table $T$ as a
partial function $T:Q\rightharpoonup\textsf{N}$. We write $\textsf{dom}(T)$ to
denote all the states that have an entry in $T$ and $\emptyset$ to denote the
empty lookup table. If $q\in\textsf{dom}(T)$, we write $T[q]$ to retrieve the
node at entry $q$. As usual, we write $T[q]=\bot$ when
$q\notin\textsf{dom}(T)$ (i.e., $T[q]$ is not defined). We use
$T[q]\leftarrow\textsf{n}$ to declare that the $q$-entry of $T$ is updated
with the node n. Since we assume the RAM computational model, we can assume
that each update or query (e.g., $q\in\textsf{dom}(T)$) to the lookup table
takes constant time.

We give the preprocessing phase of Algorithm 3 in the Evaluation procedure,
specifically, from lines $2$ to $9$. This phase starts by initializing the
ECSA $\mathcal{D}$ as empty (line 2) and setting the initial lookup table
$T_{\textsf{old}}$ (line 3). We code the initialization of $T_{\textsf{old}}$
in the subprocedure InitialStates (lines 12-16). The initialization receives
as input the initial function $I$ of $\mathcal{T}$ and prepares $T$ with the
set of initial states $p\in\textsf{dom}(I)$ with their corresponding initial
valuations $I(p)$. It finally returns $T$ which represents the set of initial
active states.

The main for-loop of the evaluation algorithm proceeds as follows (lines 4-9).
It reads the string $w=a_{1}\ldots a_{n}$ sequentially, from $i=1$ to $n$. For
each $a_{i}$, it initializes a lookup table $T_{\textsf{new}}$ to empty (line
5), where $T_{\textsf{new}}$ represents the set of new active states after
reading $a_{i}$. Then for each active state
$p\in\textsf{dom}(T_{\textsf{old}})$ and each transition $t$ of the form
$t=(p,a_{i},\sigma,q)\in\Delta$, it fires $t$ and updates $T_{\textsf{new}}$
accordingly (lines 6-8). To update the lookup table $T_{\textsf{new}}$ with
$t$, we use the method UpdateLT (lines 17-23). The method receives a lookup
table $T$, a state $q$, a node n, and an assignment $\sigma$, and updates the
entry $T[q]$ with n and $\sigma$. Specifically, if $T[q]$ is not defined, it
inserts $\textsf{n}^{\prime}=\mathcal{D}.\textsf{extend}(\textsf{n},\sigma)$
in $T[q]$ (lines 19-20). Otherwise, it updates $T[q]$ with the union between
the current node at $T[q]$ and $\textsf{n}^{\prime}$. Intuitively, in this
step we are extending the outputs in $p$ represented by node n with the
assignment $\sigma$ of the transition $t$ and store it in
$T_{\textsf{new}}[q]$, accordingly. Finally, after all transitions are fired,
we swap $T_{\textsf{old}}$ with $T_{\textsf{new}}$ (line 9) and proceed to the
next symbol.

After we read the last symbol $a_{n}$, we continue with the enumeration phase,
by calling the subprocedure Enumerate (line 10). This enumeration subprocedure
(lines 25-28) receives as input the old table $T_{\textsf{old}}$, denoted by
$T$, and the final function $F$. For the enumeration, it considers each state
$p$ that is both final (i.e., $p\in\textsf{dom}(F)$) and active (i.e.,
$p\in\textsf{dom}(T)$). We assume here that
$\textsf{dom}(F)\cap\textsf{dom}(T)$ is computed once, before starting the
iteration for each $p\in\textsf{dom}(F)\cap\textsf{dom}(T)$ (line 26). The
enumeration proceeds by taking each valuation
$\nu\in{\lsem{}{\mathcal{D}}\rsem}(T[p])$ and printing $\hat{\nu}(F(p))$
(lines 27-28). By Proposition D.1, we know that we can enumerate all
${\lsem{}{\mathcal{D}}\rsem}(T[p])$ with output-linear delay and without
preprocessing. Then getting the next $\nu\in{\lsem{}{\mathcal{D}}\rsem}(T[p])$
and printing the output string $u=\hat{\nu}(F(p))$ takes time proportional to
$O(|u|)$, given that $\mathcal{D}$ is garbage-free (since $\mathcal{T}$ is
garbage-free). In other words, we can conclude that the enumeration phase runs
with output-linear delay.

We end by discussing the correctness and running time of the evaluation
algorithm. For the correctness, one can prove by induction on the length of
$w$ that before reading each $a_{i}$, $\textsf{dom}(T_{\textsf{old}})$ is the
set of active states and ${\lsem{}{\mathcal{D}}\rsem}(T_{\textsf{old}}[p])$
are all valuations of runs of $\mathcal{T}$ over $a_{1}\ldots a_{i-1}$.
Furthermore, $\mathcal{D}$ is always garbage-free given that $\mathcal{T}$ is
garbage-free. Then, after reading the last letter $a_{n}$, $T_{\textsf{old}}$
contains all active states and its corresponding valuations, and the method
Enumerate retrieves all strings in ${\lsem{}{\mathcal{T}}\rsem}(w)$ correctly,
and with output-linear delay. For the time complexity of the preprocessing
phase, we can check that each step takes constant time (i.e., by Theorem D.2)
and in each iteration we perform at most $|\mathcal{T}|$ number of steps.
Overall, the evaluation algorithm takes at most $O(|\mathcal{T}|\cdot|w|)$
number of steps to finish.

##  Appendix E Proofs of Section 6

###  E.1 Proofs of Theorem 6.1

###### Proof.

Let
$\mathcal{T}_{1}=(Q_{1},\Sigma,\Omega,\mathcal{R}_{1},\Delta_{1},I_{1},F_{1})$
and
$\mathcal{T}_{2}=(Q_{2},\Omega,\Gamma,\mathcal{R}_{2},\Delta_{2},I_{2},F_{2})$
be two NSSTs such that $\Omega\subseteq\Gamma$. By Proposition 5.2, we can
assume for the rest of the proof that $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$
are garbage-free.

Given sets $A$ and $B$, we define the set
$\textsf{Asg}^{*}(A,B)\subseteq\textsf{Asg}(A,B)$ of all copyless assignments
that are copyless both in $A$ and $B$, simultaneously; namely, every element
in $A\cup B$ appears at most once in the image of $\sigma$ for every
$\sigma\in\textsf{Asg}^{*}(A,B)$. Note that $\textsf{Asg}^{*}(A,B)$ is a
finite set. In the sequel, we will use $\zeta$ to denote an assignment in
$\textsf{Asg}^{*}(A,B)$.

We define the NSST $\mathcal{T}$ that will work as the composition of
$\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ such that:

$\mathcal{T}\ =\ (Q,\Sigma,\Gamma,\mathcal{R},\Delta,I,F)$

where
$Q=Q_{1}\times\\{f\colon\mathcal{R}_{1}\rightharpoonup(Q_{2}\times\textsf{Asg}^{*}(\mathcal{R}_{2},\mathcal{R})\times
Q_{2})\\}$. Intuitively, the states of $\mathcal{T}$ simulates a run of
$\mathcal{T}_{1}$ in the first component. In the second component,
$\mathcal{T}$ remember a _subrun_ $f(X)=(q_{1},\sigma,q_{2})$ over the content
of register $X\in\mathcal{R}_{1}$ from $\mathcal{T}_{1}$, where $q_{1}\in
Q_{2}$ is the starting state, $q_{2}\in Q_{2}$ is the ending state, and
$\sigma$ is a _summary_ of the registers content of $\mathcal{T}_{2}$. To
define the other components of $\mathcal{T}$ (i.e., $\Delta$, $I$, and $F$) we
need several technical definitions that we introduce next.

#### Summaries

We start by formalizing the notion of summary, introduced in [3]. Given a word
$w\in(\mathcal{R}_{2}\cup\Gamma\cup\mathcal{R})^{*}$ we define the _summary of
$w$ by $\mathcal{R}$_ as the pair $(\bar{w},\zeta)$ such that, if $w$ is of
the form:

$w=u_{1}X_{1}u_{2}X_{2}\ldots X_{k}u_{k+1}$

for some $k\geq 0$ such that $X_{i}\in\mathcal{R}_{2}$ and
$u_{i}\in(\Gamma\cup\mathcal{R})^{*}$, then
$\bar{w}=Y_{1}X_{1}Y_{2}X_{2}\ldots X_{k}Y_{k+1}$ for some pairwise distinct
registers $Y_{1},\ldots,Y_{k+1}\in\mathcal{R}$ and
$\zeta\in\textsf{Asg}(\\{Y_{1},\ldots,Y_{k+1}\\},\Gamma\cup\mathcal{R})$
satisfies that $\zeta(Y_{i})=u_{i}$ for every $i\leq k+1$. The idea of a
summary $(\bar{w},\zeta)$ is to replace each maximal subword
$u_{1},\ldots,u_{k+1}\in(\Gamma\cup\mathcal{R})^{*}$ from $w$ with distinct
registers $Y_{1},\ldots,Y_{k+1}$, represented by $\bar{w}$, and store them
into the registers $Y_{1},\ldots,Y_{k+1}$, represented by $\zeta$. In
particular, one can check that $\zeta(\bar{w})=w$ and that $\zeta$ is always
copyless.

We can generalize the notion of summary from words to assignments as follows.
Let $\sigma\in\textsf{Asg}(\mathcal{R}_{2},\Gamma\cup\mathcal{R})$ be an
assignment and assume that $\textsf{dom}(\sigma)=\\{X_{1},\ldots,X_{\ell}\\}$.
The summary of $\sigma$ by $\mathcal{R}$ is a pair $(\bar{\sigma},\zeta)$ such
that, if $(\bar{w}_{1},\zeta_{1}),\ldots,(\bar{w}_{\ell},\zeta_{\ell})$ are
summaries of $\sigma(X_{1}),\ldots,\sigma(X_{\ell})$, respectively, with
$\textsf{dom}(\zeta_{i})\cap\textsf{dom}(\zeta_{i^{\prime}})=\emptyset$ for
every $i\neq i^{\prime}$, then $\bar{\sigma}(X_{j})=\bar{w}_{j}$ for every
$j\leq\ell$ and $\zeta=\zeta_{1}\cup\ldots\cup\zeta_{\ell}$. Intuitively, we
are summarizing every $\sigma(X_{i})$ together into a single assignment
$\bar{\sigma}$ and $\zeta$ is the disjoint union of $\zeta_{i}$. Finally, the
summary of a tuple $(\sigma_{1},\ldots,\sigma_{n})$ with each
$\sigma_{i}\in\textsf{Asg}(\mathcal{R}_{2},\Gamma\cup\mathcal{R})$ is a pair
$((\bar{\sigma}_{1},\ldots,\bar{\sigma}_{n}),\zeta_{1}\cup\ldots\cup\zeta_{n})$
such that, for every $i\leq n$, $(\bar{\sigma}_{i},\zeta_{i})$ is a summary of
$\sigma_{i}$ and
$\textsf{dom}(\zeta_{i})\cap\textsf{dom}(\zeta_{j})=\emptyset$ for every
$j\neq i$. Notice that $\zeta$ is an assignment in
$\textsf{Asg}(\mathcal{R},\Gamma)$ and it is always copyless, since we always
pick disjoint set of registers for each component.

#### Semigroup of subruns

The following semigroup will be useful for composing subruns and checking if
the composition is valid. Consider the semigroup with domain
$\mathcal{S}=(Q_{2}\times\textsf{Asg}(\mathcal{R}_{2},\Gamma\cup\mathcal{R})\times
Q_{2})\cup\\{\bot\\}$ where $\bot$ is a new fresh element. Then we define the
operation $\circledast$ of the semigroup such that:

$(q_{1},\sigma,q_{2})\circledast(q_{3},\sigma^{\prime},q_{4})\ =\
\left\\{\begin{array}[]{ll}(q_{1},\sigma\circ\sigma^{\prime},q_{4})&\text{if
}q_{2}=q_{3}\\\ \bot&\text{otherwise}\end{array}\right.$

Further, $s_{1}\circledast s_{2}=\bot$ whenever $s_{1}=\bot$ or $s_{2}=\bot$.
One can easily check that $(\mathcal{S},\circledast)$ forms a semigroup, given
that $\circledast$ is well-defined in $\mathcal{S}$ (i.e., the result is
always an element in $\mathcal{S}$), and is associative. Below, we will use
the semigroup $(\mathcal{S},\circledast)$ to easily apply and check that
subruns match. Indeed, one can check that $s_{1}\circledast s_{2}=s_{3}$ and
$s_{3}\neq\bot$, then $s_{3}$ is the subrun representing $s_{1}$ followed by
$s_{2}$. Instead, if $s_{1}\circledast s_{2}=\bot$ then either $s_{1}$ or
$s_{2}$ are not valid subruns, or $s_{1}$ followed by $s_{2}$ does not form a
subrun.

For using the semigroup $(\mathcal{S},\circledast)$, the notion of
homomorphism between semigroups will be also relevant. Let $A$ be any finite
alphabet. An _homomorphism_ from $(A^{*},\cdot)$ to
$(\mathcal{S},\circledast)$ is a function $H:A^{*}\to\mathcal{S}$ such that
$H(w_{1}\cdot w_{2})=H(w_{1})\circledast H(w_{2})$. In the following, we will
usually define homomorphisms as a function $H:A\to\mathcal{S}$, that extends
naturally to a homomorphism $H:A^{*}\to\mathcal{S}^{*}$ such that
$H(a_{1}\ldots a_{n})=H(a_{1})\circledast\ldots\circledast H(a_{n})$.

#### Assignment indexing

The last technical ingredient is a notation for indexing all letters from an
assignment in $\textsf{Asg}(\mathcal{R}_{1},\Omega)$. Formally, for
$c\in\mathcal{R}_{1}\cup\Omega$, let $\textsf{index}(c,X,i)$ be a function
such that $\textsf{index}(c,X,i)=(c,X,i)$ if $c\in\Omega$ and
$\textsf{index}(c,X,i)=c$, otherwise. Then we define $\sigma_{\textsf{index}}$
as an assignment in
$\textsf{Asg}(\mathcal{R}_{1},\Omega\times\mathcal{R}_{1}\times\mathbb{N})$
such that $\textsf{dom}(\sigma_{\textsf{index}})=\textsf{dom}(\sigma)$ and, if
$\sigma(X)=c_{1}\ldots c_{n}$, then:

$\sigma_{\textsf{index}}(X)=\textsf{index}(c_{1},X,1)\ldots\textsf{index}(c_{n},X,n).$

For the special case that $\sigma(X)=\epsilon$, we define
$\sigma_{\textsf{index}}(X)=(\epsilon,X,1)$. In other words,
$\sigma_{\textsf{index}}$ works as $\sigma$ where each letter in $\sigma(X)$
is indexed by $X$ and its position. For example, below we show an assignment
$\sigma$ and its corresponding $\sigma_{\textsf{index}}$.

$\begin{array}[]{ll}\begin{array}[]{rl}\sigma:\\!\\!&X:=baXab\\\ &Y:=Xb\\\
&Z:=\epsilon\end{array}&\ \ \ \ \
\begin{array}[]{rl}\sigma_{\textsf{index}}:\\!\\!&X:=(b,X,1)(a,X,2)Y(a,X,4)(b,X,5)\\\
&Y:=X(b,Y,2)\\\ &Z:=(\epsilon,Z,1)\end{array}\end{array}$

Finally, define $\textsf{index}[\sigma]$ to be all letters of the form
$(c,X,i)$ that appear in $\sigma_{\textsf{index}}$. We call $(c,X,i)$ an
_index_ of $\sigma$.

It will be convenient to extend the notation $\sigma_{\textsf{index}}$ to
words. Specifically, for a word $w=c_{1}\ldots c_{n}\in(R_{1}\cup\Omega)^{*}$
we define
$w_{\textsf{index}}=\textsf{index}(c_{1},1)\ldots\textsf{index}(c_{n},n)$
where $\textsf{index}(c,i)=(c,i)$ if $c\in\Omega$, and
$\textsf{index}(c,i)=c$, otherwise. If $w=\epsilon$, we define
$w_{\textsf{index}}=(\epsilon,1)$. For the word case, note that we omit the
$X$ component in the index, given that it is unnecessary.

The purpose of $\sigma_{\textsf{index}}$ is to identify each letter $a$ (or
$\epsilon$) in $\sigma$ and to assign a special code $(a,X,i)$. The set
$\textsf{index}[\sigma]$ will allow us to collect all these codes for deciding
the transitions that we will use when the NSST $\mathcal{T}_{1}$ takes a
transition. This will be more clear in the next subsection, when we finally
define the transition relation of $\mathcal{T}$.

#### Definition of $\Delta$

We have all the ingredients to define the components $\Delta$, $I$, and $F$ of
the NSST $\mathcal{T}$. For defining $\Delta$, we repeat the following steps,
until all possible decisions are covered.

  1. 1.

Take a state $(p,f)\in Q$ (recall that $f:\mathcal{R}_{1}\rightharpoonup
Q_{2}\times\textsf{Asg}^{*}(\mathcal{R}_{2},\mathcal{R})\times Q_{2}$).

  2. 2.

Take a transition $(p,a,\sigma,q)\in\Delta_{1}$.

  3. 3.

Let
$\textsf{index}[\sigma]=\\{(a_{1},X_{1},i_{1}),\ldots,(a_{\ell},X_{\ell},i_{\ell})\\}$
be all indexes of $\sigma$.

  4. 4.

Choose transitions
$(q_{1},a_{1},\sigma_{1},q_{1}^{\prime}),\ldots,(q_{\ell},a_{\ell},\sigma_{\ell},q_{\ell}^{\prime})\in\Delta_{2}$.
For the special case that $a_{i}=\epsilon$ for some $i\leq\ell$, choose a pair
of the form $(q_{i},\epsilon,\sigma_{\textsf{id}},q_{i})$ where $q_{i}\in
Q_{2}$ and $\sigma_{\textsf{id}}$ is the identity function over
$\mathcal{R}_{2}$.

  5. 5.

Define the homomorphism
$H:\mathcal{R}_{1}\cup\textsf{index}[\sigma]\to\mathcal{S}$ from words to the
semigroup $(\mathcal{S},\circledast)$ such that $H(X)=f(X)$ for every
$X\in\mathcal{R}_{1}$ and
$H((a_{j},X_{j},i_{j}))=(q_{j},\sigma_{j},q_{j}^{\prime})$ for every
$j\leq\ell$.

  6. 6.

If $H(\sigma_{\textsf{index}}(X))\neq\bot$ for every
$X\in\textsf{dom}(\sigma_{\textsf{index}})$, then continue.

  7. 7.

Let $\textsf{dom}(\sigma)=\\{Y_{1},\ldots,Y_{m}\\}$ and let
$H(\sigma_{\textsf{index}}(Y_{i}))=(p_{i},\pi_{i},p_{i}^{\prime})$ for every
$i\leq m$.

  8. 8.

Construct the summary $((\bar{\pi}_{1},\ldots,\bar{\pi}_{m}),\zeta)$ of
$(\pi_{1},\ldots,\pi_{m})$.

  9. 9.

Define the partial function $f^{\prime}$ such that
$\textsf{dom}(f^{\prime})=\\{Y_{1},\ldots,Y_{m}\\}$ and
$f^{\prime}(Y_{i})=(p_{i},\bar{\pi}_{i},p_{i}^{\prime})$.

  10. 10.

Add the transition $((p,f),a,\zeta,(q,f^{\prime}))$ to $\Delta$.

For understanding the previous construction, recall that $(p,f)\in Q$
represents that $\mathcal{T}_{1}$ is in state $p$ and, for every register $X$
of $\mathcal{T}_{1}$, $\mathcal{T}_{2}$ has a subrun $f(X)$ over the content
of $X$ (step (1)). Then, if we move $\mathcal{T}_{1}$ by using
$(p,a,\sigma,q)\in\Delta_{1}$ (step (2)), then we need to update the moves of
$\mathcal{T}_{2}$, namely, update $f$ with $\sigma$ and $\Delta_{2}$. The
moves of $\mathcal{T}_{2}$ for registers in $\sigma$ are encoded in $f$, but
we still have to decide how to move with letters in $\sigma$. For this reason,
we choose one transition $(q_{j},a_{j},\sigma_{j},q_{j}^{\prime})$ for each
letter $a_{j}\in\Omega$ appearing in $\sigma$, represented by the index
$(a_{j},X_{j},i_{j})$ (step (3) and (4)). Thus, for simulating
$\mathcal{T}_{2}$ over $\sigma$, we define the homomorphism $H$, which for
every register content $X$ uses $f(X)$ and for every letter indexed as
$(a_{j},X_{j},i_{j})$ uses $(q_{j},\sigma_{j},q_{j}^{\prime})$ (step (5)). To
check that these guesses of the subruns and the transitions are correct, we
check that the homomorphism $H$ applied to each content
$\sigma_{\textsf{index}}(X)$ is different from $\bot$ (step (6)). If this is
the case, it means that the subruns and guessed transitions coincide, and we
proceed to construct the new transition in $\Delta$ (steps (7) to (10)).
Towards this goal, we summarize the subrun
$H(\sigma_{\textsf{index}}(Y_{i}))=(p_{i},\pi_{i},p_{i}^{\prime})$ and store
it in $f^{\prime}$ as $f^{\prime}(Y_{i})=(p_{i},\bar{\pi}_{i},p_{i}^{\prime})$
(steps (7) to (9)). The summaries produce the copyless assignment $\zeta$ that
stores the partial valuations of the summaries in $\mathcal{R}$-registers.
Finally, we define the transition $((p,f),a,\zeta,(q,f^{\prime}))\in\Delta$,
which encodes the whole process above.

It is important to note that $\zeta$ in the transition
$((p,f),a,\zeta,(q,f^{\prime}))\in\Delta$ is a copyless assignment. Indeed,
given that $H$ works as a homomorphism and there is a single appearance of
each register $X$ in $\sigma$, then each register of $\mathcal{R}$ appears at
most once over all assignments $\pi_{1},\ldots,\pi_{m}$. Therefore, the
construction here always produces copyless assignments.

#### Definition of $I$

For defining the initial partial function $I$, we proceed similar to $\Delta$:

  1. 1.

Take a state $p\in Q_{1}$ such that $I_{1}(p)=\nu$.

  2. 2.

Let
$\textsf{index}[\nu]=\\{(a_{1},X_{1},i_{1}),\ldots(a_{\ell},X_{\ell},i_{\ell})\\}$
be the indexes of $\nu$.

  3. 3.

Choose transitions
$(q_{1},a_{1},\sigma_{1},q_{1}^{\prime}),\ldots,(q_{\ell},a_{\ell},\sigma_{\ell},q_{\ell}^{\prime})\in\Delta_{2}$.
For the special case that $a_{i}=\epsilon$ for some $i\leq\ell$, choose a pair
of the form $(q_{i},\epsilon,\sigma_{\textsf{id}},q_{i})$ where $q_{i}\in
Q_{2}$ and $\sigma_{\textsf{id}}$ is the identity function over
$\mathcal{R}_{2}$.

  4. 4.

Define the homomorphism $H:\textsf{index}[\nu]\to\mathcal{S}$ from words to
the semigroup $(\mathcal{S},\circledast)$ such that
$H((a_{j},X_{j},i_{j}))=(q_{j},\sigma_{j},q_{j}^{\prime})$ for every
$j\leq\ell$.

  5. 5.

If $H(\nu_{\textsf{index}}(X))\neq\bot$ for every
$X\in\textsf{dom}(\nu_{\textsf{index}})$, then continue.

  6. 6.

Let $\textsf{dom}(\nu)=\\{Y_{1},\ldots,Y_{m}\\}$ and let
$H(\nu_{\textsf{index}}(Y_{i}))=(p_{i},\pi_{i},p_{i}^{\prime})$ for every
$i\leq m$.

  7. 7.

Construct the summary $((\bar{\pi}_{1},\ldots,\bar{\pi}_{m}),\zeta)$ of
$(\pi_{1},\ldots,\pi_{m})$.

  8. 8.

Define the partial function $f$ such that
$\textsf{dom}(f)=\\{Y_{1},\ldots,Y_{m}\\}$ and
$f(Y_{i})=(p_{i},\bar{\pi}_{i},p_{i}^{\prime})$.

  9. 9.

Define $I((p,f))=\zeta$.

The definition of $I$ follows the same approach as for the transition relation
$\Delta$. Intuitively, if we start with a state $p$ such that $I_{1}(p)$ is
defined and equal to $\nu$, then we run $\mathcal{T}_{2}$ over the content in
$\nu$. Given that $\nu$ is an assignment, the definition follows the same
ideas as for $\Delta$, by switching $\sigma$ with $\nu$.

#### Definition of $F$

The construction of the final function $F$ is slightly different to $\Delta$
and $I$, although we present it in a similar fashion.

  1. 1.

Take a state $(p,f)\in Q$ such that $F_{1}(p)$ is defined.

  2. 2.

Let $\textsf{index}[F_{1}(p)]=\\{(a_{1},i_{1}),\ldots(a_{\ell},i_{\ell})\\}$
be the indexes of $F_{1}(p)$.

  3. 3.

Choose transitions
$(q_{1},a_{1},\sigma_{1},q_{1}^{\prime}),\ldots,(q_{\ell},a_{\ell},\sigma_{\ell},q_{\ell}^{\prime})\in\Delta_{2}$
(not necessarily different). For the special case that $F_{1}(p)=\epsilon$ and
$\textsf{index}[F_{1}(p)]=\\{(\epsilon,1)\\}$, choose one tuple of the form
$(r,\epsilon,\sigma_{\textsf{id}},r)$ for some $r\in Q_{2}$ and
$\sigma_{\textsf{id}}$ is the identity function over $\mathcal{R}_{2}$.

  4. 4.

Define the homomorphism
$H:\mathcal{R}_{1}\cup\textsf{index}[F_{1}(p)]\to\mathcal{S}$ from words to
the semigroup $(\mathcal{S},\circledast)$ such that $H(X)=f(X)$ for every
$X\in\mathcal{R}_{1}$ and $H((a_{j},i_{j}))=(q_{j},\sigma_{j},q_{j}^{\prime})$
for every $j\leq\ell$.

  5. 5.

If $H(F_{1}(p))=(p_{0},\pi,p_{f})$ and both $I_{2}(p_{0})$ and $F_{2}(p_{f})$
are defined, then define:

$F((p,f))=[I_{2}(p_{0})]\big{(}\pi(F_{2}(p_{f}))\big{)}.$

Here, the goal is to reconstruct the final output of $\mathcal{T}_{2}$, given
that $\mathcal{T}_{1}$ reaches a final state where $F_{1}(p)$ is defined (step
(1)). Then, similar to $\Delta$, we choose the transitions for the letters in
$F_{1}(p)$ (steps (2) and (3)), and construct the homomorphism $H$ to simulate
$\mathcal{T}_{2}$ over $F_{1}(p)$ (step (4)). If
$H(F_{1}(p))=(p_{0},\pi,p_{f})$, this means that the subruns and transitions
of $\mathcal{T}_{2}$ match. However, we have to still check that $p_{0}$ is an
initial state and $p_{f}$ is a final state. If this is the case, then we can
reconstruct the output of $\mathcal{T}_{2}$ with the expression
$[I_{2}(p_{0})]\big{(}\pi(F_{2}(p_{f}))\big{)}$ (step (5)).

#### Correctness

This concludes the construction of $\mathcal{T}$. To show that
${\lsem{}{\mathcal{T}}\rsem}(\mathbf{D})={\lsem{}{\mathcal{T}_{1}\circ\mathcal{T}_{2}}\rsem}(\mathbf{D})$
for every document $\mathbf{D}$, the proofs goes by making a bijection between
accepting runs $\rho$ of $\mathcal{T}$ over $\mathbf{D}$ and pair of runs
$(\rho_{1},\rho_{2})$ such that $\rho_{1}$ is an accepting run of
$\mathcal{T}_{1}$ over $\mathbf{D}$ and $\rho_{2}$ is an accepting run of
$\mathcal{T}_{2}$ over the output of $\rho_{1}$. For defining this bijection
$F$, we can follow the construction above and, for every run $\rho$ of
$\mathcal{T}$ over $\mathcal{D}$, construct a unique pair
$(\rho_{1},\rho_{2})$ by induction. For showing that $F$ is injective, the
garbage-free assumption over $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ helps,
given that all the content tracked by $\mathcal{T}$ is useful, and then always
produce a unique pair $(\rho_{1},\rho_{2})$. For proving that $F$ is
surjective, from a pair of runs $(\rho_{1},\rho_{2})$ we can construct the run
$\rho$ over $\mathbf{D}$ by following the construction above. Given that there
is a bijection between ${\lsem{}{\mathcal{T}}\rsem}(\mathbf{D})$ and
${\lsem{}{\mathcal{T}_{1}\circ\mathcal{T}_{2}}\rsem}(\mathbf{D})$ for every
$\mathbf{D}$, we conclude that
${\lsem{}{\mathcal{T}}\rsem}={\lsem{}{\mathcal{T}_{1}\circ\mathcal{T}_{2}}\rsem}$.

#### Size of $\mathcal{T}$

To bound the size of the NSST $\mathcal{T}$, let $|Q_{1}|=k$,
$|\mathcal{R}_{1}|=\ell$, $|Q_{2}|=m$, and $|\mathcal{R}_{2}|=n$. Recall that
$Q=Q_{1}\times\mathcal{F}$ where:

$\mathcal{F}\ =\ \\{f:\mathcal{R}_{1}\rightharpoonup
Q_{2}\times\textsf{Asg}^{*}(\mathcal{R}_{2},\mathcal{R})\times Q_{2}\\}.$

First, we bound the number of register in $\mathcal{R}$ that we need to do the
summaries (i.e., $|\mathcal{R}|$). For this, we need to bound the number of
states to do a summary of one $f\in\mathcal{F}$. For one assignment
$\sigma\in\textsf{Asg}^{*}(\mathcal{R}_{2},\mathcal{R})$, we will need at most
$(n+1)^{2}$ registers. Given that we have at most $\ell$ of these assignments
in $f$, then we need at most $\ell\cdot(n+1)^{2}$ registers in $\mathcal{R}$,
namely, $|\mathcal{R}|\leq\ell\cdot(n+1)^{2}$. To simplify the following
calculations, let $N=\ell\cdot(n+1)^{2}$.

Next, we bound the size of $\textsf{Asg}^{*}(\mathcal{R}_{2},\mathcal{R})$.
For any $\sigma\in\textsf{Asg}^{*}(\mathcal{R}_{2},\mathcal{R})$ and any
$X\in\mathcal{R}_{2}$, we can put at most $(n+N+1)!$ different strings at the
entry $\sigma(X)$. Therefore,
$|\textsf{Asg}^{*}(\mathcal{R}_{2},\mathcal{R})|\leq((n+N+1)!)^{n}$.

To finish, we bound the size of $Q_{1}\times\mathcal{F}$. Given that
$\mathcal{F}$ are partial functions we have that the number of possible
elements in the image is:

$|Q_{2}\times\textsf{Asg}^{*}(\mathcal{R}_{2},\mathcal{R})\times Q_{2}|\leq
m^{2}\cdot((n+N+1)!)^{n}$

Then $|\mathcal{F}|\leq(m^{2}\cdot((n+N+1)!)^{n})^{\ell}$. We conclude that:

$\begin{array}[]{rcl}|Q|&\leq&|Q_{1}|\cdot|\mathcal{F}|\\\
&\leq&k\cdot(m^{2}\cdot((n+N+1)!)^{n})^{\ell}\\\ &\leq&k\cdot
m^{2\ell}\cdot((n+N+1)!)^{n\ell}\\\ &\leq&k\cdot
m^{2\ell}\cdot((n+\ell\cdot(n+1)^{2}+1)!)^{n\ell}\\\
&\leq&2^{\log(k)+2\ell\cdot\log(m)+n\ell\cdot(\ell\cdot(n+1)^{2})\cdot\log(\ell\cdot(n+1)^{2})}\end{array}$

where for the last equation we are using that $x!\leq x^{x}$ for $x$ big
enough. Then the number of states of $\mathcal{T}$ is in
$O\big{(}2^{g(|\mathcal{T}_{1}|,|\mathcal{T}_{2}|)}\big{)}$ for some
polynomial $g(x,y)$. Note that one can similarly bound the number of
transitions in $O\big{(}2^{g(|\mathcal{T}_{1}|,|\mathcal{T}_{2}|)}\big{)}$. ∎


# The spectra of the complements of graphs with given connectivity ††thanks:
This work is supported by NSFC (No. 11461071).

Huan Qiu, Keng Li, Guoping Wang111Corresponding author. Email<EMAIL_ADDRESS>
School of Mathematical Sciences, Xinjiang Normal University,
Urumqi, Xinjiang 830054, P.R.China

Abstract. Spectral radius of a graph $G$ is the largest eigenvalue of
adjacency matrix of $G$. The least eigenvalue of a graph $G$ is the least
eigenvalue of adjacency matrix of $G$. In this paper we determine the graphs
which attain respectively the minimum spectral radius and the minimum least
eigenvalue among all complements of connected simple graphs with given
connectivity.Spectral radius of a graph $G$ is the largest eigenvalue of
adjacency matrix of $G$. The least eigenvalue of a graph $G$ is the least
eigenvalue of adjacency matrix of $G$. In this paper we determine the graphs
which attain respectively the minimum spectral radius and the minimum least
eigenvalue among all complements of connected simple graphs with given
connectivity.

Key words:

Spectral radius; The least eigenvalue; Complements of graphs; Connectivity.

MR(2020) Subject Classification:

05C12, 05C50

##  1\. Introduction

Let $G$ be a connected simple graph with the vertex set
$V(G)=\\{v_{1},v_{2},\ldots,v_{n}\\}$ and the edge set $E(G)$. The adjacency
matrix of $G$ is denoted by $A(G)=(a_{ij})_{n\times n}$, where $a_{ij}=1$ if
$v_{i}v_{j}\in E(G)$, and $a_{ij}=0$ otherwise. Since $A(G)$ is a non-negative
real symmetric matrix, its eigenvalues can be ranged as
$\lambda_{1}(G)\geq\lambda_{2}(G)\geq\cdots\geq\lambda_{n}(G)$, where
$\lambda_{1}(G)$ and $\lambda_{n}(G)$ are called spectral radius and the least
eigenvalue of $G$, respectively. The complement of $G$ is denoted by
$G^{c}=(V(G^{c}),E(G^{c}))$, where $V(G^{c})=V(G)$ and $E(G^{c})=\\{uv:u,v\in
V(G),uv\notin E(G)\\}$.

There is little research about spectra of the complements of graphs. Y. Fan,
F. Zhang and Y. Wang [3] determined the connected graph with the minimal least
eigenvalue among all complements of trees. G. Jiang, G. Yu, W. Sun and Z. Ruan
[6] gave the graph with the minimum least eigenvalue among all graphs whose
complements have only two pendent vertices. S. Li and S. Wang [5] introduced
the unique connected graph whose the least signless Laplacian eigenvalue
attains the minimum among all complements of trees. G. Yu, Y. Fan and M. Ye
[9] achieved the unique graph which minimizes the least signless Laplacian
eigenvalue among all connected complements of unicyclic graphs. H. Lin and S.
Drury [4] characterized the unique graph whose distance spectral radius has
maximum and minimum among all complements of trees, and the unique graph whose
the least distance eigenvalue has maximum and minimum among all complements of
trees. R. Qin, D. Li, Y. Chen and J. Meng [7] determined the unique graph
which has maximum distance spectral radius among all complements of unicyclic
graphs and the unique graph which has maximum least distance eigenvalue among
all complements of unicyclic graphs of diameter three. X. Chen and G. Wang [1]
characterized among all complements of graphs of diameter greater than three
the unique graph whose distance spectral radius attains respectively maximum
and minimum and whose the least distance eigenvalue attains minimum. X. Chen
and G. Wang [2] characterized among all complements of graphs with two pendent
vertices the unique graph whose distance spectral radius attains respectively
maximum and minimum and whose the least distance eigenvalue attains minimum.

The connectivity of graph is the minimum number of vertices whose deletion
yields the resulting graph disconnected. We study spectral radius and the
least eigenvalue of the complements of graphs with given connectivity in this
paper. This paper is organized as follows. In Section $2$ we give some
preliminary results. In Section $3$ and Section $4$ we determine the graphs
which attain respectively the minimum spectral radius and the minimum least
eigenvalue among all complements of connected simple graphs with given
connectivity.

##  2\. Preliminary

Suppose that $G$ is a connected simple graph with the vertex set
$V(G)=\\{v_{1},v_{2},\ldots,v_{n}\\}$. Let $x=(x_{1},x_{2},\cdots,x_{n})^{T}$,
where $x_{i}$ corresponds to $v_{i}$, i.e., $x(v_{i})=x_{i}$ for
$i=1,2,\cdots,n$. Then

$x^{T}A(G)x=\sum_{v_{i}v_{j}\in E(G)}2x_{i}x_{j}.$ (1)

If $u$, $v\in V(G)$ and $uv\in E(G)$ then $u$ and $v$ are neighbours. The set
of neighbours of $v$ in $G$ is denoted by $N_{G}(v)$. Suppose that $x$ is an
eigenvector of $A(G)$ corresponding to the eigenvalue $\lambda$. Then for
$v_{i}\in V(G)$, we have

$\lambda x_{i}=\sum_{v_{j}\in N_{G}(v_{i})}x_{j}\quad for\ i=1,2,\cdots,n.$
(2)

Lemma 2.1. (Rayleigh’s inequalities) Let $G$ be a connected simple graph with
spectral radius $\lambda_{1}(G)$ and the least eigenvalue $\lambda_{n}(G)$ of
$A(G)$, and $x=(x_{1},x_{2},\cdots,x_{n})^{T}$ be a unit vector. Then we have

$\lambda_{n}(G)\leq x^{T}A(G)x\leq\lambda_{1}(G).$

Moreover, the first equality holds if and only if $x$ is a unit eigenvector of
$A(G)$ with respect to $\lambda_{n}(G)$ and the second equality holds if and
only if $x$ is a unit eigenvector of $A(G)$ with respect to $\lambda_{1}(G)$.

Lemma 2.2. [8] Let the transmission $\sigma(G)$ of a connected simple graph
$G$ on $n$ vertices be the sum of distances between all unordered pairs of
vertices of $G$. Then $\lambda_{1}(G)\geq\frac{2\sigma(G)}{n}.$

Let $G$ be a connected simple graph on $n$ vertices, $J_{n}$ be the matrix of
order $n$ whose all entries are $1$ and $I_{n}$ be the identity matrix of
order $n$. Then we have

$A(G^{c})=J_{n}-I_{n}-A(G).$

Let $\mathbb{G}_{n,\kappa}$ denote the set of those connected simple graphs on
$n$ vertices with the connectivity $\kappa$. In the next two sections we will
characterize the extreme graphs which attain respectively the minimum spectral
radius and the minimum least eigenvalue among all complements of graphs in
$\mathbb{G}_{n,\kappa}$.

##  3\. Spectral radius of the complements of graphs with given connectivity

Let $G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$ are two graphs. The union
$G_{1}\cup G_{2}$ is defined to be $G_{1}\cup G_{2}=(V_{1}\cup V_{2},E_{1}\cup
E_{2})$. Graph $G$ is bipartite if its vertex set can be partitioned into two
subsets $X$ and $Y$ so that every edge has one end in $X$ and the other end in
$Y$. If every vertex in $X$ is joined to every vertex in $Y$, then $G$ is
called a complete bipartite graph, denoted by $K_{x,y}$ if $|X|=x$ and
$|Y|=y$. We denote by $d(G)$ the diameter of a graph $G$ which is farthest
distance between all pairs of vertices.

Theorem 3.1. Let $G\in\mathbb{G}_{n,\kappa}$. If $d(G)=2$, then
$\lambda_{1}(G^{c})\geq\sqrt{n-\kappa-1}$.

Proof. Suppose $\partial(G)$ is a minimum vertex-cut of $G$. Then
$|\partial(G)|=\kappa$. Let $D_{1}$ be the component of $G-\partial(G)$ which
has as few vertices as possible, and $D_{2}$ be the union of all other
components of $G-\partial(G)$ but $D_{1}$. Set $|V(D_{1})|=s$ and
$|V(D_{2})|=t$. Clearly, $s+t+\kappa=n$. Connect respectively all pairs of
vertices which are not adjacent in $D_{1}$, $D_{2}$ and $\partial(G)$, and
connect respectively all pairs of vertices which are not adjacent between
$D_{1}$ and $\partial(G)$ and between $D_{2}$ and $\partial(G)$. Then we
obtain the resulting graph $\mathcal{B}(s,t,\kappa)$. Clearly,
$\mathcal{B}^{c}(s,t,\kappa)=K_{s,t}\cup O_{\kappa}$, where $O_{\kappa}$ is an
empty graph of order $\kappa$.

Set $x=(x_{1},x_{2},\cdots,x_{n})^{T}$ to be the unit Perron vector of
$A(\mathcal{B}^{c}(s,t,\kappa))$ with respect to the eigenvalue
$\lambda_{1}(\mathcal{B}^{c}(s,t,\kappa))$, that is $x(v_{i})=x_{i}>0$
$(i=1,2,\cdots,n)$ and $\|x\|=1$.

From the equation $(1)$, we have

$x^{T}A(G)x=\sum_{v_{i}v_{j}\in E(G)}2x_{i}x_{j}\leq\sum_{v_{i}v_{j}\in
E(\mathcal{B}(s,t,\kappa))}2x_{i}x_{j}=x^{T}A(\mathcal{B}(s,t,\kappa))x$.

Thus we have

$\begin{split}\lambda_{1}(G^{c})&\geq x^{T}A(G^{c})x\\\
&=x^{T}(J_{n}-I_{n})x-x^{T}A(G)x\\\ &\geq
x^{T}(J_{n}-I_{n})x-x^{T}A(\mathcal{B}(s,t,\kappa))x\\\
&=x^{T}A(\mathcal{B}^{c}(s,t,\kappa))x\\\
&=\lambda_{1}(\mathcal{B}^{c}(s,t,\kappa))\\\
&=\lambda_{1}(K_{s,t}).\end{split}$

Whereas $\lambda_{1}(K_{s,t})=\sqrt{st}$ and
$\lambda_{1}(K_{s,t})\geq\lambda_{1}(K_{1,n-\kappa-1})$, we have
$\lambda_{1}(G^{c})\geq\sqrt{n-\kappa-1}$. $\Box$

By the above theorem we can assume $d(G)\geq 3$ in what follows below in this
section. Then there must be a component which contains a vertex v which is not
adjacent to any vertex of the vertex cut $\partial(G)$ of $G$. This implies
that $G^{c}$ is connected. Let $\widetilde{G}$ be the component of
$G-\partial(G)$ containing v. Let $G_{s}(\neq\widetilde{G})$ be the component
of $G-\partial(G)$ which has as few vertices as possible, and $G_{t}$ be the
union of all other components of $G-\partial(G)$ but $G_{s}$. Set
$|V(G_{s})|=s$ and $|V(G_{t})|=t$. Then $s+t+\kappa=n$. Connect respectively
all pairs of vertices which are not adjacent in $G_{s}$, $G_{t}$ and
$\partial(G)$, and connect respectively all pairs of vertices which are not
adjacent between $G_{s}$ and $\partial(G)$ and all pairs of vertices which are
not adjacent between $\partial(G)$ and $G_{t}$ but v. Then we obtain the
resulting graph $B(s,t,\kappa)$.

Lemma 3.2. Let $G\in\mathbb{G}_{n,\kappa}$. If $d(G)\geq 3$, then we have
$\lambda_{1}(G^{c})\geq\lambda_{1}(B^{c}(s,t,\kappa))$.

Proof. Set $x=(x_{1},x_{2},\cdots,x_{n})^{T}$ to be the unit Perron vector of
$A(B^{c}(s,t,\kappa))$ with respect to $\lambda_{1}(B^{c}(s,t,\kappa))$. From
the equation $(1)$, we can get $x^{T}A(G)x=\sum_{v_{i}v_{j}\in
E(G)}2x_{i}x_{j}\leq\sum_{v_{i}v_{j}\in
E(B(s,t,\kappa))}2x_{i}x_{j}=x^{T}A(B(s,t,\kappa))x$. Then we have

$\begin{split}\lambda_{1}(G^{c})&\geq x^{T}A(G^{c})x\\\
&=x^{T}(J_{n}-I_{n})x-x^{T}A(G)x\\\ &\geq
x^{T}(J_{n}-I_{n})x-x^{T}A(B(s,t,\kappa))x\\\ &=x^{T}A(B^{c}(s,t,\kappa))x\\\
&=\lambda_{1}(B^{c}(s,t,\kappa)).\end{split}$

Therefore, we have $\lambda_{1}(G^{c})\geq\lambda_{1}(B^{c}(s,t,\kappa))$.
$\Box$

Lemma 3.3.
$\lambda_{1}(B^{c}(s,t,\kappa))>\lambda_{1}(B^{c}(1,n-\kappa-1,\kappa))$.

Proof. Assume without loss of generality that $s<t+1$. Set
$x=(x_{1},x_{2},\cdots,x_{n})^{T}$ to be the unit Perron vector of
$A(B^{c}(s,t,\kappa))$ with respect to $\lambda_{1}(B^{c}(s,t,\kappa))$. We
write $\lambda_{1}(B^{c}(s,t,\kappa))$ as $\lambda_{1}$ for short. By the
symmetry of $B^{c}(s,t,\kappa)$, all the vertices in $V(G_{s})$ correspond to
the same value $x_{s}$, all the vertices in $V(G_{t})\setminus\\{v\\}$
correspond to the same value $x_{t}$, and all the vertices in $\partial(G)$
correspond to the same value $x_{\kappa}$. From the equation $(2)$, we have

$\left\\{\begin{array}[]{l}\lambda_{1}x_{s}=(t-1)x_{t}+x_{v},\\\
\lambda_{1}x_{t}=sx_{s},\\\ \lambda_{1}x_{\kappa}=x_{v},\\\
\lambda_{1}x_{v}=sx_{s}+\kappa x_{\kappa}.\\\ \end{array}\right.$

Then transform the above equations into a matrix equation
$(A_{s,t}-\lambda_{1}I_{4})\widetilde{x}=0$, where
$\widetilde{x}=(x_{s},x_{t},x_{\kappa},x_{v})^{T}$ and

$A_{s,t}=\left(\begin{matrix}0&t-1&0&1\\\ s&0&0&0\\\ 0&0&0&1\\\
s&0&\kappa&0\\\ \end{matrix}\right).$

Let $f_{s,t}(\lambda)=\det(A_{s,t}-\lambda I_{4})$. We can compute out

$\begin{split}f_{s,t}(\lambda)=\lambda^{4}-(\kappa+st)\lambda^{2}+\kappa
s(t-1).\end{split}$

Therefore, we can compute out

$\begin{split}f_{s,t}(\lambda)-f_{s-1,t+1}(\lambda)=(s-t-1)\lambda^{2}-\kappa(s-t),\end{split}$

whose maximum root is $\theta=\sqrt{\kappa(1+\frac{1}{s-t-1})}$.

We compute out
$\sigma(B^{c}(s,t,\kappa))=\kappa^{2}+(2s+3t-3)\kappa+s^{2}+t^{2}+st-s-t$. By
Lemma 2.2 we have

$\begin{split}\lambda_{1}\geq\frac{2(\kappa^{2}+2s\kappa+3t\kappa-3\kappa+s^{2}+t^{2}+st-
s-t)}{s+t+\kappa}.\end{split}$

Then

$\begin{split}\lambda_{1}-\theta&>\lambda_{1}-\sqrt{\kappa}\\\
&=\frac{h(s,t)}{s+t+\kappa},\end{split}$

where
$h(s,t)=2\kappa^{2}+2(2s+3t-3)\kappa+2s^{2}+2t^{2}+2st-2s-2t-s\sqrt{\kappa}-t\sqrt{\kappa}-\kappa\sqrt{\kappa}$.
Clearly, $h(s,t)>0$, and so $\lambda_{1}>\theta$.

Recall $s<t+1$. We have $f_{s,t}(\lambda_{1})-f_{s-1,t+1}(\lambda_{1})<0$, and
so $f_{s-1,t+1}(\lambda_{1})>0$. Note that $f_{s,t}(\lambda)$ increases
monotonically on $\lambda\geq\sqrt{\frac{\kappa+st}{2}}$, and
$f_{s,t}(\sqrt{\frac{\kappa+st}{2}})<0$ and that $f_{s-1,t+1}(\lambda)$
increases monotonically on $\lambda\geq\sqrt{\frac{\kappa+st+s-t-1}{2}}$, and
$f_{s-1,t+1}(\sqrt{\frac{\kappa+st+s-t-1}{2}})<0$. We can observe
$\lambda_{1}>\sqrt{\frac{\kappa+st}{2}}>\sqrt{\frac{\kappa+st+s-t-1}{2}}$, and
so $\lambda_{1}>\lambda_{1}(B^{c}(s-1,t+1,\kappa))$. This shows
$\lambda_{1}(B^{c}(s,t,\kappa))>\lambda_{1}(B^{c}(1,n-\kappa-1,\kappa))$.
$\Box$

From Lemmas 3.2 and 3.3 we can easily see that the following result is true.
Theorem 3.4. Let $G\in\mathbb{G}_{n,\kappa}$. If $d(G)\geq 3$, then
$\lambda_{1}(G^{c})>\lambda_{1}(B^{c}(1,n-\kappa-1,\kappa))$.

##  4\. The least eigenvalue of the complements of graphs with given
connectivity

Let $K_{n_{1}}$ and $K_{n_{2}}$ be two complete graphs of orders $n_{1}$ and
$n_{2}$, respectively, where $n_{1}+n_{2}=n$. Let $k$ be an integer number
satisfying $n_{1}+n_{2}>2k$ and $n_{i}\geq k$ ($i=1,2$). We denote by
$\mathbb{B}(n_{1},n_{2};k)$ the graph obtained from $K_{n_{1}}$ and
$K_{n_{2}}$ by connecting $k$ vertices of $K_{n_{1}}$ and ones of $K_{n_{2}}$.
Clearly, $\mathbb{B}(n_{1},n_{2};k)\in\mathbb{G}_{n,\kappa}$.

Lemma 4.1. Among all complements of $\mathbb{G}_{n,\kappa}$, the minimum least
eigenvalue is obtained at $\mathbb{B}^{c}(n_{1},n_{2};\kappa)$.

Proof. Let $G\in\mathbb{G}_{n,\kappa}$ be such a graph that
$\lambda_{n}(G^{c})$ attains the minimum value in $\mathbb{G}_{n,\kappa}^{c}$.
Let $\partial(G)$ be a minimum vertex-cut of $G$. Then $|\partial(G)|=\kappa$.
Set $x=(x_{1},\cdots,x_{n})^{T}$ to be a unit eigenvector of $A(G^{c})$ with
respect to $\lambda_{n}(G^{c})$. Denote by $\partial(G)^{+}=\\{v:x(v)\geq
0,v\in\partial(G)\\}$, $\partial(G)^{-}=\\{v:x(v)<0,v\in\partial(G)\\}$. We
now by some claims to characterize the graph $G$.

Claim 1. $G-\partial(G)$ contains exactly two components $G_{1}$ and $G_{2}$.

Proof. Suppose on the contrary that $G-\partial(G)$ contains three components
$G_{1}$, $G_{2}$ and $G_{3}$. Then we can choose two vertices $u\in V(G_{1})$
and $v\in V(G_{2})$ such that $x(u)x(v)>0$. Let $H_{1}=G+uv$. Clearly,
$H_{1}\in\mathbb{G}_{n,\kappa}$. From the equation $(1)$, we have
$x^{T}A(G)x=\sum_{v_{i}v_{j}\in E(G)}2x_{i}x_{j}<\sum_{v_{i}v_{j}\in
E(H_{1})}2x_{i}x_{j}=x^{T}A(H_{1})x$.

Thus we have

$\begin{split}\lambda_{n}(G^{c})&=x^{T}A(G^{c})x\\\
&=x^{T}(J_{n}-I_{n})x-x^{T}A(G)x\\\ &>x^{T}(J_{n}-I_{n})x-x^{T}A(H_{1})x\\\
&=x^{T}A(H_{1}^{c})x\\\ &\geq\lambda_{n}(H_{1}^{c}).\end{split}$

This contradicts the minimality of $G^{c}$, and so Claim 1 is true. $\Box$

Denote by $G_{i}^{+}=\\{v:x(v)\geq 0,v\in V(G_{i})\\}$,
$G_{i}^{-}=\\{v:x(v)<0,v\in V(G_{i})\\}$, where $i=1,2$. Assume $S$ is a non-
empty subset of $V(G)$. We denote by $G[S]$ the subgraph induced by $S$.

Claim 2. $G[G_{1}^{+}\cup\partial(G)^{+}]$, $G[G_{2}^{+}\cup\partial(G)^{+}]$,
$G[G_{1}^{-}\cup\partial(G)^{-}]$ and $G[G_{2}^{-}\cup\partial(G)^{-}]$ are
all complete graphs.

Proof. Suppose on the contrary that the vertices $u$ and $v$ are not adjacent
in $G[G_{1}^{+}\cup\partial(G)^{+}]$. Let $H_{2}=G+uv$ and the connectivity of
$H_{2}$ be $\kappa^{*}$. Clearly, $\kappa^{*}\geq\kappa$. Note that
$\partial(G)$ is also $\kappa$-vertex cut of $H_{2}$, and so
$\kappa^{*}=\kappa$. From the equation $(1)$, $x^{T}A(G)x=\sum_{v_{i}v_{j}\in
E(G)}2x_{i}x_{j}\leq\sum_{v_{i}v_{j}\in E(H_{2})}2x_{i}x_{j}=x^{T}A(H_{2})x$.
If $x(u)x(v)=0$ then as in the proof of Claim 1, we can verify
$\lambda_{n}(G^{c})=\lambda_{n}(H_{2}^{c})$. In this case we can consider $G$
as $H_{2}$. If $x(u)x(v)>0$ then $\lambda_{n}(G^{c})>\lambda_{n}(H_{2}^{c})$.
This contradicts the minimality of $G^{c}$. Therefore,
$G[G_{1}^{+}\cup\partial(G)^{+}]$ is complete graph.

Similarly, $G[G_{2}^{+}\cup\partial(G)^{+}]$,
$G[G_{1}^{-}\cup\partial(G)^{-}]$ and $G[G_{2}^{-}\cup\partial(G)^{-}]$ are
also complete graphs. $\Box$

Claim 3. There exists no edge between $\partial(G)^{+}$ and $\partial(G)^{-}$.

Proof. Suppose on the contrary that there exist one edge $uv$ between
$\partial(G)^{+}$ and $\partial(G)^{-}$. Clearly,
$H_{3}=G-uv\in\mathbb{G}_{n,\kappa}$. From the equation $(1)$,
$x^{T}A(G)x=\sum_{v_{i}v_{j}\in E(G)}2x_{i}x_{j}\leq\sum_{v_{i}v_{j}\in
E(H_{3})}2x_{i}x_{j}=x^{T}A(H_{3})x$. If $x(u)x(v)=0$ then as in the proof of
Claim 1, we can verify $\lambda_{n}(G^{c})=\lambda_{n}(H_{3}^{c})$. In this
case we can consider $G$ as $H_{3}$. If $x(u)x(v)<0$ then
$\lambda_{n}(G^{c})>\lambda_{n}(H_{3}^{c})$. This contradicts the minimality
of $G^{c}$, and so Claim 3 is true. $\Box$

Claim 4. If $w\in G_{1}^{+}\cup G_{2}^{+}$ (or $G_{1}^{-}\cup G_{2}^{-}$) then
there exists at most one vertex in $\partial(G)^{-}$ (or $\partial(G)^{+}$)
which is adjacent to $w$.

Proof. Suppose on the contrary that there exist two edges $uw$ and $vw$, where
$u,v\in\partial(G)^{-}$. Clearly, $H_{4}=G-uw\in\mathbb{G}_{n,\kappa}$. From
the equation $(1)$, $x^{T}A(G)x=\sum_{v_{i}v_{j}\in
E(G)}2x_{i}x_{j}\leq\sum_{v_{i}v_{j}\in E(H_{4})}2x_{i}x_{j}=x^{T}A(H_{4})x$.
As in the proof of Claim $3$, we can verify Claim 4 is true. $\Box$

Denote by $G^{+}=\\{v:x(v)\geq 0,v\in V(G)\\}$, $G^{-}=\\{v:x(v)<0,v\in
V(G)\\}$.

Claim 5. There are at least $\kappa$ pairs of vertices which are adjacent
between $G^{+}$ and $G^{-}$.

Proof. It is clear that if $w\in\partial(G)^{-}$ (or $\partial(G)^{+}$) then
there exist at least one vertex in $G_{1}^{+}\cup G_{2}^{+}$ (or
$G_{1}^{-}\cup G_{2}^{-}$) which is adjacent to $w$. According to Claim $4$,
if $w_{1}$ and $w_{2}$ are two distinct vertices of $\partial(G)^{-}$ (or
$\partial(G)^{+}$) then they have no common neighbour in $G_{1}^{+}\cup
G_{2}^{+}$ (or $G_{1}^{-}\cup G_{2}^{-}$). This implies that Claim $5$ is
true. $\Box$

Delete some edges between $G^{+}$ and $G^{-}$ so that only $\kappa$ pairs of
vertices are adjacent between $G^{+}$ and $G^{-}$. Connect respectively all
pairs between $G_{1}^{+}$ and $G_{2}^{+}$ and between $G_{1}^{-}$ and
$G_{2}^{-}$. Then we obtain the resulting graph
$\mathbb{B}(n_{1},n_{2};\kappa)$, where $|G^{+}|=n_{1}$ and $|G^{-}|=n_{2}$.
From the equation $(1)$, $x^{T}A(G)x=\sum_{v_{i}v_{j}\in
E(G)}2x_{i}x_{j}\leq\sum_{v_{i}v_{j}\in
E(\mathbb{B}(n_{1},n_{2};\kappa))}2x_{i}x_{j}=x^{T}A(\mathbb{B}(n_{1},n_{2};\kappa))x$.
As in the proof of Claim $1$, we can verify
$\lambda_{n}(G^{c})\geq\lambda_{n}((\mathbb{B}^{c}(n_{1},n_{2};\kappa)))$.
From the minimality of $G^{c}$, we can determine that
$\lambda_{n}(G^{c})=\lambda_{n}((\mathbb{B}^{c}(n_{1},n_{2};\kappa)))$. $\Box$

Lemma 4.2.
$\lambda_{n}({\mathbb{B}}^{c}(n_{1},n_{2},\kappa))>\lambda_{n}({\mathbb{B}}^{c}(\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor,\kappa))$.

Proof. Assume without loss of generality that $n_{1}>n_{2}+1$. Suppose that
$U\subseteq V(K_{n_{1}})$ is a vertex cut of
${\mathbb{B}}(n_{1},n_{2},\kappa)$, and that $W\subseteq V(K_{n_{2}})$ is a
set composed of those vertices which are adjacent to the vertices in $U$. Let
$x=(x_{1},x_{2},\cdots,x_{n})^{T}$ be a unit eigenvector of
${\mathbb{B}}^{c}(n_{1},n_{2},\kappa)$ with respect to
$\lambda_{n}({\mathbb{B}}^{c}(n_{1},n_{2},\kappa))$. By the symmetry of
${\mathbb{B}}^{c}(n_{1},n_{2},\kappa)$, all the vertices in
$V(K_{n_{1}})\setminus U$ correspond to the same value $x_{1}$, all the
vertices in $U$ correspond to the same value $x_{2}$, all the vertices in
$V(K_{n_{2}})\setminus W$ correspond to the same value $x_{3}$, and all the
vertices in $W$ correspond to the same value $x_{4}$. From the equation $(2)$,
we have

$\left\\{\begin{array}[]{l}\lambda_{n}x_{1}=(n_{2}-\kappa)x_{3}+\kappa
x_{4},\\\ \lambda_{n}x_{2}=(n_{2}-\kappa)x_{3},\\\
\lambda_{n}x_{3}=(n_{1}-\kappa)x_{1}+\kappa x_{2},\\\
\lambda_{n}x_{4}=(n_{1}-\kappa)x_{1}.\\\ \end{array}\right.$

Then transform the above equations into a matrix equation
$(A_{n_{1},n_{2}}-\lambda_{n}I_{4})\widetilde{x}=0$, where
$\widetilde{x}=(x_{1},x_{2},x_{3},x_{4})^{T}$ and

$A_{n_{1},n_{2}}=\left(\begin{matrix}0&0&n_{2}-\kappa&\kappa\\\
0&0&n_{2}-\kappa&0\\\ n_{1}-\kappa&\kappa&0&0\\\ n_{1}-\kappa&0&0&0\\\
\end{matrix}\right).$

Let $g_{n_{1},n_{2}}(\lambda)=\det(A_{n_{1},n_{2}}-\lambda I_{4})$. We can
compute out

$\begin{split}g_{n_{1},n_{2}}(\lambda)=\lambda^{4}+(\kappa^{2}-n_{1}n_{2})\lambda^{2}+\kappa^{4}-(n_{1}+n_{2})\kappa^{3}+n_{1}n_{2}\kappa^{2}.\end{split}$

Therefore, we can compute out

$\begin{split}g_{n_{1},n_{2}}(\lambda)-g_{n_{1}-1,n_{2}+1}(\lambda)=(n_{1}-n_{2}-1)(\lambda^{2}-\kappa^{2}),\end{split}$

whose minimum root is $\alpha=-\kappa$.

We compute out
$\sigma({\mathbb{B}}^{c}(n_{1},n_{2},\kappa))=n_{1}^{2}+n_{2}^{2}+n_{1}n_{2}-n_{1}-n_{2}+2\kappa^{2}$.
By Lemma 2.2 we have

$\begin{split}\lambda_{1}({\mathbb{B}}^{c}(n_{1},n_{2},\kappa))\geq\frac{2(n_{1}^{2}+n_{2}^{2}+n_{1}n_{2}-n_{1}-n_{2}+2\kappa^{2})}{n_{1}+n_{2}}.\end{split}$

Clearly, the graph ${\mathbb{B}}^{c}(n_{1},n_{2},\kappa)$ is bipartite. Then

$\begin{split}\alpha-\lambda_{n}({\mathbb{B}}^{c}(n_{1},n_{2},\kappa))&=\alpha+\lambda_{1}({\mathbb{B}}^{c}(n_{1},n_{2},\kappa))\\\
&\geq\frac{h(n_{1},n_{2})}{n_{1}+n_{2}},\end{split}$

where
$h(n_{1},n_{2})=2n_{1}^{2}+2n_{2}^{2}+2n_{1}n_{2}-2(n_{1}+n_{2})+4\kappa^{2}-(n_{1}+n_{2})\kappa$.
Clearly, $h(n_{1},n_{2})>0$, and so
$\alpha>\lambda_{n}({\mathbb{B}}^{c}(n_{1},n_{2},\kappa))$.

Recall $n_{1}>n_{2}+1$. We have
$g_{n_{1},n_{2}}(\lambda_{n}({\mathbb{B}}^{c}(n_{1},n_{2},\kappa)))-g_{n_{1}-1,n_{2}+1}(\lambda_{n}({\mathbb{B}}^{c}(n_{1},n_{2},\kappa)))>0$,
and so
$g_{n_{1}-1,n_{2}+1}(\lambda_{n}({\mathbb{B}}^{c}(n_{1},n_{2},\kappa)))<0$.
Note that the function $g_{n_{1}-1,n_{2}+1}(\lambda)$ monotonically decreases
when $\lambda<-\sqrt{n_{1}n_{2}+n_{1}-n_{2}-1-k^{2}}$ and increases when
$-\sqrt{n_{1}n_{2}+n_{1}-n_{2}-1-k^{2}}<\lambda<0$, and so
$\lambda_{n}({\mathbb{B}}^{c}(n_{1},n_{2},\kappa))>\lambda_{n}({\mathbb{B}}^{c}(n_{1}-1,n_{2}+1,\kappa))$.
This shows
$\lambda_{n}({\mathbb{B}}^{c}(n_{1},n_{2},\kappa))>\lambda_{n}({\mathbb{B}}^{c}(\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor,\kappa))$.
$\Box$

From Lemmas 4.1 and 4.2 we can easily see that the following result is true.

Theorem 4.3. Let $G\in\mathbb{G}_{n,\kappa}$, then we have
$\lambda_{n}(G^{c})>\lambda_{n}({\mathbb{B}}^{c}(\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor,\kappa))$.

## References

  * [1] X. Chen, G. Wang, The distance spectrum of the complements of graphs of diameter greater than three, Indian Journal Pure and Applied Mathematical, DOI: 10.1007/s13226-022-00315-9.
  * [2] X. Chen, G. Wang, The distance spectrum of the complements of graphs with two pendent vertices, Indian Journal Pure and Applied Mathematical, DOI: 10.1007/s13226-022-00322-w.
  * [3] Y. Fan, F. Zhang, Y. Wang, The least eigenvalue of the complements of trees, Linear Algebra and its Applications 435 (2011) 2150-2155.
  * [4] H. Lin, S. Drury, On the distance spectrum of complements of trees, Linear Algebra and its Applications 530 (2017) 185-201.
  * [5] S. Li, S. Wang, The least eigenvalue of the signless Laplacian of the complements of trees, Linear Algebra and its Applications 436 (2012) 2398-2405.
  * [6] G. Jiang, G. Yu, W. Sun, Z. Ruan, The least eigenvalue of graphs whose complements have only two pendent vertices, Applied Mathematics and Computation 331 (2018) 112-119.
  * [7] R. Qin, D. Li, Y. Chen, J. Meng, The distance eigenvalues of the complements of unicyclic graphs, Linear Algebra and its Applications 598 (2020) 49-67.
  * [8] R. Xing, B. Zhou, J. Li, On the distance signless Laplacian spectral radius of graphs, Linear and Multilinear Algebra 62 (2014) 49-67.
  * [9] G. Yu, Y. Fan, M. Ye, The least signless Laplacian eigenvalue of the complements of unicyclic graphs, Applied Mathematics and Computation 306 (2017) 13-21.