# Symmetric Nonnegative Trifactorization of Pattern Matrices

Damjana Kokol Bukovšek  Helena Šmigoc

###### Abstract

A factorization of an $n\times n$ nonnegative symmetric matrix $A$ of the form
$BCB^{T}$, where $C$ is a $k\times k$ symmetric matrix, and both $B$ and $C$
are required to be nonnegative, is called the Symmetric Nonnegative Matrix
Trifactorization (SN-Trifactorization). The SNT-rank of $A$ is the minimal $k$
for which such factorization exists. The SNT-rank of a simple graph $G$ that
allows loops is defined to be the minimal possible SNT-rank of all symmetric
nonnegative matrices whose zero-nonzero pattern is prescribed by a given
graph.

We define set-join covers of graphs, and show that finding the SNT-rank of $G$
is equivalent to finding the minimal order of a set-join cover of $G$. Using
this insight we develop basic properties of the SNT-rank for graphs and
compute it for trees and cycles without loops. We show the equivalence between
the SNT-rank for complete graphs and the Katona problem, and discuss
uniqueness of patterns of matrices in the factorization.

###### keywords:

Nonnegative Matrix Factorization; Nonnegative Symmetric Matrices; Symmetric
Nonnegative Trifactorization; Pattern Matrices

###### MSC:

[2020] 15A23 , 15B48

[inst1]organization=University of Ljubljana, School of Economics and Business,
country=Slovenia [inst2]organization=Institute of Mathematics Physics and
Mechanics, city=Ljubljana, country=Slovenia

[inst3]organization=School of Mathematics and Statistics, University College
Dublin, country=Ireland

##  1 Introduction and Notation

Factorizations of matrices where the factors are required to be entry-wise
nonnegative provide a powerful tool in analysing nonnegative data. In this
paper we consider a factorization of nonnegative symmetric matrices, which
takes into account symmetry, nonnegativity and low rank of a matrix.

Denote by $\mathbb{R}_{+}$ the set of nonnegative real numbers, by
$\mathbb{R}^{n\times m}$ the set of $n\times m$ real matrices, and by
$\mathbb{R}_{+}^{n\times m}$ the set of $n\times m$ entry-wise nonnegative
matrices. Furthermore, we denote

$\mathcal{S}_{n}^{+}=\\{A\in\mathbb{R}_{+}^{n\times n};A=A^{T}\\}.$

######  Definition 1.1.

A factorization of $A\in\mathcal{S}_{n}^{+}$ of the form $BCB^{T}$, where
$B\in\mathbb{R}_{+}^{n\times k}$ and $C\in\mathcal{S}_{k}^{+}$, is called
_Symmetric Nonnegative Trifactorization_ of $A$ (_SN-Trifactorization_ for
short). Minimal possible $k$ in such factorization is called the _SNT-rank_ of
$A$, and is denoted by $\mathrm{st}_{+}(A)$.

The SN-Trifactorization was studied in [7], and is closely related to two
other well known factorizations that feature nonnegative factors: Nonnegative
Matrix Factorization and Completely Positive Factorization. We refer the
reader to [4] for the background on the Nonnegative Matrix Factorization and
to [1] for the background on the Completely Positive Factorization.

The zero-nonzero pattern of a nonnegative matrix $A\in\mathcal{S}_{n}^{+}$
poses constrains on the zero-nonzero pattern of nonnegative matrices
$B\in\mathbb{R}_{+}^{n\times k}$ and $C\in\mathcal{S}_{k}^{+}$ satisfying
$A=BCB^{T}$. The aim of this paper is to better understand those restrictions.

In the context of matrix patterns, graphs arise naturally. In this work, a
graph $G=(V(G),E(G))$ will always be a simple undirected graph that allows
loops. Hence, $E(G)\subseteq\\{\\{i,j\\};i,j\in V(G)\\}$, where $\\{i\\}\in
E(G)$ corresponds to a loop on the vertex $i$ in $G$. A vertex $i\in V(G)$ is
_isolated_ , if $\\{i,j\\}\not\in E(G)$ for all $j\in V(G)$. In particular,
$i$ does not have a loop. The vertex set $V(G)$ will often be
$[n]:=\\{1,2,\ldots,n\\}$.

Let $G$ and $H$ be two simple graphs that allow loops. We denote by $G\cup H$
their disjoint union, by $tG$ the union of $t$ copies of $G$ and by $G\vee H$
the join of $G$ and $H$, i.e. the graph with $V(G\vee H)=V(G)\cup V(H)$ and
$E(G\vee H)=E(G)\cup E(H)\cup\\{\\{i,j\\}~{}|~{}i\in V(G),j\in V(H)\\}$. We
use standard notation for graphs without any loops: we denote by $K_{n}$ the
complete graph on $n$ vertices, by $K_{m,n}$ the bipartite graph on $m+n$
vertices, by $P_{n}$ the path, and by $C_{n}$ the cycle on $n$ vertices. We
denote by $K^{\ell}_{n}$ the complete graph on $n$ vertices with all possible
loops.

We denote matrices by capital letters, $A\in\mathbb{R}^{n\times m}$, vectors
by bold letters, ${\bf a}\in\mathbb{R}^{n}$, the zero matrix in
$\mathbb{R}^{n\times m}$ by $0_{n\times m}$ and the zero vector in
$\mathbb{R}^{n}$ by ${\bf 0}_{n}$.

Let $A,B\in\mathbb{R}^{n\times m}$. Then $A>B$ means that $A-B$ is entry-wise
positive, and $A\geq B$ denotes entry-wise nonnegativity of $A-B$. _The
support_ of a vector ${\bf a}\in\mathbb{R}^{n}$ is the set of all indices in
$i\in[n]$ for which $a_{i}\neq 0$. For $A\in\mathbb{R}^{n\times m}$ and
$\mathcal{S}\subset[n],\mathcal{T}\subset[m]$, we denote by
$A[\mathcal{S},\mathcal{T}]$ the submatrix of $A$ containing entries $a_{ij}$
for all $i\in\mathcal{S},j\in\mathcal{T}$.

After a brief introduction and development of notation in Section 1, we
dedicate Section 2 to the definition of the SNT-rank and set-join covers of
simple graphs that allow loops. We prove that finding the SNT-rank of a graph
$G$ is equivalent to determining minimal order of the set-join cover of $G$.
Using this insight we develop basic properties of SNT-rank of graphs. We
conclude Section 2 by defining uniqueness of optimal set-join covers of
graphs. In Section 3 we find the SNT-rank of trees without loops and consider
the unicyclic graphs without loops. Section 4 is dedicated to the SNT-rank and
optimal set-join covers of complete graphs without loops. Section 5 offers a
selection of possible applications and further research directions motivated
by the work in this paper.

##  2 Set-join covers and $\mathrm{st}_{+}(G)$

In this work we will for the most part take aside the actual values of
matrices and only consider their patterns. Our main focus will be the
question, how small can $\mathrm{st}_{+}(A)$ be among all matrices $A$ with a
given zero-nonzero pattern.

###  2.1 Setup

We begin by defining $\mathrm{st}_{+}(G)$ for a graph $G$, and developing a
combinatorial question that is equivalent to finding $\mathrm{st}_{+}(G)$.

######  Definition 2.1.

Let $A\in\mathbb{R}_{+}^{n\times m}$. The _pattern matrix_ of $A$ is the
matrix $\mathrm{sign}(A)\in\\{0,1\\}^{n\times m}$ defined by

$\mathrm{sign}(A)_{ij}=\begin{cases}1;&\mbox{if }a_{ij}>0,\\\ 0;&\mbox{if
}a_{ij}=0.\end{cases}$

(The pattern matrix is in some literature called _the derangement matrix_.)

######  Definition 2.2.

_The pattern graph_ $G(A)=(V(G),E(G))$ of a matrix $A\in{\mathcal{S}}_{n}^{+}$
is defined by $V(G)=[n]$, and $\\{i,j\\}\in E(G)$ precisely when $a_{ij}>0$.

Let $G$ be a graph with $|V(G)|=n$. By $\mathcal{S}^{+}(G)$ we denote the set
of all matrices in $\mathcal{S}^{+}_{n}$ with the pattern graph $G$, and ask
the question how small can the SNT-rank be on this set.

######  Definition 2.3.

Let $G=(V(G),E(G))$ be a simple graph with loops. We define:
$\mathrm{st}_{+}(G):=\min\\{\mathrm{st}_{+}(A);A\in\mathcal{S}^{+}(G)\\}$.

######  Remark 2.4.

A factorization of $A\in\mathbb{R}_{+}^{n\times m}$ of the form $UV^{T}$,
where $U\in\mathbb{R}_{+}^{n\times k}$ and $V\in\mathbb{R}_{+}^{m\times k}$,
is called Nonnegative Matrix Factorization of $A$. Minimal possible $k$ in
such factorization is called the NMF-rank of $A$, and is denoted by
$\mathrm{rk}_{+}(A)$ (see [4]). In this context also Boolean rank is studied.
It is defined as

$\mathrm{rk}_{01}(A)=\min\\{\mathrm{rk}_{+}(B);B\in\mathbb{R}_{+}^{n\times
m},\mathrm{sign}(B)=\mathrm{sign}(A)\\}.$

It is easy to see that Boolean rank is equal to rectangle covering bound, i.e.
the minimum number of rectangles needed to cover all nonzero entries in $A$
(see [4]).

We proceed to develop basic properties of $\mathrm{st}_{+}(G)$. We start with
a simple proposition which follows from the property that for
$A\in\mathcal{S}_{n}^{+},B\in\mathcal{S}_{m}^{+}$ we have
$\mathrm{st}_{+}(A\oplus B)=\mathrm{st}_{+}(A)+\mathrm{st}_{+}(B)$, see [7].

######  Proposition 2.5.

For any graphs $G,H$ we have $\mathrm{st}_{+}(G\cup
H)=\mathrm{st}_{+}(G)+\mathrm{st}_{+}(H)$. In particular,
$\mathrm{st}_{+}(G\cup K_{1})=\mathrm{st}_{+}(G)$ as
$\mathrm{st}_{+}(K_{1})=0$.

The next result connects the patterns of nonnegative matrices $A$, $B$ and
$C$, provided $A=BCB^{T}$.

######  Proposition 2.6.

Let $A=BCB^{T}$ be SN-Trifactorization of $A=(a_{ij})\in\mathcal{S}_{n}^{+}$.
For $i\in[n]$ let $r_{i}(B)^{T}\in\mathbb{R}^{1\times k}$ be the $i$-th row of
$B$, and $\mathcal{R}_{i}\subseteq\\{1,\ldots,k\\}$ the support of $r_{i}(B)$,
i.e. $\mathcal{R}_{i}:=\\{j;(r_{i}(B))_{j}\neq 0\\}$. Then
$C[\mathcal{R}_{i},\mathcal{R}_{j}]=0$ if and only if $a_{ij}=0$.

###### Proof.

Since
$a_{ij}=r_{i}(B)^{T}Cr_{j}(B)=(r_{i}(B)[\mathcal{R}_{i}])^{T}C[\mathcal{R}_{i},\mathcal{R}_{j}](r_{j}(B)[\mathcal{R}_{j}])$,
and $r_{s}(B)[\mathcal{R}_{s}]>0$ by the definition of $\mathcal{R}_{s}$, the
conclusion follows. ∎

Note that $\mathrm{sign}(B)$ in Proposition 2.6 is the incidence matrix of
${\bf R}=(\mathcal{R}_{1},\ldots,\mathcal{R}_{n})$. We recall the definition
of the incidence matrix below.

######  Definition 2.7.

Let ${\bf R}=(\mathcal{R}_{1},\ldots,\mathcal{R}_{n})$ be a list of sets
$\mathcal{R}_{i}\subseteq\\{1,\ldots,k\\}$. _The incidence matrix_ of ${\bf
R}$ is an $n\times k$ matrix $\iota({\bf R})$ with

$\iota({\bf R})_{ij}=\begin{cases}1;&j\in\mathcal{R}_{i},\\\
0;&j\not\in\mathcal{R}_{i}.\end{cases}$

Since $\mathrm{st}_{+}(G)$ is a parameter of the graph $G$, we would like to
determine it directly from $G$. For this we need to introduce the set-join and
the set-join cover.

######  Definition 2.8.

Let $\mathcal{S}$ be a finite set and $\mathcal{K},\mathcal{L}$ two nonempty
subsets of $\mathcal{S}$ with possibly nonempty intersection. We define _the
set-join of $\mathcal{K}$ and $\mathcal{L}$ on $\mathcal{S}$_, denoted by
$\mathcal{K}\vee_{\mathcal{S}}\mathcal{L}$, to be the graph with
$V(\mathcal{K}\vee_{\mathcal{S}}\mathcal{L})=\mathcal{S}$, and
$E(\mathcal{K}\vee_{\mathcal{S}}\mathcal{L})=\\{\\{i,j\\};i\in\mathcal{K},j\in\mathcal{L}\\}$.

Note that $\mathcal{K}\vee_{\mathcal{S}}\mathcal{L}$ has a loop on vertex $i$
precisely when $i\in\mathcal{K}\cap\mathcal{L}$, and that if
$\mathcal{K}\cup\mathcal{L}\neq\mathcal{S}$, then
$\mathcal{K}\vee_{\mathcal{S}}\mathcal{L}$ contains some isolated vertices
without loops.

######  Definition 2.9.

Let $G$ be a graph and $\mathcal{K}_{i},\mathcal{L}_{i}\subseteq V(G)$. We say
that

$\mathscr{C}=\\{\mathcal{K}_{i}\vee_{V(G)}\mathcal{L}_{i},i\in[t]\\}$

is _a set-join cover_ of $G$ if
$E(G)=\bigcup_{i=1}^{t}E(\mathcal{K}_{i}\vee_{V(G)}\mathcal{L}_{i})$.

For a set-join cover $\mathscr{C}$ we define:

  * •

_the component set_ of $\mathscr{C}$ to be:

$V(\mathscr{C})=\\{\mathcal{K}_{i};i\in[t]\\}\cup\\{\mathcal{L}_{i};i\in[t]\\},$

  * •

_the order_ of $\mathscr{C}$ to be $|\mathscr{C}|=|V(\mathscr{C})|$,

  * •

_the graph_ of $\mathscr{C}$ denoted by $G(\mathscr{C})$ to be a graph with
$V(G(\mathscr{C}))=V(\mathscr{C})$ and
$\\{\mathcal{K}_{i},\mathcal{K}_{j}\\}\in E(G(\mathscr{C}))$ if and only if
$\mathcal{K}_{i}\vee_{V(G)}\mathcal{K}_{j}\in\mathscr{C}$.

Note that in the above definition we allow $\mathcal{K}_{i}=\mathcal{K}_{j}$
or $\mathcal{K}_{i}=\mathcal{L}_{j}$, so $|\mathscr{C}|$ can be smaller than
$2t$, and can in the extreme case even be equal to $1$.

######  Definition 2.10.

Let $G$ be graph with a set-join cover $\mathscr{C}$, and
$\mathcal{S}\subseteq V(G)$. _The restriction of $\mathscr{C}$ to
$\mathcal{S}$_ is the set

$\mathscr{C}[\mathcal{S}]=\\{(\mathcal{K}\cap\mathcal{S})\vee_{V(G)\cap\mathcal{S}}(\mathcal{L}\cap\mathcal{S});\mathcal{K}\vee_{V(G)}\mathcal{L}\in\mathscr{C},\mathcal{K}\cap\mathcal{S}\not=\emptyset,\mathcal{L}\cap\mathcal{S}\not=\emptyset\\}.$

In the definition above, $\mathscr{C}[\mathcal{S}]$ is a set-join cover of a
subgraph of $G$ induced on $V(G)\cap\mathcal{S}$ that satisfies
$|\mathscr{C}[\mathcal{S}]|\leq|\mathscr{C}|$ .

######  Theorem 2.11.

Let $G$ be a graph. Then
$\mathrm{st}_{+}(G)=\min\\{|\mathscr{C}|;\,\mathscr{C}$ a set-join cover of
$G\\}$.

###### Proof.

Let $G$ be a graph with $V(G)=[n]$, and $A\in\mathcal{S}^{+}(G)$ with SN-
Trifactorization $A=BCB^{T}$, where $C\in\mathcal{S}_{k}^{+}$. For $i\in[k]$,
let $c_{i}(B)$ be the $i$-th column of $B$, and $\mathcal{L}_{i}$ the support
of the $c_{i}(B)$. Clearly,
$c_{i}(B)c_{j}(B)^{T}+c_{j}(B)c_{i}(B)^{T}\in\mathcal{S}^{+}(\mathcal{L}_{i}\vee_{[n]}\mathcal{L}_{j})$,
and

$\mathrm{sign}(A)=\mathrm{sign}\left\\{\sum_{\\{i,j\\}\in
E(G(C))}\big{(}c_{i}(B)c_{j}(B)^{T}+c_{j}(B)c_{i}(B)^{T}\big{)}\right\\}.$

We deduce that
$\mathscr{C}=\\{\mathcal{L}_{i}\vee_{[n]}\mathcal{L}_{j};\\{i,j\\}\in
E(G(C))\\}$ is a set-join cover of $G$ with $|\mathscr{C}|=k$.

Conversely, let
$\mathscr{C}=\\{\mathcal{L}_{i}\vee_{[n]}\mathcal{K}_{i};i\in[t]\\}$ be a set-
join cover of $G$, and let us list all the elements in $V(\mathscr{C})$ in
some fixed order:
$(\widehat{\mathcal{L}}_{1},\widehat{\mathcal{L}}_{2},\ldots,\widehat{\mathcal{L}}_{|\mathscr{C}|})$.
We define $C$ to be a $|\mathscr{C}|\times|\mathscr{C}|$ matrix with:

$c_{ij}=\begin{cases}1;&\text{if
}\widehat{\mathcal{L}}_{i}\vee_{[n]}\widehat{\mathcal{L}}_{j}\in\mathscr{C},\\\
0;&\text{otherwise},\end{cases}$

and $B$ to be an $n\times|\mathscr{C}|$ matrix with

$b_{ij}=\begin{cases}1,&\text{if }i\in\widehat{\mathcal{L}}_{j}\\\
0,&\text{otherwise}.\end{cases}$

In other words, $C$ is the zero-one matrix in
$\mathcal{S}^{+}(G(\mathscr{C}))$, and $B^{T}$ is the incidence matrix of
$(\widehat{\mathcal{L}}_{1},\widehat{\mathcal{L}}_{2},\ldots,\widehat{\mathcal{L}}_{|\mathscr{C}|})$.
The proof is completed by noting that $BCB^{T}\in\mathcal{S}^{+}(G)$. ∎

######  Definition 2.12.

If $\mathscr{C}$ is a set-join cover of $G$ with of order
$\mathrm{st}_{+}(G)$, then we say that $\mathscr{C}$ is an _optimal set-join
cover_ for $G$. We will use the abbreviation _OSJ cover_ for $G$.

######  Proposition 2.13.

An OSJ cover $\mathscr{C}$ of $G$ satisfies

$\mathrm{st}_{+}(G(\mathscr{C}))=|\mathscr{C}|=|V(G(\mathscr{C}))|.$

###### Proof.

Let $\mathscr{C}$ be an OSJ cover of $G$,
$C\in\mathcal{S}^{+}(G(\mathscr{C}))$ and $B=\iota(V(\mathscr{C}))^{T}$ the
transposed incidence matrix of $V(\mathscr{C})$. Then
$A=BCB^{T}\in\mathcal{S}^{+}(G)$. If
$\mathrm{st}_{+}(G(\mathscr{C}))<|\mathscr{C}|$, then the matrix
$C\in\mathcal{S}^{+}(G(\mathscr{C}))$ can be chosen so that
$\mathrm{st}_{+}(C)<|\mathscr{C}|$. Hence, $C=B_{1}C_{1}B_{1}^{T}$ where
$C_{1}\in\mathcal{S}_{k}^{+}$ with $k<|\mathscr{C}|$. From
$A=(BB_{1})C_{1}(BB_{1})^{T}$ we conclude $\mathrm{st}_{+}(A)\leq
k<|\mathscr{C}|=\mathrm{st}_{+}(G)$, a contradiction. ∎

######  Remark 2.14.

A set-join cover $\mathscr{C}$ of a graph can be interpreted in the following
way. Consider a set of items $V$ that are either required or forbidden to
interact. The interactions are organised by meetings of certain subgroups of
$V$. If two subgroups $V_{1},V_{2}\subseteq V$ meet, then all the items from
$V_{1}$ interact with all the items from $V_{2}$. Hence, if $i,j\in V$ are
forbidden to interact, and $V_{1}$ and $V_{2}$ are two subgroups that meet,
then $i\in V_{1}$ and $j\in V_{2}$ is not allowed. The desired interactions
can clearly be organised by meetings of singletons, and we are asking what is
the minimal number of subgroups that need to be formed, to be able to organise
the desired interactions in such a way that no forbidden interactions occur.

Let $G$ be a graph that records which interactions are required and which are
forbidden: $V(G)=V$, $\\{i,j\\}\in E(G)$ if and only if $\\{i,j\\}$ are
required to interact. Any set-join cover $\mathscr{C}$ of $G$ gives us
possible way of organising required interactions, and $\mathrm{st}_{+}(G)$ is
the minimal number of groups that need to be formed.

We illustrate Theorem 2.11 by the following example.

######  Example 2.15.

Let $A=BCB^{T}$ with

$B=\left(\begin{array}[]{ccccc}1&0&1&0&0\\\ 1&0&0&1&0\\\ 1&0&0&0&1\\\
0&1&1&0&0\\\ 0&1&0&1&0\\\ 0&1&0&0&1\\\ \end{array}\right),\ \ \
C=\left(\begin{array}[]{ccccc}0&1&0&0&0\\\ 1&0&0&0&0\\\ 0&0&0&1&1\\\
0&0&1&0&1\\\ 0&0&1&1&0\\\ \end{array}\right).$

Then $G(A)=K_{6}$. This proves that $\mathrm{st}_{+}(K_{6})\leq 5$. (In
Section 4 we will show that $\mathrm{st}_{+}(K_{6})=5$.) The patterns of $B$
and $C$ determine the set-join cover of $K_{6}$:

$\mathcal{K}_{1}=\\{1,2,3\\},\mathcal{K}_{2}=\\{4,5,6\\},\mathcal{K}_{3}=\\{1,4\\},\mathcal{K}_{4}=\\{2,5\\},\mathcal{K}_{5}=\\{3,6\\},$

and
$\mathscr{C}=\\{\mathcal{K}_{1}\vee_{[6]}\mathcal{K}_{2},\mathcal{K}_{3}\vee_{[6]}\mathcal{K}_{4},\mathcal{K}_{4}\vee_{[6]}\mathcal{K}_{5},\mathcal{K}_{5}\vee_{[6]}\mathcal{K}_{3}\\}$.
Notice that $G(\mathscr{C})=G(C)=K_{2}\cup K_{3}$.

######  Example 2.16.

Let $G$ be a graph with the adjacency matrix

$A=\left(\begin{array}[]{ccccc}0&1&1&0&0\\\ 1&1&1&1&0\\\ 1&1&1&1&1\\\
0&1&1&1&1\\\ 0&0&1&1&0\\\ \end{array}\right).$

Then $\mathrm{st}_{+}(G)=4$. Indeed, any matrix $X$ with pattern matrix
$\mathrm{sign}(X)=A$ has rank at least $4$. The first three rows of $X$
clearly have to be linearly independent, and the last row cannot be written as
a linear combination of the first three. Since
$\mathrm{st}_{+}(X)\geq\mathrm{rk}(X)$ for any $X\in\mathcal{S}^{+}(G)$, we
have $\mathrm{st}_{+}(G)\geq 4$. Let

$\mathcal{K}_{1}=\\{1,2\\},\mathcal{K}_{2}=\\{2,3\\},\mathcal{K}_{3}=\\{3,4\\},\mathcal{K}_{4}=\\{4,5\\},$

and observe that
$\mathscr{C}=\\{\mathcal{K}_{1}\vee_{[5]}\mathcal{K}_{2},\mathcal{K}_{2}\vee_{[5]}\mathcal{K}_{3},\mathcal{K}_{3}\vee_{[5]}\mathcal{K}_{4}\\}$
a set-join cover of $G$ with $|\mathscr{C}|=4$, proving
$\mathrm{st}_{+}(G)\leq 4$.

Let $B^{T}=\iota({\bf R})$ be the incidence matrix of the list ${\bf
R}=(\mathcal{K}_{1},\mathcal{K}_{2},\mathcal{K}_{3},\mathcal{K}_{4})$, $C$ the
adjacency matrix of the path on 4 vertices, and $X=BCB^{T}$. Then
$X\in\mathcal{S}^{+}(G)$ and $\mathrm{st}_{+}(X)=4$.

######  Remark 2.17.

A matrix $A\in\mathcal{S}_{n}^{+}$ is completely positive, if it can be
written as $BB^{T}$ for some matrix $B\in\mathbb{R}_{+}^{n\times k}$. Such
factorization is called CP-Factorization of $A$. The minimal possible $k$ in
CP-Factorization as above is called the CP-rank of $A$, and is denoted by
$\mathrm{cp}(A)$, see [1]. The set $\mathcal{S}_{n}^{+}(G)$ contains matrices
with CP-rank $k$ if and only if there exists a set-join cover of $G$ of the
form
$\mathscr{C}=\\{\mathcal{K}_{i}\vee_{V(G)}\mathcal{K}_{i},i=1\ldots,k\\}$,
since any CP-factorization $A=BB^{T}$ can be viewed as an SN-Trifactorization
$A=BCB^{T}$, with the middle matrix $C$ equal to the identity. So the graph
$G(\mathscr{C})$ is equal to $tK_{1}^{\ell}$. Hence, all the edges of $G$ can
be covered with $k$ complete graphs with all the loops. The lowest CP-rank
that a nonnegative symmetric matrix with prescribed zero-nonzero pattern can
have is equal to the clique cover number of the pattern graph.

######  Lemma 2.18.

Let $\mathscr{C}$ be a set-join cover for a graph $G$ with $V(G)=[n]$. Assume
there exist:

  * •

$V^{\prime}\subseteq V(\mathscr{C})$ with $|V^{\prime}|=t$, and

  * •

$V=\\{\mathcal{L}_{i}\subseteq[n];\,i\in[s]\\}$,

so that $s<t$ and every element of $V^{\prime}$ can be written as the union of
some elements of $V$. Then $\mathscr{C}$ is not an OSJ cover of $G$.

###### Proof.

We will prove the lemma by constructing a set-join cover
$\widehat{\mathscr{C}}$ of $G$ with
$V(\widehat{\mathscr{C}})=(V(\mathscr{C})\setminus V^{\prime})\cup V$. This
will prove our claim as $|(V(\mathscr{C})\setminus V^{\prime})\cup
V|\leq|\mathscr{C}|-t+s<|\mathscr{C}|$. We define $\widehat{\mathscr{C}}$ as
the union of the following three sets:

  * •

$\mathscr{C}_{1}:=\\{\mathcal{K}\vee_{[n]}\mathcal{K}^{\prime};$
$\mathcal{K}\vee_{[n]}\mathcal{K}^{\prime}\in\mathscr{C}$ and
$\mathcal{K},\mathcal{K}^{\prime}\in(V(\mathscr{C})\setminus V^{\prime})\\}$.

  * •

$\mathscr{C}_{2}:=\\{\mathcal{K}\vee_{[n]}\mathcal{L};$
$\mathcal{K}\in(V(\mathscr{C})\setminus V^{\prime})$, $\mathcal{L}\in V$ and
there exists $\mathcal{K}\vee_{[n]}\mathcal{K}^{\prime}\in\mathscr{C}$ with
$\mathcal{L}\subseteq\mathcal{K}^{\prime}\\}$,

  * •

$\mathscr{C}_{3}:=\\{\mathcal{L}\vee_{[n]}\mathcal{L}^{\prime};$
$\mathcal{L},\mathcal{L}^{\prime}\in V$ and there exists
$\mathcal{K}\vee_{[n]}\mathcal{K}^{\prime}\in\mathscr{C}$ with
$\mathcal{L}\subseteq\mathcal{K}$, and
$\mathcal{L}^{\prime}\subseteq\mathcal{K}^{\prime}\\}$.

To prove that $\widehat{\mathscr{C}}$ is a set-join cover of $G$ we need to
show that $\widehat{\mathscr{C}}$ covers all the edges of $G$, and that it
does not cover any edges that are not in $G$. Since $\mathscr{C}$ is a cover
of $G$, it is clear that $\mathscr{C}_{1}$ does not cover any edges that are
not in $E(G)$. If $\mathcal{K}\in(V(\mathscr{C})\setminus V^{\prime})$,
$\mathcal{L}\in V$ and there exists
$\mathcal{K}\vee_{[n]}\mathcal{K}^{\prime}\in\mathscr{C}$ with
$\mathcal{L}\subseteq\mathcal{K}^{\prime}$, then
$E(\mathcal{K}\vee_{[n]}\mathcal{L})\subseteq
E(\mathcal{K}\vee_{[n]}\mathcal{K}^{\prime})\subseteq E(G).$ Hence,
$\mathscr{C}_{2}$ does not cover any edges not in $E(G)$. The claim for
$\mathscr{C}_{3}$ is proved in a similar way.

Now let $e\in E(G)$ and
$\mathcal{K}\vee_{[n]}\mathcal{K}^{\prime}\in\mathscr{C}$ with $e\in
E(\mathcal{K}\vee_{[n]}\mathcal{K}^{\prime})$. If
$\mathcal{K},\mathcal{K}^{\prime}\in V(\mathscr{C})\setminus V^{\prime}$, then
$\mathcal{K}\vee_{[n]}\mathcal{K}^{\prime}\in\mathscr{C}_{1}$. If
$\mathcal{K}\in V(\mathscr{C})\setminus V^{\prime}$ and
$\mathcal{K}^{\prime}\in V^{\prime}$, then $\mathcal{K}^{\prime}$ is the union
of some elements form $V$, hence there exists $\mathcal{L}\in V$ so that
$\mathcal{L}\subseteq\mathcal{K}^{\prime}$ and
$e\in\mathcal{K}\vee_{[n]}\mathcal{L}$, hence $e$ is covered by
$\mathscr{C}_{2}$. The case when $\mathcal{K},\mathcal{K}^{\prime}\in
V^{\prime}$ is proved in a similar way. ∎

Let $\mathscr{C}$ be a set-join cover of a graph $G$ with the component set
$V(\mathscr{C})=\\{\mathcal{K}_{i},i\in[t]\\}$. Recall that _a system of
distinct representatives_ (SDR for short) of $V(\mathscr{C})$ is a set
$\\{x_{i},i\in[t]\\}$ with the property that $x_{i}\in\mathcal{K}_{i}$ and
$x_{i}$ are distinct, [2, Section 1.2].

######  Lemma 2.19.

Let $\mathscr{C}$ be an optimal set-join cover of a graph $G$. Then
$V(\mathscr{C})$ has a system of distinct representatives.

###### Proof.

It is well known that a family of subsets $V(\mathscr{C})$ has an SDR if an
only the permanent of the incidence matrix $\iota(V(\mathscr{C}))$ is not
zero, [2, Section 7.5]. Assume then that $\mathscr{C}$ is an optimal cover of
$G$ with $\operatorname{per}(\iota(V(\mathscr{C})))=0$. Since
$\mathrm{st}_{+}(G)\leq n$, this is equivalent to $\iota(V(\mathscr{C}))$
having an $w\times t$ zero submatrix, where $w+t=n+1$, by Frobenius-König
Theorem, see for example [2, Section 1.2]. Hence, there exists
$V^{\prime}\subset V(\mathscr{C})$ with $|V^{\prime}|=t$ so that
$|\cup_{\mathcal{K}_{i}\in V^{\prime}}\mathcal{K}_{i}|\leq n-w=t-1$. Let
$V=\\{\\{x\\},x\in\cup_{\mathcal{K}_{i}\in\mathcal{V}}\mathcal{K}_{i}\\}$ be
the set of singletons from $\cup_{\mathcal{K}_{i}\in
V^{\prime}}\mathcal{K}_{i}$. Then $V^{\prime}$ and $V$ satisfy the conditions
of Lemma 2.18, thus $\mathscr{C}$ is not optimal, a contradiction. ∎

######  Theorem 2.20.

Let $\mathscr{C}$ be an optimal set-join cover of a graph $G$. Then $G$
contains a subgraph that is isomorphic to $G(\mathscr{C})$.

###### Proof.

Let $\mathscr{C}$ be an optimal cover for $G$ and
$\mathcal{S}=\\{x_{i},i=1\ldots,|\mathscr{C}|\\}$ an SDR for $V(\mathscr{C})$
that exists by Lemma 2.19. Clearly, there exists a (not necessarily induced)
subgraph of $G$ on vertices from $\mathcal{S}$ that is isomorphic to
$G(\mathscr{C})$. ∎

######  Remark 2.21.

A graph property $P$ is _monotone_ if every subgraph of a graph with property
$P$ also has property $P$. Theorem 2.20 shows that if $G$ has a monotone graph
property and $\mathscr{C}$ is an OSJ cover of $G$, then $G(\mathscr{C})$ has
it also. For example:

  * •

If $G$ is a forest, then $G(\mathscr{C})$ is a forest.

  * •

If $G$ is triangle free, then $G(\mathscr{C})$ is also.

  * •

If $G$ is bipartite, then $G(\mathscr{C})$ is also.

###  2.2 Uniqueness

After we establish $\mathrm{st}_{+}(G)$, we can ask, if the set-join cover of
$G$ of order $\mathrm{st}_{+}(G)$ is unique. We will consider three different
types of uniqueness as described in the definition below.

######  Definition 2.22.

A graph $G$ has _unique optimal set-join cover_ (_unique OSJ cover_ for
short), if the OSJ cover of $G$ of order $\mathrm{st}_{+}(G)$ is unique. A
graph $G$ has _essentially unique OSJ cover_ , if for any two covers
$\mathscr{C}$ and $\mathscr{C}^{\prime}$ of $G$ satisfying
$|\mathscr{C}|=|\mathscr{C}^{\prime}|=\mathrm{st}_{+}(G)$, there exists an
automorphism $\sigma:V(G)\rightarrow V(G)$ of $G$ so that
$\sigma(\mathscr{C})=\mathscr{C}^{\prime}$. (For a cover
$\mathscr{C}=\\{\mathcal{K}_{i}\vee_{V(G)}\mathcal{L}_{i},i=1\ldots,\mathrm{st}_{+}(G)\\}$,
we define $\sigma(\mathscr{C})$ to be the cover
$\\{\sigma(\mathcal{K}_{i})~{}\vee_{V(G)}~{}\mathcal{\sigma}(\mathcal{L}_{i}),i=1\ldots,\mathrm{st}_{+}(G)\\}$.)

A graph $G$ has the _unique OSJ cover graph_ , if all covers $\mathscr{C}$ of
$G$ of order $\mathrm{st}_{+}(G)$ have the same $G(\mathscr{C})$ up to
isomorphism of graphs.

######  Example 2.23.

Let $G_{1}=(3K_{1}^{\ell})\vee K_{1}^{\ell}$ be the star graph on $4$ vertices
with all the loops, and denote the vertices of $3K_{1}^{\ell}$ by $1$, $2$,
$3$ and the central vertex by $4$. Then $\mathrm{st}_{+}(G_{1})=3$ and $G_{1}$
has the unique OSJ cover $\mathscr{C}_{1}$, with the components:

$\mathcal{K}_{1}=\\{1,4\\},\mathcal{K}_{2}=\\{2,4\\},\mathcal{K}_{3}=\\{3,4\\},$

$\mathscr{C}_{1}=\\{\mathcal{K}_{1}\vee_{[4]}\mathcal{K}_{1},\mathcal{K}_{2}\vee_{[4]}\mathcal{K}_{2},\mathcal{K}_{3}\vee_{[4]}\mathcal{K}_{3}\\}$
and $G(\mathscr{C}_{1})=3K_{1}^{\ell}$.

Next, let $G_{2}$ be defined by $V(G_{2})=[4]$ and adjacency matrix

$A_{2}=\left(\begin{array}[]{ccccc}1&1&1&1\\\ 1&1&0&1\\\ 1&0&0&1\\\ 1&1&1&0\\\
\end{array}\right).$

Again $\mathrm{st}_{+}(G_{2})=3$, but $G_{2}$ does not even have the unique
OSJ cover graph. Indeed, $G_{2}$ has two OSJ covers. Both covers have
components

$\mathcal{K}_{1}=\\{1,2\\},\mathcal{K}_{2}=\\{1,4\\},\mathcal{K}_{3}=\\{1,2,3\\},$

$\mathscr{C}_{2}=\\{\mathcal{K}_{1}\vee_{[4]}\mathcal{K}_{1},\mathcal{K}_{1}\vee_{[4]}\mathcal{K}_{2},\mathcal{K}_{2}\vee_{[4]}\mathcal{K}_{3}\\}$,
and
$\mathscr{C}_{3}=\\{\mathcal{K}_{1}\vee_{[4]}\mathcal{K}_{1},\mathcal{K}_{2}\vee_{[4]}\mathcal{K}_{3}\\}$.
Note that $G(\mathscr{C}_{2})$ is a path $P_{3}$ with a loop on one pendant
vertex, and $G(\mathscr{C}_{3})$ is $K_{1}^{\ell}\cup P_{2}$.

Finally, let $G_{3}=K_{3}\vee K_{1}^{\ell}$ be a graph on $4$ vertices. Denote
the vertices of $K_{3}$ by $1$, $2$, $3$ and the vertex with the loop by $4$.
Again $\mathrm{st}_{+}(G_{3})=3$. This time $G_{3}$ has the unique OSJ cover
graph $K_{3}$, but OSJ cover is not unique nor essentially unique. Let

$\mathcal{K}_{1}=\\{1,4\\},\mathcal{K}_{2}=\\{2,4\\},\mathcal{K}_{3}=\\{3,4\\},\mathcal{K}^{\prime}_{3}=\\{3\\}.$

The covers
$\mathscr{C}_{4}=\\{\mathcal{K}_{1}\vee_{[4]}\mathcal{K}_{2},\mathcal{K}_{2}\vee_{[4]}\mathcal{K}_{3},\mathcal{K}_{3}\vee_{[4]}\mathcal{K}_{1}\\}$
and
$\mathscr{C}_{5}=\\{\mathcal{K}_{1}\vee_{[4]}\mathcal{K}_{2},\mathcal{K}_{2}\vee_{[4]}\mathcal{K}^{\prime}_{3},\mathcal{K}^{\prime}_{3}\vee_{[4]}\mathcal{K}_{1}\\}$
are not isomorphic since the cardinalities of their components do not match.

In Example 4.10 we will see that $K_{6}$ has essentially unique but not unique
OSJ cover.

###  2.3 Operations on graphs that preserve $\mathrm{st}_{+}(G)$

Observations so far make it clear, that if $G$ has two vertices with the same
set of neighbours, then removing one of those vertices will not change
$\mathrm{st}_{+}(G)$. This gives us an operation on graphs, whose effect on
SNT-rank is easily understood. To make this observation more precise, we need
the definition below.

######  Definition 2.24.

Let $G$ be a graph and $v\in V(G)$. Then

$N_{G}(v):=\\{w;\\{v,w\\}\in E(G)\\}$

is called the _neighbourhood_ of $v$.

Note that $v\in N_{G}(v)$ precisely when $v$ has a loop in $G$.

######  Definition 2.25.

Two vertices $v,w\in V(G)$ are called _twins_ if $N_{G}(v)=N_{G}(w)$. A graph
$G$ is _twin-free_ , if no two pairs of vertices in $V(G)$ are twins.

By $F_{tw}(G)$ we denote the biggest twin free sub-graph of $G$. Note that
$F_{tw}(G)$ is obtained from $G$ by removing all but one vertex from every set
of twins in $G$.

######  Definition 2.26.

Let $A\in\mathcal{S}_{n}^{+}$. The graph $F_{tw}(G(A))$ is called _the twin-
free graph_ of $A$. _The twin-free pattern matrix_ of $A$, denoted by
$F_{tw}(\mathrm{sign}(A))$, is the adjacency matrix of $F_{tw}(G(A))$ and can
be obtained from $\mathrm{sign}(A)$ by removing any duplicate rows and columns
from $\mathrm{sign}(A)$.

With this new terminology we can restate our earlier observation.

######  Proposition 2.27.

Let $G$ be a graph. Then $\mathrm{st}_{+}(G)=\mathrm{st}_{+}(F_{tw}(G))$.
Moreover, $G$ has unique OSJ cover if and only if $F_{tw}(G)$ has.

###### Proof.

Let $G$ be a graph, $v\in V(G)$, and $\widehat{G}$ a graph obtained from $G$
by duplicating the vertex $v$ into vertices $v_{1}$ and $v_{2}$. Hence,
$V(\widehat{G})=(V(G)\setminus\\{v\\})\cup\\{v_{1},v_{2}\\}$, and
$N_{\widehat{G}}(v_{i})$, $i=1,2$, is equal to $N_{G}(v)$ if $v\not\in
N_{G}(v)$, and is equal to $(N_{G}(v)\setminus\\{v\\})\cup\\{v_{1},v_{2}\\}$
otherwise.

A set-join cover of $\widehat{G}$ can be obtained from a set-join cover
$\mathscr{C}$ of $G$ by replacing $v$ in each of the components of
$\mathscr{C}$ by $v_{1}$ and $v_{2}$. Note that two distinct set-join covers
of $G$ result two distinct set-join covers of $\widehat{G}$ in this process.
Hence, $\mathrm{st}_{+}(G)\geq\mathrm{st}_{+}(\widehat{G})$ and unique OSJ
cover of $\widehat{G}$ implies unique OSJ cover of $G$.

In order to prove that unique OSJ cover of $G$ also implies unique OSJ cover
of $\widehat{G}$, let us assume that $G$ has unique OSJ cover, and let
${\widehat{\mathscr{C}}}$ be some OSJ cover of $\widehat{G}$. We claim that
for $\mathcal{K}\in V({\widehat{\mathscr{C}}})$, $v_{1}\in\mathcal{K}$ if and
only if $v_{2}\in\mathcal{K}$. If this is not true, then one set-join cover
$\mathscr{C}_{1}$ of $G$ can be obtained from ${\widehat{\mathscr{C}}}$ by
removing $v_{2}$ and replacing $v_{1}$ in each of the components of
${\widehat{\mathscr{C}}}$ by $v$, and a different set-join cover
$\mathscr{C}_{2}$ of $G$ can be obtained from ${\widehat{\mathscr{C}}}$ by
removing $v_{1}$ and replacing $v_{2}$ in each of the components of
${\widehat{\mathscr{C}}}$ by $v$. In particular, this proves that every OSJ
cover of $\widehat{G}$ can be obtained from some OSJ cover of $G$ by the
process outlined above. Since the OSJ cover of $G$ is by our assumption unique
this establishes the uniqueness of OSJ cover of $\widehat{G}$. ∎

######  Lemma 2.28.

If $\mathscr{C}$ is an optimal set-join cover for a graph $G$, then
$G(\mathscr{C})$ is twin-free.

###### Proof.

The assertion follows directly from Propositions 2.13 and 2.27. ∎

######  Remark 2.29.

Suppose that $G(\mathscr{C})$ contains twin vertices $\mathcal{K}_{1}$ and
$\mathcal{K}_{2}$. Let $\mathcal{K}_{3}=\mathcal{K}_{1}\cup\mathcal{K}_{2}$
and

$\displaystyle\mathscr{C}_{1}$
$\displaystyle=\\{\mathcal{K}\vee_{V(G)}\mathcal{K}^{\prime};\mathcal{K},\mathcal{K}^{\prime}\in(V(\mathscr{C})\setminus\\{\mathcal{K}_{1},\mathcal{K}_{2}\\}),\mathcal{K}\vee_{V(G)}\mathcal{K}^{\prime}\in\mathscr{C}\\},$
$\displaystyle\mathscr{C}_{2}$
$\displaystyle=\\{\mathcal{K}_{3}\vee_{V(G)}\mathcal{K}^{\prime};\mathcal{K}^{\prime}\in(V(\mathscr{C})\setminus\\{\mathcal{K}_{1},\mathcal{K}_{2}\\}),\mathcal{K}_{1}\vee_{V(G)}\mathcal{K}^{\prime}\in\mathscr{C}\\}.$
$\displaystyle\mathscr{C}_{3}$
$\displaystyle=\\{\mathcal{K}_{3}\vee_{V(G)}\mathcal{K}_{3}\\}.$

If $\mathcal{K}_{1}\vee_{V(G)}\mathcal{K}_{2}\in\mathscr{C}$ let
$\widehat{\mathscr{C}}=\mathscr{C}_{1}\cup\mathscr{C}_{2}\cup\mathscr{C}_{3}$,
otherwise let $\widehat{\mathscr{C}}=\mathscr{C}_{1}\cup\mathscr{C}_{2}$. It
is straightforward to check that $\widehat{\mathscr{C}}$ is set-join cover of
$G$ with
$V(\widehat{\mathscr{C}})=(V(\mathscr{C})\setminus\\{\mathcal{K}_{1},\mathcal{K}_{2}\\})\cup\\{\mathcal{K}_{3}\\}$,
so $\mathscr{C}$ is not an optimal set-join cover of $G$.

######  Proposition 2.30.

Let $G$ be a graph and let $\widehat{G}=G\vee K_{1}^{\ell}$. Then:

$\mathrm{st}_{+}(\widehat{G})=\begin{cases}\mathrm{st}_{+}(G);&\text{ if
}|N_{G}(v)|\geq 1\text{ for all }v\in V(G),\\\ \mathrm{st}_{+}(H)+2;&\text{ if
}G=H\cup tK_{1}.\end{cases}$

Moreover, if $G$ is a graph without isolated vertices, then $G$ has unique OSJ
cover graph if and only if $\widehat{G}$ has one.

###### Proof.

Since any $A\in\mathcal{S}_{+}(G\vee K_{1}^{\ell})$ has
$A_{1}\in\mathcal{S}_{+}(G)$ as a principal sub-matrix
$\mathrm{st}_{+}(G)\leq\mathrm{st}_{+}(G\vee K_{1}^{\ell})$ holds.

Assume that $G$ has no isolated vertices. Let $V(G)=[n]$ and
$V(\widehat{G})=[n+1]$. Replacing every component $\mathcal{K}$ in a set-join
cover of $G$ by $\widehat{\mathcal{K}}:=\mathcal{K}\cup\\{n+1\\}$ produces a
set-join cover of $\widehat{G}$. Conversely, replacing every component
$\mathcal{K}$ in a set-join cover of $\widehat{G}$ by
$\mathcal{K}^{\prime}:=\mathcal{K}\setminus\\{n+1\\}$ produces a set-join
cover of $G$. Observe that $\\{n+1\\}$ is not a component of any OSJ cover of
$\widehat{G}$. Indeed, if a cover $\widehat{\mathscr{C}}$ of $\widehat{G}$
contains $\\{n+1\\}$ as a component, then we can construct a set join cover
$\widehat{\mathscr{C}}^{\prime}$ of $\widehat{G}$ satisfying
$|\widehat{\mathscr{C}}^{\prime}|=|\widehat{\mathscr{C}}|-1$ by removing any
set-joins involving $\\{n+1\\}$ and adding $n+1$ to all other components of
$\mathscr{C}$. Since the process outlined above preserves the order and the
graphs of the corresponding OSJ covers, the statement for graphs without
isolated vertices follows. (We note in passing that $G$ may have unique OSJ
cover, but $\widehat{G}$ doesn’t, since the vertex $n+1$ is not necessarily
contained in all the components of OSJ cover of $G\vee K_{1}^{\ell}$.)

Now, let $G=H\cup tK_{1}$, where we assume that $H$ does not contain any
isolated vertices (without loops). Let $V(G)=V(H)\cup\mathcal{I}=[n]$, and
$V(\widehat{G})=[n+1]$ as before. Defining $\widehat{\mathcal{K}}$ as above,
produces from a set-join cover $\mathscr{C}$ of $G$ a set-join cover
$\widehat{\mathscr{C}}$ of $(G\vee K_{1}^{\ell})\cup tK_{1}$, since the
elements of $\mathcal{I}$ are not contained in any component in this
construction. Adding $\mathcal{I}\vee_{[n+1]}\\{n+1\\}$ to
$\widehat{\mathscr{C}}$ results in a set-join cover of $\widehat{G}$, and
introduces $2$ new components. We conclude that
$\mathrm{st}_{+}(\widehat{G})\leq\mathrm{st}_{+}(H)+2$.

Finally, let ${\mathscr{C}^{\prime}}$ be an OSJ cover of $\widehat{G}$. Since
the elements of $\mathcal{I}$ are connected only to $\\{n+1\\}$ in
$\widehat{G}$, we observe that ${\mathscr{C}^{\prime}}$ has to contain
$\\{\mathcal{K}_{0}\vee_{[n+1]}\\{n+1\\}\\}$, where
$\mathcal{I}\subseteq\mathcal{K}_{0}$, and $\mathcal{K}_{0}$ is not a
component of any other set-join in ${\mathscr{C}^{\prime}}$. Let
$\mathscr{C}^{\prime\prime}$ be obtained from $\mathscr{C}^{\prime}$ by
removing all set-joins with a component $\\{n+1\\}$. Note that
$|\mathscr{C}^{\prime\prime}|\leq|\mathscr{C}^{\prime}|-2$, since
$V({\mathscr{C}^{\prime\prime}})$ does not contain $\\{n+1\\}$ nor
$\mathcal{K}_{0}$. Replacing every
$\mathcal{K}\vee_{V(\widehat{G})}\mathcal{L}\in\mathscr{C}^{\prime\prime}$ by
$\mathcal{K}^{\prime}\vee_{V(H)}\mathcal{L}^{\prime}$, where
$\mathcal{K}^{\prime}:=\mathcal{K}\setminus\\{n+1\\}$ as above, gives us a
set-join cover of $H$, proving
$\mathrm{st}_{+}(\widehat{G})=\mathrm{st}_{+}(H)+2$. ∎

######  Remark 2.31.

Note that $G=K_{2}\cup K_{1}$ has unique OSJ cover graph, but
$\widehat{G}=G\vee K_{1}^{\ell}$ doesn’t.

From Propositions 2.5, 2.27 and 2.30 we see that in order to understand SNT-
rank of graphs, we can from now on consider only connected twin-free graphs
that are not of the form $G\vee K_{1}^{\ell}$.

######  Example 2.32.

Threshold graphs is a family of graphs (without loops) that can be constructed
by repeating two operations, adding an isolated vertex ($G\cup K_{1}$), and
joining a vertex ($G\vee K_{1}$). Here we extend this definition to _threshold
graphs with loops_ to be all graphs that can be constructed by repeating the
following two operations on $G$:

  * •

$G\cup K_{1}$

  * •

$G\vee K_{1}^{\ell}$

To obtain a twin free graph the two operations have to alternate. Considering
only connected twin-free graphs resulting from this process, we get the
following sequence of graphs:

$T_{1}:=K_{1}\vee K_{1}^{\ell},\,T_{i+1}:=(T_{i}\cup K_{1})\vee K_{1}^{\ell}.$

We have $\mathrm{st}_{+}(T_{i})=2i$ by Proposition 2.30. This is not
surprising, as it is not difficult to see that every matrix
$A\in\mathcal{S}^{+}(T_{i})$ has $\mathrm{rk}(A)=2i$.

######  Remark 2.33.

Let $G$ be a graph with a cut edge $\\{u_{1},u_{2}\\}$, so that $G$ with this
edge removed is equal to $G_{1}\cup G_{2}$, where $u_{i}\in V(G_{i})$,
$i=1,2$. Then:

$\mathrm{st}_{+}(G_{1})+\mathrm{st}_{+}(G_{2})\leq\mathrm{st}_{+}(G)\leq\mathrm{st}_{+}(G_{1})+\mathrm{st}_{+}(G_{2})+2.$

Moreover, $\mathrm{st}_{+}(G)=\mathrm{st}_{+}(G_{1})+\mathrm{st}_{+}(G_{2})$
if and only if for $i=1,2$ there exist OSJ covers $\mathscr{C}_{i}$ with
$\\{u_{i}\\}\in V(\mathscr{C}_{i})$, and
$\mathrm{st}_{+}(G)=\mathrm{st}_{+}(G_{1})+\mathrm{st}_{+}(G_{2})+1$ if such
cover exists for either $i=1$ or $i=2$, but not both.

##  3 Trees and cycles without loops

Let $G$ be a graph without loops that does not contain any four cycles. Then a
set-join cover of $G$ can contain only elements of the form
$\mathcal{K}\vee_{V(G)}\\{v\\}$ for some $v\in V(G)$, since all set-joins
$\mathcal{K}\vee_{V(G)}\mathcal{L}$ with $|\mathcal{K}|\geq 2$ and
$|\mathcal{L}|\geq 2$ contain a four cycle. Hence, for graphs without loops
and four cycles, a set-join cover is equivalent to an edge star cover, as
defined below.

######  Definition 3.1.

Let $G$ be a simple graph without loops. A family of simple stars
$\\{S_{1},S_{2},...,$ $S_{k}\\}$ is _an edge star cover_ of $G$ if
$E(G)=\cup_{i=1}^{k}E(S_{i})$. The _edge star cover number_
$\operatorname{star}(G)$ of $G$ is the minimal number of stars in any edge
star cover of $G$.

Clearly, $\mathrm{st}_{+}(G)\leq 2\operatorname{star}(G)$ for any graph $G$,
and we will show that this is an equality for trees. For any tree $T$ it is
known that $\mathrm{rk}(A)$ equals twice the matching number of $T$ for all
$A\in\mathcal{S}^{+}(T)$, [5]. Since for a tree $T$ the matching number equals
$\operatorname{star}(T)$, the inequality $\mathrm{st}_{+}(T)\geq
2\operatorname{star}(T)$ clearly holds. In this work we use the edge star
cover number due to its immediate connection to set-join covers. We summarise
this observation in the next proposition.

######  Proposition 3.2.

Let $T$ be a forest (without loops) and $A\in\mathcal{S}^{+}(T)$. Then
$\mathrm{rk}(A)=\mathrm{st}_{+}(A)=2\operatorname{star}(T)$. In particular,
$\mathrm{st}_{+}(T)=2\operatorname{star}(T)$.

In the next lemma we see that if a graph $G$ contains a leaf, then any set-
join cover has to contain at least one element of the form
$\mathcal{K}\vee\\{v\\}$ for some $v\in V(G)$, i.e. it contains at least one
star.

######  Lemma 3.3.

Let $G$ be a graph and let $L(G)\subset V(G)$ be the set of all leaves without
a loop in $G$. Let $\ell\in L(G)$, $w\in V(G)$ its unique neighbour, and
$G^{\prime}$ the graph obtained from $G$ by deleting all edges
$\\{w,v^{\prime}\\}$ with $v^{\prime}\in N_{G}(w)$ (and all singletons that
result after this deletion). Then
$\mathrm{st}_{+}(G)=\mathrm{st}_{+}(G^{\prime})+2$ and for any optimal set-
join cover $\mathscr{C}$ of $G$, we have
$\\{w\\}\vee_{V(G)}\mathcal{N}\in\mathscr{C}$, where $N_{G}(w)\cap
L(G)\subseteq\mathcal{N}\subseteq N_{G}(w)$.

###### Proof.

Let $\mathscr{C}$ be an optimal set-join cover of $G$. Since
$N_{G}(\ell)=\\{w\\}$, there exists $\mathcal{N}\subseteq N_{G}(w)$ with
$\ell\in\mathcal{N}$, so that $\\{w\\}\vee_{V(G)}\mathcal{N}\in\mathscr{C}$.
If there exists $\ell^{\prime}\in(N_{G}(w)\cap L(G))\setminus\mathcal{N}$,
then we also have $\\{w\\}\vee_{V(G)}\mathcal{N}^{\prime}\in\mathscr{C}$ for
some $\mathcal{N}^{\prime}$ with $\ell^{\prime}\in\mathcal{N}^{\prime}$. Since
$\mathscr{C}_{1}:=(\mathscr{C}\cup(\\{w\\}\vee
N_{G}(w)))\setminus\\{\\{w\\}\vee_{V(G)}\mathcal{N},\\{w\\}\vee_{V(G)}\mathcal{N}^{\prime}\\}$
is a set-join cover of $G$ with $|\mathscr{C}_{1}|\leq|\mathscr{C}|-1$, we get
a contradiction with the assumption that $\mathscr{C}$ is optimal. Hence,
$N_{G}(w)\cap L(G)\subseteq\mathcal{N}$.

Observe that
$\mathscr{C}^{\prime}:=\mathscr{C}\setminus\\{\\{w\\}\vee_{V(G)}\mathcal{N}\\}$
is a set-join cover for $G^{\prime}\cup tK_{1}$ for some $t\in\mathbb{N}$.
Since, $\mathrm{st}_{+}(G^{\prime})=\mathrm{st}_{+}(G^{\prime}\cup tK_{1})$,
this implies $\mathrm{st}_{+}(G^{\prime})\leq\mathrm{st}_{+}(G)+2$. On the
other hand,
$\mathscr{C}=\\{\\{w\\}\vee_{V(G)}N_{G}(w)\\}\cup\mathscr{C}^{\prime}$ is a
set-join cover of $G$ for any set-join cover $\mathscr{C}^{\prime}$ of
$G^{\prime}$. Hence, $\mathrm{st}_{+}(G)\leq\mathrm{st}_{+}(G^{\prime})+2$, as
desired. ∎

######  Example 3.4.

For paths we have $\mathrm{st}_{+}(P_{2k})=\mathrm{st}_{+}(P_{2k+1})=2k$ by
inductive application of Lemma 3.3.

In the result below we resolve the question of uniqueness of OSJ covers for
trees without loops.

######  Theorem 3.5.

Let $T$ be a tree with $|V(T)|\geq 3$. Then $T$ has unique OSJ cover if and
only if the distance between any two leaves in $T$ is even.

###### Proof.

Assume the distance between any two leaves in $T$ is even, and let $V_{0}$ be
the set of vertices in $T$ at an odd distance to all leaves. An inductive
application of Lemma 3.3 shows that

$\mathscr{C}_{0}:=\\{\\{v\\}\vee N_{T}(v);v\in V_{0}\\}$

is an OSJ cover of $T$. Let $\mathscr{C}^{\prime}$ be an OSJ cover of $T$ and
$V^{\prime}$ the set of all central vertices of stars in
$\mathscr{C}^{\prime}$. Then $|\mathscr{C}^{\prime}|=2|V^{\prime}|=2|V_{0}|$.
Since for any $v\in V(T)\setminus V^{\prime}$ there exists $w\in
V^{\prime}\cap N_{T}(v)$, we necessarily have $V^{\prime}=V_{0}$. Since no two
vertices in $V_{0}$ are connected in $T$, $\mathscr{C}_{0}$ is the only
collection of stars with central vertices $V_{0}$ that covers $T$. We conclude
that the cover is unique. We further remark, that the unique OSJ cover graph
of $T$ is $|V_{0}|P_{2}$.

Assume now, that there are two leaves $\ell_{1}$ and $\ell_{2}$ in a tree $T$
at odd distance $d$, $d\geq 3$. Observe that in any set-join cover
$\mathscr{C}$ of $T$ at least every second vertex of the path between
$\ell_{1}$ and $\ell_{2}$ is a central vertex of a star in that cover, hence a
component in $\mathscr{C}$. Since $d$ is odd, we have
$\\{v_{1}\\}\vee\mathcal{S}_{1}$ and $\\{v_{2}\\}\vee\mathcal{S}_{2}$ in
$\mathscr{C}$, such that $v_{1}$ and $v_{2}$ are neighbours in $T$, and at
least one of the inclusions $v_{1}\in\mathcal{S}_{2}$ and
$v_{2}\in\mathcal{S}_{1}$ holds. Assume now that $\mathscr{C}$ is an OSJ
cover, and without loss of generality that $v_{1}\in\mathcal{S}_{2}$. Then we
get a different OSJ cover of $T$ by replacing $\\{v_{1}\\}\vee\mathcal{S}_{1}$
and $\\{v_{2}\\}\vee\mathcal{S}_{2}$ by
$\\{v_{1}\\}\vee(\mathcal{S}_{1}\cup\\{v_{2}\\})$ and
$\\{v_{2}\\}\vee(\mathcal{S}_{2}\setminus\\{v_{1}\\})$. ∎

######  Example 3.6.

Note that the only tree with $|V(T)|=2$ is a path $P_{2}$ and it has the
unique OSJ cover. Moreover, a path $P_{n}$ has unique OSJ cover if and only if
$n$ is odd or $n=2$, see Theorem 3.5.

For integers $t\geq 3$ and $k_{i}\geq 1$, $i\in[t]$, we denote by
$\mathrm{star}(k_{1},k_{2},...,k_{t})$ the graph with the central vertex $v$
and $t$ arms, where each arm is a path on $k_{i}+1$ vertices and one of its
end-vertices is $v$. Hence, $\mathrm{star}(k_{1},k_{2},...,k_{t})$ is a
generalised star with $\sum_{i=1}^{t}k_{i}+1$ vertices. If $k_{i}=1$ for all
$i$, then $\mathrm{star}(1,1,...,1)=K_{1,t}$ is a star graph with $t$ leaves.

######  Example 3.7.

Let $G=\mathrm{star}(k_{1},k_{2},...,k_{t})$, $t\geq 3$, be a generalised
star. Then

$\mathrm{st}_{+}(G)=\begin{cases}|V(G)|+1-|\\{k_{i};k_{i}\text{
odd}\\}|;&\text{if at least one }k_{i}\text{ is odd},\\\ |V(G)|-1;&\text{if
all }k_{i}\text{ are even}.\end{cases}$

We will prove this claim by induction on

$\psi(G):=\sum_{i=1}^{t}k_{i}-t.$

We first assume $\psi(G)=0$. This implies
$G=G_{0}(t):=\mathrm{star}(1,1,\ldots,1)$, i.e. a star with $t$ leaves.
Clearly, $\mathrm{st}_{+}(G_{0}(t))=2$, and the claim holds. For $\psi(G)=1$,
we have $G=G_{1}(t):=\mathrm{star}(2,1,\ldots,1)$, i.e. a generalised star
with $t$ arms. Applying Lemma 3.3 for the leaf on the long arm, we get:

$\mathrm{st}_{+}(G_{1}(3))=\mathrm{st}_{+}(P_{3})+2=4$

by Example 3.4, and for $t>3$:

$\mathrm{st}_{+}(G_{1}(t))=\mathrm{st}_{+}(G_{0}(t-1))+2=4.$

Since $G_{1}(t)$ has $t+2$ vertices and $t-1$ arms of odd length, this
establishes the base of induction.

Now assume the claim holds for all generalised stars
$G^{\prime}=\mathrm{star}(k_{1}^{\prime},k_{2}^{\prime},...,k_{t^{\prime}}^{\prime})$
with $\psi(G^{\prime})\leq\psi$, and let
$G:=\mathrm{star}(k_{1},k_{2},...,k_{t})$ with $\psi(G)=\psi+1\geq 2$. Without
loss of generality we can assume $k_{1}\geq 2$. By Lemma 3.3 we have
$\mathrm{st}_{+}(G)=\mathrm{st}_{+}(G^{\prime})+2$, where:

  * •

$G^{\prime}:=\mathrm{star}(k_{2},\ldots,k_{t})$ with
$\psi(G^{\prime})=\psi(G)-1\geq 1$ for $k_{1}=2$,

  * •

$G^{\prime}:=\mathrm{star}(k_{1}-2,k_{2},\ldots,k_{t})$ with
$\psi(G^{\prime})=\psi(G)-2$ for $k_{1}\geq 3$.

If $k_{1}=2$ and $t=3$, then $G^{\prime}=P_{k_{2}+k_{t}+1}$, and the claim
holds for $G$ by Example 3.4. In all other cases $G^{\prime}$ is again a
generalised star, so we can use the induction hypothesis. Noticing that
$V(G)-V(G^{\prime})=2$ and that $G$ and $G^{\prime}$ have same number of arms
of odd length, we establish the claim.

The graph $G$ has unique OSJ cover if and only if all $k_{i}$’s are odd or all
even by Theorem 3.5.

A vertex $v$ is a _cut_ vertex of a connected graph $G$, if by removing $v$
and all edges $\\{v,w\\}$, $w\in N_{G}(v)$, from $G$ we get a disconnected
graph that we will denote by $G\setminus\\{v\\}$. (We allow for a cut vertex
to have a loop.)

######  Proposition 3.8.

Let $v$ be a cut vertex of a connected graph $G$, where $k\geq 2$ and
$G\setminus\\{v\\}=\cup_{i=1}^{k}G_{i}$ for some connected graphs $G_{i}$.
Then $\mathrm{st}_{+}(G)\leq 2+\sum_{i=1}^{k}\mathrm{st}_{+}(G_{i})$.

###### Proof.

Let $\mathscr{C}_{i}$ be a set-join cover of $G_{i}$, $i\in[k]$. Then

$\mathscr{C}:=\cup_{i=1}^{k}\mathscr{C}_{i}\cup\\{\\{v\\}\vee_{V(G)}N_{G}(v)\\}$

is a set-join cover of $G$. Since
$|\mathscr{C}|=2+\sum_{i=1}^{k}|\mathscr{C}_{i}|$, the claim follows. ∎

######  Example 3.9.

The inequality of Proposition 3.8 is not always an equality, but it cannot be
improved in general.

  1. 1.

Let $G=\mathrm{star}(2,2,2)$. Then $\mathrm{st}_{+}(G)=6$ by Proposition 3.7
and $G\setminus\\{v\\}=3P_{2}$, so $2+\sum_{i=1}^{k}\mathrm{st}_{+}(G_{i})=8$.

  2. 2.

Let $G$ be a star graph $G=\mathrm{star}(3,3,3)$. Then $\mathrm{st}_{+}(G)=8$
by Proposition 3.7 and $G\setminus\\{v\\}=3P_{3}$, so
$2+\sum_{i=1}^{k}\mathrm{st}_{+}(G_{i})=8$.

We now consider SNT-rank of cycles.

######  Proposition 3.10.

Let $n\geq 3,n\neq 4$. Then $\mathrm{st}_{+}(C_{n})=n$. Furthermore,
$\mathrm{st}_{+}(C_{4})=2$.

###### Proof.

If $n=3$, then the determinant of any matrix $A\in\mathcal{S}^{+}(C_{3})$ is
positive, so $\mathrm{rk}(A)=3$, thus $\mathrm{st}_{+}(C_{3})=3$. If $n=4$,
then

$\mathscr{C}=\\{\mathcal{\\{}1,3\\}\vee_{[4]}\mathcal{\\{}2,4\\}\\}$

is a set-join cover of $C_{4}$, so $\mathrm{st}_{+}(C_{4})=2$. Now let $n\geq
5$ and let $\mathscr{C}$ be a set-join cover of $C_{n}$. If every component in
$\mathscr{C}$ is a singleton, then $|\mathscr{C}|=n$. If $\mathscr{C}$
contains a component $\mathcal{K}_{1}$, which is not a singleton, then
$\mathcal{K}_{1}=N_{C_{n}}(v)$ for some $v\in V(C_{n})$ and
$\\{v\\}\vee_{[n]}\mathcal{K}_{1}\in\mathscr{C}$. Since $n\geq 5$ the
components $\\{v\\}$ and $\mathcal{K}_{1}$ don’t appear anywhere else in
$\mathscr{C}$. This implies that
$\mathscr{C}\setminus\\{\\{v\\}\vee_{[n]}\mathcal{K}_{1}\\}$ is a set-join
cover of $P_{n-1}$, so $|\mathscr{C}|\geq 2+\mathrm{st}_{+}(P_{n-1})\geq n$,
proving $\mathrm{st}_{+}(C_{n})=n$. ∎

######  Remark 3.11.

Let $G$ be an unicyclic graph, i.e. connected simple graph without loops
containing exactly one cycle. Then $G$ is either a cycle or it contains at
least one leaf. We can find the SNT-rank of $G$ by repeatedly applying Lemma
3.3 on a leaf. In each step we obtain a disjoint union of trees and at most
one unicyclic graph. Eventually we obtain a disjoint union of trees and at
most one cycle. For this graph the SNT-rank can be computed by Proposition 3.2
and Proposition 3.10.

##  4 Complete graphs without loops

Let $\mathscr{C}$ be a set-join cover of $K_{n}$ with $V(K_{n})=[n]$. If
$\mathcal{K}\vee_{[n]}\mathcal{L}\in\mathscr{C}$, then
$\mathcal{K}\cap\mathcal{L}=\emptyset$, since $K_{n}$ has no loops. On the
other hand, for any pair $i,j\in[n],$ $i\neq j$, there exist
$\mathcal{K}\vee_{[n]}\mathcal{L}\in\mathscr{C}$, so that $i\in\mathcal{K}$,
$j\in\mathcal{L}$.

######  Definition 4.1.

Let $\bf T$ be a $k$-tuple of subsets of $[n]$. If for any pair $i,j\in[n],$
$i\neq j$, there exists $\mathcal{K},\mathcal{L}\in\bf T$ so that
$i\in\mathcal{K}$, $j\in\mathcal{L}$ and
$\mathcal{K}\cap\mathcal{L}=\emptyset$, then $\bf T$ is called _a separating
cover_ of $n$ elements with $k$ sets.

Hence, if $\mathscr{C}$ is a set-join cover of $K_{n}$, then $V(\mathscr{C})$
is a separating cover of $n$ elements with $|V(\mathscr{C})|$ sets. To
determine $\mathrm{st}_{+}(K_{n})$ for a given $n$, we need to find minimal
separating cover of $n$ elements. This problem is known as Katona problem and
has been solved independently by A. C. C. Yao, [9] and M. C. Cai [3], hence
the problem of determining $\mathrm{st}_{+}(K_{n})$ is resolved. In this
section we expand on the work in [9], by showing how various set-join covers
of $K_{n}$ can be constructed, investigate when these covers are optimal, and
when they are essentially unique.

######  Theorem 4.2 ([9]).

Let $n\in\mathbb{N}$, and let $s(n):=\min\\{k:$ there is a separating cover on
$n$ elements with $k$ sets$\\}$. For all $n\geq 2$,

$s(n)=\begin{cases}3i&\text{if }\,2\cdot 3^{i-1}<n\leq 3^{i}\\\ 3i+1&\text{if
}\,3^{i}<n\leq 4\cdot 3^{i-1}\\\ 3i+2&\text{if }\,4\cdot 3^{i-1}<n\leq 2\cdot
3^{i},\\\ \end{cases}$ (1)

while $s(1)=0$.

######  Corollary 4.3.

The SNT-rank of a complete graph is $\mathrm{st}_{+}(K_{n})=s(n)$, where
$s(n)$ is defined in (1).

To give some intuition on how a set-join cover for $K_{n}$ can be constructed,
we offer the following example.

######  Example 4.4.

Suppose that $n\in\mathbb{N}$ is written as a product of two factors $n=p\cdot
q$ with $p,q\geq 2$. Let $V(K_{n})=[n]$, and define:

$\displaystyle\mathcal{L}_{i}$ $\displaystyle=\\{(i-1)p+s;s=1,\ldots,p\\}\
\text{ for every }i\in[q],$ $\displaystyle\mathcal{K}_{j}$
$\displaystyle=\\{j+tp;t=0,\ldots,q-1\\},\ \text{ for every }j\in[p].$

Then

$\mathscr{C}=\\{\mathcal{L}_{i}\vee_{[n]}\mathcal{L}_{j},i,j\in[q],i\neq
j\\}\cup\\{\mathcal{K}_{i}\vee_{[n]}\mathcal{K}_{j},i,j\in[p],i\neq j\\}$

is a set-join of $K_{n}$. It follows that $\mathrm{st}_{+}(K_{n})\leq p+q$.

A generalisation of this example leads to an OSJ cover of $K_{n}$.

######  Proposition 4.5.

Let $n\in\mathbb{N}$ and $q_{i}\in\mathbb{N}$, $i\in[t]$, satisfy $q_{i}\geq
2$ and $n\leq\prod_{k=1}^{t}q_{k}$. Then there exists a set-join cover
$\mathscr{C}$ of $K_{n}$ with $|\mathscr{C}|=\sum_{i=1}^{t}q_{i}$ and
$G(\mathscr{C})=\cup_{i=1}^{t}K_{q_{i}}$. Furthermore,

$\mathrm{st}_{+}(K_{n})=\min\left\\{\sum_{i=1}^{t}q_{i};n\leq\prod_{i=1}^{t}q_{i}\right\\}.$
(2)

###### Proof.

We prove the first claim by induction on $t$. If $t=1$, then the claim is
trivial. If $n\leq m$, then $K_{n}$ is a subgraph of $K_{m}$ and a restriction
of any set-join cover of $K_{m}$ to the elements of $K_{n}$ results in a set-
join cover of $K_{n}$, in particular
$\mathrm{st}_{+}(K_{n})\leq\mathrm{st}_{+}(K_{m})$. This observation allows us
to assume $n=\prod_{k=1}^{t}q_{k}$. The claim for $t=2$ is proved in Example
4.4 and establishes the base of induction. Let $n_{1}=\prod_{k=1}^{t-1}q_{k}$,
$V(K_{n})=[n]$ and $V(K_{n_{1}})=[n_{1}]$. Let $\mathscr{C}$ be a set-join
cover of $K_{n_{1}}$ with $|\mathscr{C}|=\sum_{k=1}^{t-1}q_{k}$. For every
$\mathcal{K}\in V(\mathscr{C})$ let

$\mathcal{K}^{\prime}=\cup_{i\in\mathcal{K}}\\{i+tn_{1};t=0,\ldots,q_{t}-1\\}\subset[n].$

Furthermore, let

$\mathcal{L}_{i}=\\{(i-1)n_{1}+s;s=1,\ldots,n_{1}\\}\ \text{ for every
}i\in[q_{t}].$

Then

$\mathscr{C}^{\prime}=\\{\mathcal{K}^{\prime}_{1}\vee_{[n]}\mathcal{K}^{\prime}_{2};\mathcal{K}_{1}\vee_{[n_{1}]}\mathcal{K}_{2}\in\mathscr{C}\\}$

covers all the edges of $K_{n}$ within the sets
$\mathcal{L}_{1},\mathcal{L}_{2},...,\mathcal{L}_{q_{t}}$. So

$\widehat{\mathscr{C}}=\mathscr{C}^{\prime}\cup\\{\mathcal{L}_{i}\vee_{[n]}\mathcal{L}_{j},i,j\in[q_{t}],i\neq
j\\}$

is a set-join cover of $K_{n}$ with
$|\widehat{\mathscr{C}}|=\sum_{i=1}^{t}q_{i}$.

To complete the proof, we need to show
$\mathrm{st}_{+}(K_{n})\geq\min\\{\sum_{i=1}^{t}q_{i};n\leq\prod_{i=1}^{t}q_{i}\\}$.
Let us fix $n$ and define $m=\max\\{t;s(t)=~{}s(n)\\}$. From Theorem 4.2 we
know that $m$ is the largest positive integer that satisfies
$\mathrm{st}_{+}(K_{n})=\mathrm{st}_{+}(K_{m})$. In particular, $m$ has one of
the forms $m=3^{i},m=4\cdot 3^{i-1}$, or $m=2\cdot 3^{i}$. In each case we can
write $m=\prod_{k=1}^{t}q_{k}$, where $q_{j}\in\\{2,3,4\\}$ for all $j\in[t]$.
It is straightforward to check that the equality
$\mathrm{st}_{+}(K_{m})=\sum_{i=1}^{t}q_{i}$ holds in each of these cases. ∎

######  Remark 4.6.

An optimal set-join cover of $K_{6}$ is given in Example 2.15. Following the
construction outlined in the proof of Proposition 4.5, we can produce examples
of optimal set-join covers of $K_{n}$ for every $n\geq 2$.

If $n=2,3,4,5$, then $\mathrm{st}_{+}(K_{n})=n$, and the set-join cover
$\mathscr{C}$, where all the components of $\mathscr{C}$ are singletons and
$G(\mathscr{C})=K_{n}$, is an OSJ cover of $K_{n}$. Note that for $n=2$ and
for $n=3$ these OSJ covers are unique. For $n=4$ this set-join cover is not
unique, since the factorization $4=2^{2}$ gives rise to an OSJ cover
$\mathscr{C}^{\prime}$ of $K_{4}$ with $G(\mathscr{C}^{\prime})=2K_{2}$. In
the case $n=5$ this set-join cover is also not unique, since the factorization
$6=2\cdot 3$ gives rise to an OSJ cover $\mathscr{C}^{\prime}$ of $K_{5}$ with
$G(\mathscr{C}^{\prime})=K_{2}\cup K_{3}$.

Suppose that $n\geq 6$ and let $m=\max\\{t;s(t)=s(n)\\}$. An inductive
construction outlined in the proof of Proposition 4.5 gives an OSJ cover
$\mathscr{C}$ of $K_{m}$, which we can restrict to $K_{n}$ to obtain an OSJ
cover of $K_{n}$. Let us look at some properties of an OSJ cover $\mathscr{C}$
constructed in this way, for a few choices of $n$:

  * •

For $n=3^{i}$, all components of $\mathscr{C}$ have cardinally $3^{i-1}$, and
for each $\mathcal{K}\in\mathscr{C}$ there exist two other components
$\mathcal{K}^{\prime},\mathcal{K}^{\prime\prime}\in V(\mathscr{C})$, so that
$\mathcal{K},\mathcal{K}^{\prime}$ and $\mathcal{K}^{\prime\prime}$ and
pairwise disjoint.

  * •

For $n=3^{i}-1$, $2i$ components have cardinality $3^{i-1}$, and $i$
components have cardinality $3^{i-1}-1$. For each $\mathcal{K}\in\mathscr{C}$
there exist two other components
$\mathcal{K}^{\prime},\mathcal{K}^{\prime\prime}\in V(\mathscr{C})$, so that
$\mathcal{K},\mathcal{K}^{\prime}$ and $\mathcal{K}^{\prime\prime}$ and
pairwise disjoint.

  * •

For $n=2\cdot 3^{i}$, the largest two components
$\mathcal{K},\mathcal{K}^{\prime}\in V(\mathscr{C})$ are disjoint and have
cardinality $3^{i}$. All other components have cardinality $2\cdot 3^{i-1}$.

  * •

For $n=2\cdot 3^{i}-1$, the largest two components in $V(\mathscr{C})$ are
disjoint, one has $3^{i}$ and the other $3^{i}-1$ elements. There are $2i$
components of cardinality $2\cdot 3^{i-1}$, and $i$ components of cardinality
$2\cdot 3^{i-1}-1$.

Having constructed an OSJ cover of $K_{n}$ for each $n\in\mathbb{N}$, we want
to consider what properties any OSJ cover $\mathscr{C}$ of $K_{n}$ has to
have. In particular, we consider the components of minimal and maximal
cardinality.

######  Lemma 4.7.

Let $m,n\in\mathbb{N}$, $n<m$,
$\mathrm{st}_{+}(K_{n})=\mathrm{st}_{+}(K_{m})$, and let $\mathscr{C}$ be an
OSJ cover of $K_{m}$. Then any component $\mathcal{K}\in V(\mathscr{C})$
satisfies $|\mathcal{K}|>m-n$.

###### Proof.

Let $\mathscr{C}$ be an OSJ cover of $K_{m}$, and $\mathcal{K}\in
V(\mathscr{C})$. Let $\mathscr{C}^{\prime}$ be obtained from $\mathscr{C}$ by
removing $\mathcal{K}$, and elements from $\mathcal{K}$ from all components of
$\mathscr{C}$. Then $\mathscr{C}^{\prime}$ is a set-join cover of
$K_{m-|\mathcal{K}|}$ with $|\mathscr{C}^{\prime}|\leq|\mathscr{C}|-1$. From
$\mathrm{st}_{+}(K_{n})=\mathrm{st}_{+}(K_{m})$ we get $m-|\mathcal{K}|<n$, as
required. ∎

######  Corollary 4.8.

Let $\mathscr{C}$ be an OSJ cover of $K_{n}$ and $\mathcal{K}\in
V(\mathscr{C})$.

  1. 1.

If $n=3^{i}$, then $|\mathcal{K}|\geq 3^{i-1}$.

  2. 2.

If $n=4\cdot 3^{i}$, then $|\mathcal{K}|\geq 3^{i}$.

  3. 3.

If $n=2\cdot 3^{i}$, then $|\mathcal{K}|\geq 2\cdot 3^{i-1}$.

###### Proof.

Let $n=3^{i}$, then $\mathrm{st}_{+}(K_{3^{i}})=\mathrm{st}_{+}(K_{2\cdot
3^{i-1}+1})$ by Theorem 4.2. Hence, $|\mathcal{K}|>3^{i-1}-1$ by Lemma 4.7.
The other two items are proved in the same way. ∎

######  Proposition 4.9.

Suppose that $n\in\mathbb{N}$ satisfies one of the following conditions:
$n\in\\{4,5,7,8\\}$, or $3^{i}+1\leq n\leq 2\cdot 3^{i}-2$ for some $i\geq 2$,
or $2\cdot 3^{i}+1\leq n\leq 3^{i+1}-2$ for some $i\geq 2$. Then an OSJ cover
of $K_{n}$ is not essentially unique.

###### Proof.

In Remark 4.6 we have already seen that an OSJ cover of $K_{n}$ is not
essentially unique for $n\in\\{4,5\\}$. $K_{8}$ has two essentially different
OSJ covers: one arising form the factorization $8=2\cdot 4$, and the other
form $8\leq 3^{2}$. In the first case the cover has the graph $K_{2}\cup
K_{4}$, and in the second case the cover has the graph $2K_{3}$. Since
$s(8)=6$ both covers are optimal. Restrictions of those covers to the elements
of $K_{7}$ gives two OSJ covers of $K_{7}$.

Suppose that $n+2\leq m$ and $s(n)=s(m)$. We will show that in this case an
OSJ cover of $K_{n}$ is not essentially unique. Let $\mathscr{C}$ be an OSJ
cover for $K_{m}$ and let $\mathcal{K}\in V(\mathscr{C})$ be a component of
$\mathscr{C}$ of minimal cardinality. Then $|\mathcal{K}|>m-n\geq 2$, by Lemma
4.7. Now, choose $m-n$ vertices in $\mathcal{K}$ and remove them from $K_{m}$
and $\mathscr{C}$ to obtain a set-join cover $\mathscr{C}^{\prime}$ of
$K_{n}$. The set-join cover $\mathscr{C}^{\prime}$ contains a component of
cardinality $|\mathcal{K}|-(m-n)$. Next, choose $m-n$ vertices in $K_{m}$ so
that they do not all belong to the same component of $\mathscr{C}$. This is
possible since $m-n\geq 2$, and $m\geq 9$, so $m\geq|V(\mathscr{C})|+3$.
Remove them from $K_{m}$ and $\mathscr{C}$ to obtain a set-join cover
$\mathscr{C}^{\prime\prime}$ of $K_{n}$. The set-join cover
$\mathscr{C}^{\prime\prime}$ does not contain a component of cardinality
$|\mathcal{K}|-(m-n)$, so it is essentially different from
$\mathscr{C}^{\prime}$.

For $n=4\cdot 3^{i}=2^{2}\cdot 3^{i}$ the construction in Proposition 4.5
gives rise to two set-join covers $\mathscr{C}_{1}$ and $\mathscr{C}_{2}$, one
with the graph $K_{4}\cup iK_{3}$, and one with the graph $2K_{2}\cup iK_{3}$.
Both covers are optimal, proving that in this case OSJ cover is not unique.
Now let $m$ satisfy $m<n$ and $s(m)=s(n)$. By restricting $\mathscr{C}_{1}$
and $\mathscr{C}_{2}$ to $[m]$, we get two OSJ covers of $K_{m}$ with
different graphs, proving that OSJ covers of $K_{m}$ are not essentially
unique. ∎

Before we move to more general cases, we show in the example below that
$K_{6}$ has essentially unique OSJ cover.

######  Example 4.10.

Let $V(K_{6})=[6]$ and let $\mathscr{C}$, with
$V(\mathscr{C})=\\{\mathcal{K}_{i};i=1,\ldots,5\\}$, be an OSJ cover of
$K_{6}$. In addition, we assume $|\mathcal{K}_{1}|\geq|\mathcal{K}_{i}|$,
$i=2,3,4,5$, and $\mathcal{K}_{1}\vee_{[6]}\mathcal{K}_{2}\in\mathscr{C}$.

Next we show that $|\mathcal{K}_{1}|=3$. Since $\mathcal{K}_{1}$ and
$\mathcal{K}_{2}$ are disjoint, the set-joins of $\mathscr{C}$ with components
$\mathcal{K}_{3}$, $\mathcal{K}_{4}$, and $\mathcal{K}_{5}$, need to cover all
the edges between the elements of $\mathcal{K}_{1}$. In particular, the set
$V_{1}=\\{\mathcal{K}_{3}\cap\mathcal{K}_{1},\mathcal{K}_{4}\cap\mathcal{K}_{1},\mathcal{K}_{5}\cap\mathcal{K}_{1}\\}$
needs to contain a component set of a set-cover for a complete graph with the
vertex set $\mathcal{K}_{1}$. Since $s(4)=4$, this excludes
$|\mathcal{K}_{1}|\geq 4$. On the other hand, $s(6)=s(5)$ implies that
$V(\mathscr{C})$ doesn’t contain singletons by Lemma 4.7. If
$|\mathcal{K}_{i}|=2$ for all $i\in[5]$, then we may without loss of
generality assume that $\mathcal{K}_{1}=\\{1,2\\}$ and
$\mathcal{K}_{2}\subset\\{3,4,5,6\\}$. Since the edge $\\{1,2\\}$ needs to be
covered, we may also assume that $\mathcal{K}_{3}=\\{1,3\\}$ and
$\mathcal{K}_{4}=\\{2,4\\}$. Similarly, since the edge $\\{5,6\\}$ needs to be
covered, we may assume $5\in\mathcal{K}_{2}$, $6\in\mathcal{K}_{5}$ and
$\mathcal{K}_{2}\cap\mathcal{K}_{5}=\emptyset$. Now we have
$j\in\mathcal{K}_{2}$ for $j=3$ or $j=4$. In either case, the edge $\\{j,5\\}$
cannot be covered by the components $\mathcal{K}_{i}$, $i=1,\ldots,5$.

At this point we can assume $\mathcal{K}_{1}=\\{1,2,3\\}$, and deduce that
$V_{1}$ is a component set of an OSJ cover for the complete graph on
$\mathcal{K}_{1}$, hence $V_{1}=\\{\\{1\\},\\{2\\},\\{3\\}\\}$ and
$\\{\mathcal{K}_{3}\vee_{[6]}\mathcal{K}_{4},\mathcal{K}_{4}\vee_{[6]}\mathcal{K}_{5},\mathcal{K}_{5}\vee_{[6]}\mathcal{K}_{3}\\}\subset\mathscr{C}$.
Now we know that $\mathcal{K}_{3}$, $\mathcal{K}_{4}$ and $\mathcal{K}_{5}$
are pairwise disjoint, and without loss of generality we may assume
$\mathcal{K}_{1}\cap\mathcal{K}_{3}=\\{1\\}$,
$\mathcal{K}_{1}\cap\mathcal{K}_{4}=\\{2\\}$ and
$\mathcal{K}_{1}\cap\mathcal{K}_{5}=\\{3\\}$.

Next we argue that $\mathcal{K}_{2}=\\{4,5,6\\}$. Assume that
$4\not\in\mathcal{K}_{2}$, and note that $4$ can be contained in at most one
of $\mathcal{K}_{3}$, $\mathcal{K}_{4}$ and $\mathcal{K}_{5}$. Without loss of
generality let $4\in\mathcal{K}_{3}$. This leads to a contradiction, since the
edge $\\{1,4\\}$ clearly cannot be covered. Arguing as above, we prove that
$\\{\mathcal{K}_{3}\cap\mathcal{K}_{2},\mathcal{K}_{4}\cap\mathcal{K}_{2},\mathcal{K}_{5}\cap\mathcal{K}_{2}\\}=\\{\\{4\\},\\{5\\},\\{6\\}\\}$.
We may assume without loss of generality that
$\mathcal{K}_{3}=\\{1,4\\},\mathcal{K}_{4}=\\{2,5\\},$ and
$\mathcal{K}_{5}=\\{3,6\\}$. We obtain that

$\mathscr{C}=\\{\mathcal{K}_{1}\vee_{[6]}\mathcal{K}_{2},\mathcal{K}_{3}\vee_{[6]}\mathcal{K}_{4},\mathcal{K}_{4}\vee_{[6]}\mathcal{K}_{5},\mathcal{K}_{5}\vee_{[6]}\mathcal{K}_{3}\\}$

and $G(\mathscr{C})=K_{2}\cup K_{3}$.

Notice that an OSJ cover of $K_{6}$ constructed above is not unique, since by
permuting the vertices of $K_{6}$ we can obtain a different set-join cover of
$K_{6}$.

To identify $K_{n}$ with essentially unique OSJ covers, we need to extend the
arguments seen in Example 4.10. To do so, we depend on a selection of
observations, that we do not prove here, but that can be deduced from the
proof of Theorem 4.2 given in [6, Ch. 18].

######  Lemma 4.11.

([9, 6]) Let $\mathscr{C}$ be an OSJ cover of $K_{n}$ for some $n\geq 4$. Then

$s(n)=\min\left\\{k+s\left(\left\lceil\frac{n}{k}\right\rceil\right);k=2,3,4,5\right\\}.$
(3)

Let $\mathcal{M}_{n}$ be the set of all $k\in\\{2,3,4,5\\}$ for which the
minimum is achieved, and $\mathcal{K}_{1}$ a component of $\mathscr{C}$ of
maximal cardinality. Then there exists $k_{0}\in\mathcal{M}_{n}$ so that:

  1. 1.

$\mathcal{K}_{1}$ is disjoint with precisely $k_{0}-1$ components
$\mathcal{K}_{2},\ldots,\mathcal{K}_{k_{0}}\in V(\mathscr{C})$.

  2. 2.

The restriction of $\mathscr{C}$ to $\mathcal{K}_{1}$ is an OSJ cover of the
complete graph on $\mathcal{K}_{1}$, and the restriction of $\mathscr{C}$ to
$\mathcal{S}=[n]\setminus\cup_{j=2}^{k_{0}}\mathcal{K}_{i}$ is an OSJ cover of
the complete graph on $\mathcal{S}$.

  3. 3.

$s(|\mathcal{S}|)=s(|\mathcal{K}_{1}|)=s(\lceil\frac{n}{k_{0}}\rceil)=s(n)-k_{0}$.

######  Proposition 4.12.

Suppose that $n\in\mathbb{N}$, $n=3^{i}$ or $n=2\cdot 3^{i}$ for some $i\geq
1$. Then $K_{n}$ has essentially unique OSJ cover.

###### Proof.

We will prove the claim by induction on $i$. Since we have already seen that
$K_{3}$ and $K_{6}$ have essentially unique OSJ covers, the base of induction
is established. We assume $i\geq 2$, and that the claim holds for $n=3^{i-1}$
and $n=2\cdot 3^{i-1}$. Throughout the proof we also assume that $\mathscr{C}$
is an OSJ cover of $K_{n}$, and $\mathcal{K}_{1}\in V(\mathscr{C})$ is one of
its components with maximal cardinality.

First we want to determine the parameter $k_{0}$ from Lemma 4.11. Combining
(1) and (3) it is straightforward to see that for $i\geq 2$ we have
$\mathcal{M}_{3^{i}}=\\{3\\}$ and $\mathcal{M}_{2\cdot 3^{i}}=\\{2,3\\}$.
Suppose that for $n=2\cdot 3^{i}$ we have $k_{0}=3$. Applying Lemma 4.11 we
get $s(|\mathcal{K}_{1}|)=s(|\mathcal{S}|)=s(\lceil\frac{n}{3}\rceil)=s(2\cdot
3^{i-1})=3i-1$. This restricts $4\cdot
3^{i-2}<|\mathcal{K}_{1}|\leq|\mathcal{S}|\leq 2\cdot 3^{i-1}$. From

$\displaystyle|\mathcal{K}_{2}\cup\mathcal{K}_{3}|$ $\displaystyle\leq
2|\mathcal{K}_{1}|\leq 4\cdot 3^{i-1},$
$\displaystyle|\mathcal{K}_{2}\cup\mathcal{K}_{3}|$
$\displaystyle=n-|\mathcal{S}|\geq 2\cdot 3^{i}-2\cdot 3^{i-1}=4\cdot 3^{i-1}$

we conclude that $|\mathcal{K}_{2}\cup\mathcal{K}_{3}|=4\cdot 3^{i-1}$. Hence,
$\mathcal{K}_{2}\cap\mathcal{K}_{3}=\emptyset$, and $|\mathcal{K}_{i}|=2\cdot
3^{i-1}$ for $i=1,2,3$. Note that for $i=1,2,3$,
$|\mathscr{C}[\mathcal{K}_{i}]|=|\mathscr{C}|-3$, hence
$\mathcal{C}[\mathcal{K}_{i}]$ is an OSJ cover of $\mathcal{K}_{i}$, and by
the induction hypothesis essentially unique. By Remark 4.6,
$\mathscr{C}[\mathcal{K}_{i}]$ has two components of cardinality $3^{i-1}$,
and all other components of cardinality $2\cdot 3^{i-2}$. Let
$\mathcal{K}_{4}$ be one of the components of $\mathscr{C}$ with the largest
intersection with $\mathcal{K}_{1}$. From
$|\mathscr{C}[\mathcal{K}_{i}]|=|\mathscr{C}|-3$ for $i=2,3$, we deduce that
$\mathcal{K}_{4}\cap\mathcal{K}_{i}\neq\emptyset$ for $i=2,3$. Then
$|\mathcal{K}_{4}\cap\mathcal{K}_{1}|=3^{i-1}$ and
$|\mathcal{K}_{4}\cap\mathcal{K}_{i}|\geq 2\cdot 3^{i-2}$ for $i=2,3$. It
follows that $|\mathcal{K}_{4}|\geq 3^{i-1}+2\cdot 3^{i-2}+2\cdot
3^{i-2}>2\cdot 3^{i-1}=|\mathcal{K}_{1}|$, a contradiction with maximality of
$|\mathcal{K}_{1}|$.

Let $n=3^{i}$ for $i\geq 2$, and hence $s(n)=3i$ and $k_{0}=3$. From Lemma
4.11 we get $s(|\mathcal{K}_{1}|)=s(|\mathcal{S}|)=3(i-1)$, implying
$|\mathcal{K}_{1}|\leq|\mathcal{S}|\leq 3^{i-1}$. Hence,

$\displaystyle|\mathcal{K}_{2}\cup\mathcal{K}_{3}|$ $\displaystyle\leq
2|\mathcal{K}_{1}|\leq 2\cdot 3^{i-1},$
$\displaystyle|\mathcal{K}_{2}\cup\mathcal{K}_{3}|$
$\displaystyle=n-|\mathcal{S}|\geq 3^{i}-3^{i-1}=2\cdot 3^{i-1}.$

As above, we conclude that $\mathcal{K}_{1}$, $\mathcal{K}_{2}$, and
$\mathcal{K}_{3}$ are pairwise disjoint, their union is $[n]$, and they all
have $\frac{n}{3}=3^{i-1}$ elements. Since we are allowing isomorphism of
graphs, $\mathcal{K}_{j}$, $j\in[3]$, can be taken to be any three subsets of
$[n]$ that satisfy those conditions. Furthermore,
$\mathscr{C}[\mathcal{K}_{j}]$, $j\in[3]$, is an OSJ cover of the complete
graph on $\mathcal{K}_{j}$ and by the induction hypothesis essentially unique.
Since $\mathcal{K}_{j}$, $j\in[3]$, are pairwise disjoint and
$\cup_{j\in[3]}\mathcal{K}_{j}=[n]$ this implies essential uniqueness of
$\mathscr{C}$.

The proof for $n=2\cdot 3^{i}$, $i\geq 2$ with $s(n)=2+3i$ and $k_{0}=2$ is
very similar and we leave it to the reader. ∎

######  Remark 4.13.

With arguments, akin to the ones in the proof of Proposition 4.12, it can be
shown that for $n=4\cdot 3^{i}$ the graph $K_{n}$ has exactly two essentially
different OSJ covers. In particular, the components of any OSJ cover of
$K_{n}$ either satisfy $|\mathcal{K}_{1}|=\ldots=|\mathcal{K}_{4}|=2\cdot
3^{i}$, $|\mathcal{K}_{5}|=\ldots=|\mathcal{K}_{3i+4}|=4\cdot 3^{i-1}$ or
$|\mathcal{K}_{1}|=\ldots=|\mathcal{K}_{3i}|=4\cdot 3^{i-1}$,
$|\mathcal{K}_{3i+1}|=\ldots=|\mathcal{K}_{3i+4}|=3^{i}$.

Notice that in this case two possible values of $k_{0}\in\mathcal{M}_{n}$ can
be attained, namely in the first cover we have $k_{0}=2$ and in the second
cover $k_{0}=3$.

The following proposition covers the remaining cases with essentially unique
OSJ cover. Only a sketch of the proof is given. The proof with all the
technical details included would be rather long, and would not give
significant new insights to the reader.

######  Proposition 4.14.

Let $n\in\mathbb{N}$ be of the form $n=3^{i}-1$ for some $i\geq 3$, or of the
form $n=2\cdot 3^{i}-1$ for some $i\geq 2$. Then $K_{n}$ has essentially
unique OSJ cover.

_Sketch of the proof._ We claim that $K_{n}$ has essentially unique OSJ cover
for every $n$ in the set

$\mathcal{N}=\\{n\in\mathbb{N},n=3^{i}-1,i\geq
3\\}\cup\\{n\in\mathbb{N},n=2\cdot 3^{i}-1,i\geq 2\\}.$

This claim can be proved by induction, where the base of induction needs to be
established for $n\in\\{17,26\\}$. (This is left to the reader.) Next we fix
$n$, and assume that the claim holds for $m\in\mathcal{N}$, with $m<n$. We
assume notation and definitions from Lemma 4.11.

For $n=3^{i}-1,i\geq 3$, we have $\mathcal{M}_{n}=\\{3\\}$. Lemma 4.11 implies
$s(|\mathcal{K}_{1}|)=s(|\mathcal{S}|)=3(i-1)$. From here we get:

$|\mathcal{K}_{2}\cup\mathcal{K}_{3}|\geq n-|\mathcal{S}|\geq 2\cdot
3^{i-1}-1.$

Since $\mathcal{K}_{1}\cap(\mathcal{K}_{2}\cup\mathcal{K}_{3})=\emptyset$ and
$\mathcal{K}_{1}\cup\mathcal{K}_{2}\cup\mathcal{K}_{3}=[3^{i}-1]$, we conclude
that $|\mathcal{K}_{1}|=3^{i-1}$ and
$|\mathcal{K}_{2}\cup\mathcal{K}_{3}|=2\cdot 3^{i-1}-1$. Note that
$|\mathscr{C}[\mathcal{K}_{2}\cup\mathcal{K}_{3}]|=|\mathcal{C}|-1=3i-1$,
since $\mathcal{K}_{1}\cap(\mathcal{K}_{2}\cup\mathcal{K}_{3})=\emptyset$.
Hence $\mathscr{C}[\mathcal{K}_{2}\cup\mathcal{K}_{3}]$ is an OSJ set-join
cover of the complete graph on $\mathcal{K}_{2}\cup\mathcal{K}_{3}$, and it is
by the induction hypothesis essentially unique. By Remark 4.6 we know that its
largest components are disjoint (and of order $3^{i-1}$ and $3^{i-1}-1$). This
implies that $\mathcal{K}_{2}$ and $\mathcal{K}_{3}$ are disjoint,
$|\mathcal{K}_{1}|=|\mathcal{K}_{2}|=3^{i-1}$, and
$|\mathcal{K}_{3}|=3^{i-1}-1$. The claim is proved by noting that
$\mathscr{C}[\mathcal{K}_{j}]$ is an essentially unique OSJ cover of the
complete graph on $\mathcal{K}_{j}$ for $j\in[3]$.

For $n=2\cdot 3^{i}-1,i\geq 2$, we have $\mathcal{M}_{n}=\\{2,3\\}$. The case
$k_{0}=3$ can be excluded in a similar way, as was done in the proof of
Proposition 4.12 for the case $n=2\cdot 3^{i}$. The rest of the proof of this
case is very similar to the proof for the case $n=3^{i}-1$ above, and it is
left to the reader.

Propositions 4.9, 4.12, and 4.14 completely decide the question of essential
uniqueness of OSJ covers of $K_{n}$. The result is summarized in the theorem
below.

######  Theorem 4.15.

Let $n\in\mathbb{N}$, $n\geq 2$. The graph $K_{n}$ has essentially unique OSJ
cover if and only if $n=3^{i}$ for some $i\geq 1$, $n=2\cdot 3^{i}$ for some
$i\geq 1$, $n=3^{i}-1$ for some $i\geq 3$, or $n=2\cdot 3^{i}-1$ for some
$i\geq 2$.

######  Remark 4.16.

Equations (1), (2) and (3) express $\mathrm{st}_{+}(K_{n})$ in three different
ways:

$\displaystyle\mathrm{st}_{+}(K_{n})$ $\displaystyle=\begin{cases}3i&\text{if
}\,2\cdot 3^{i-1}<n\leq 3^{i}\\\ 3i+1&\text{if }\,3^{i}<n\leq 4\cdot
3^{i-1}\\\ 3i+2&\text{if }\,4\cdot 3^{i-1}<n\leq 2\cdot 3^{i}\\\ \end{cases}$
$\displaystyle=\min\left\\{\sum_{i=1}^{t}q_{i};n\leq\prod_{i=1}^{t}q_{i}\right\\}$
$\displaystyle=\min\left\\{k+\mathrm{st}_{+}\left(K_{\left\lceil\frac{n}{k}\right\rceil}\right);k=2,3,4,5\right\\}.$

Through those expressions we have seen how OSJ covers can be constructed
recursively.

######  Remark 4.17.

In this section, an idea of constructing set-join covers from set-join covers
of smaller graphs was repeatedly used. This idea can be formalised using co-
normal products of graphs. Let $G$ and $H$ be simple graphs (with loops). The
co-normal product of $G$ and $H$, denoted by $G*H$, is the graph with the
vertex set $V(G)\times V(H)$, and the edge set

$E(G*H)=\left\\{\\{(g,h),(g^{\prime},h^{\prime})\\};\\{g,g^{\prime}\\}\in
E(G)\text{ or }\\{h,h^{\prime}\\}\in E(H)\right\\}.$

Let $\mathscr{C}_{G}$ and $\mathscr{C}_{H}$ be set-join covers of $G$ and $H$,
respectively. Using $\mathscr{C}_{G}$ and $\mathscr{C}_{H}$ we can build a
set-join cover $\mathscr{C}^{\prime}$ of $G*H$ as follows. For every
$\mathcal{K}\in V(\mathscr{C}_{G})$ define
$\mathcal{K}^{\prime}:=\\{(g,h);g\in\mathcal{K},h\in V(H)\\}$ and for every
$\mathcal{L}\in V(\mathscr{C}_{H})$ define
$\mathcal{L}^{\prime}:=\\{(g,h);g\in V(G),h\in\mathcal{L}\\}$. Then

$\mathscr{C}^{\prime}:=\\{\mathcal{K}_{1}^{\prime}\vee_{V(G*H)}\mathcal{K}_{2}^{\prime};\,\mathcal{K}_{1}\vee_{V(G)}\mathcal{K}_{2}\in\mathscr{C}_{G}\\}\cup\\{\mathcal{L}_{1}^{\prime}\vee_{V(G*H)}\mathcal{L}_{2}^{\prime};\,\mathcal{L}_{1}\vee_{V(H)}\mathcal{L}_{2}\in\mathscr{C}_{H}\\}$

is a set-join cover of $G*H$. In particular,

$\mathrm{st}_{+}(G*H)\leq\mathrm{st}_{+}(G)+\mathrm{st}_{+}(H).$ (4)

Since $K_{p}*K_{q}$ is isomorphic to $K_{pq}$, we see from above, that the
inequality (4) can be strict (for example for $p=q=5$), but it cannot be
improved in general (it is equality for example for $p=3^{i}$ and $q=3^{j}$).

######  Remark 4.18.

If $A\in\mathcal{S}_{n}^{+}$, then its Boolean rank is the NMF-rank of the
pattern graph of the matrix $A$ (see [4]):

$\mathrm{rk}_{01}(A)=\min\\{\mathrm{rk}_{+}(B);B\in\mathcal{S}^{+}(G(A))\\}.$

It follows immediately from (1) that $\mathrm{st}_{+}(K_{n})$ behaves
asymptotically as $\mathrm{st}_{+}(K_{n})\sim\frac{3}{\log 3}\log n$. On the
other hand, if $A\in\mathcal{S}^{+}(K_{n})$ its Boolean rank
$\mathrm{rk}_{01}(A)$ is the minimal $k$ such that $n\leq\binom{k}{\lfloor
k/2\rfloor}$, [4]. It follows that NMF-rank of such matrix is asymptotically
bounded below by $\frac{1}{\log 2}\log n$. It means that the minimal SNT-rank
and the minimal NMF-rank that can be achieved on the complete graphs have the
same order of asymptotic behaviour, but the constant differs by factor
$1.893$.

##  5 Concluding remarks

Finding $\mathrm{st}_{+}(G)$ for a given graph $G$ is well-defined
combinatorial optimisation problem, that is of independent interest. In this
section we highlight a few settings, where the theory of this paper naturally
appears and provides relevant groundwork.

The most immediate application of $\mathrm{st}_{+}(G)$ is the study
$\mathrm{st}_{+}(A)$ and SN-Trifactorizations of $A\in\mathcal{S}_{n}^{+}$.
Below we offer an example how this can be done for a given matrix.

######  Example 5.1.

The matrix

$A=\left(\begin{array}[]{cccc}4&1&1&4\\\ 1&1&2&0\\\ 1&2&0&3\\\ 4&0&3&1\\\
\end{array}\right)$

has rank $3$. Let $G:=G(A)$, and let $H$ be an induced subgraph of $G$ on the
set $\\{2,3,4\\}$. Since any matrix in $\mathcal{S}^{+}(H)$ is invertible, we
have $\mathrm{st}_{+}(G)\geq 3$. Note also that $H$ has the unique OSJ cover
$\mathscr{C}_{H}$, where each component in $V(\mathscr{C}_{H})$ is a
singleton.

The set-join cover $\mathscr{C}_{H}$ can be extended to a set-join cover of
$G$:

$\mathscr{C}=\\{\mathcal{K}_{1}\vee_{[4]}\mathcal{K}_{1},\mathcal{K}_{1}\vee_{[4]}\mathcal{K}_{2},\mathcal{K}_{2}\vee_{[4]}\mathcal{K}_{3},\mathcal{K}_{3}\vee_{[4]}\mathcal{K}_{3}\\},$

where

$2\in\mathcal{K}_{1},3\in\mathcal{K}_{2},4\in\mathcal{K}_{3},$

and $1$ is an element of at least two of $\mathcal{K}_{i}$, $i=1,2,3$. This
describes all possible set-join covers of $G$, and, in particular, shows that
$\mathrm{st}_{+}(G)=3$.

Suppose that $\mathrm{st}_{+}(A)=3$ and let $A=BCB^{T}$ be an optimal SN-
Trifactorization. By observations above and Theorem 2.11 the matrix $B$ has
the form

$B=\left(\begin{array}[]{c}{\bf b}^{T}\\\ D\\\ \end{array}\right),$

where ${\bf b}\in\mathbb{R}_{+}^{3}$ has at least two nonzero entries and $D$
is an invertible nonnegative diagonal matrix. It follows that

$A=BCB^{T}=\left(\begin{array}[]{c}{\bf b}^{T}\\\ D\\\
\end{array}\right)C\left(\begin{array}[]{cc}{\bf b}&D\\\
\end{array}\right)=\left(\begin{array}[]{cc}{\bf b}^{T}C{\bf b}&{\bf
b}^{T}CD\\\ DC{\bf b}&DCD\\\ \end{array}\right),$

so

$DCD=\left(\begin{array}[]{ccc}1&2&0\\\ 2&0&3\\\ 0&3&1\\\
\end{array}\right)\text{ and }DC{\bf b}=\left(\begin{array}[]{c}1\\\ 1\\\ 4\\\
\end{array}\right).$

Thus

${\bf b}=D(DCD)^{-1}(DC{\bf b})=D\left(\begin{array}[]{ccc}1&2&0\\\ 2&0&3\\\
0&3&1\\\ \end{array}\right)^{-1}\left(\begin{array}[]{c}1\\\ 1\\\ 4\\\
\end{array}\right)=D\left(\begin{array}[]{c}-1\\\ 1\\\ 1\\\
\end{array}\right),$

which means that vector ${\bf b}$ has a negative entry, a contradiction. It
follows that $\mathrm{st}_{+}(A)=4$.

Given an $n\times n$ nonnegative symmetric matrix $A$ there are existing
algorithms that given $k$ find matrices $B\in\mathbb{R}_{+}^{n\times k}$ and
$C\in\mathcal{S}_{k}^{+}$ that minimize $\left\|{A-BCB^{T}}\right\|_{F}$, [8].
Using the theory developed in this paper it should be possible to extend such
algorithms to find matrices $B\in\mathbb{R}_{+}^{n\times k}$ and
$C\in\mathcal{S}_{k}^{+}$ where $BCB^{T}$ has some prescribed zero-nonzero
pattern.

In Remark 2.14 we have seen an interpretation of $\mathrm{st}_{+}(G)$ as the
minimal number of subsets of a given set $V$ that need to be formed if we want
to organize required and forbidden interactions as given by the graph $G$.
This interpretation motivates variations of the question considered in this
paper. For example, minimizing the number of meetings corresponds to finding
set-join covers $\mathscr{C}$ containing minimal number of set-joins. Posing
restrictions on the size of groups would mean looking for set-join covers
$\mathscr{C}$ with restrictions on the cardinalities of the elements in
$V(\mathscr{C})$. In addition to having pairs of elements that are required
and pairs that are forbidden to interact, we may have pairs of elements that
can (but are not required to) interact. To solve this question we would be
looking for partial set-join covers of $G$.

## Acknowledgments

Damjana Kokol Bukovšek acknowledges financial support from the ARIS (Slovenian
Research and Innovation Agency, research core funding No. P1-0222).

## References

  * [1] Abraham Berman and Naomi Shaked-Monderer, _Completely positive matrices_ , World Scientific Publishing Co., Inc., River Edge, NJ, 2003. MR 1986666
  * [2] Richard A. Brualdi and Herbert J. Ryser, _Combinatorial matrix theory_ , paperback ed., Encyclopedia of Mathematics and its Applications, vol. 39, Cambridge University Press, New York, 2013. MR 3469704
  * [3] Mao Cheng Cai, _On a problem of Katona on minimal completely separating systems with restrictions_ , Discrete Math. 48 (1984), no. 1, 121–123. MR 732208
  * [4] Nicolas Gillis, _Nonnegative matrix factorization_ , SIAM, 2020.
  * [5] Frank J. Hall, Zhongshan Li, and Di Wang, _Symmetric sign pattern matrices that require unique inertia_ , Linear Algebra Appl. 338 (2001), 153–169. MR 1861120
  * [6] Ross Honsberger, _Mathematical gems. III_ , The Dolciani Mathematical Expositions, vol. 9, Mathematical Association of America, Washington, DC, 1985\. MR 801393
  * [7] Damjana Kokol Bukovšek and Helena Šmigoc, _Symmetric nonnegative matrix trifactorization_ , Linear Algebra Appl. 665 (2023), 36–60. MR 4547308
  * [8] Lu Lin and Zhong-Yun Liu, _An alternating projected gradient algorithm for nonnegative matrix factorization_ , Appl. Math. Comput. 217 (2011), no. 24, 9997–10002. MR 2806386
  * [9] Andrew Chi Chih Yao, _On a problem of Katona on minimal separating systems_ , Discrete Math. 15 (1976), no. 2, 193–199. MR 422036