#  Unmixedness of some weighted oriented graphs

Lourdes Cruz<EMAIL_ADDRESS>Departamento de Matemáticas
Centro de Investigación y de Estudios Avanzados del Instituto Politécnico
Nacional
Apartado Postal 14–740, Ciudad de México
07000 México Yuriko Pitones<EMAIL_ADDRESS>Departamento de
Matemáticas
Centro de Investigación y de Estudios Avanzados del Instituto Politécnico
Nacional
Apartado Postal 14–740, Ciudad de México
07000 México Enrique Reyes<EMAIL_ADDRESS>Departamento de
Matemáticas
Centro de Investigación y de Estudios Avanzados del Instituto Politécnico
Nacional
Apartado Postal 14–740, Ciudad de México
07000 México

( )

###### Abstract

Let $D=(G,\mathcal{O},w)$ be a weighted oriented graph whose edge ideal is
$I(D)$. In this paper, we characterize the unmixed property of $I(D)$ for each
one of the following cases: $G$ is an $SCQ$ graph; $G$ is a chordal graph; $G$
is a simplicial graph; $G$ is a perfect graph; $G$ has no $4$\- or $5$-cycles;
$G$ is a graph without $3$\- and $5$-cycles; and ${\rm girth}(G)\geqslant 5$.

Keywords: Weighted oriented graphs, edge ideal, unmixed ideal, $SCQ$ graph,
perfect graph.

##  1 Introduction

A weighted oriented graph $D$ is a triplet $(G,\mathcal{O},w)$, where $G$ is a
simple graph whose vertex set is $V(G)$; $\mathcal{O}$ is an edge orientation
of $G$ (an assignment of a direction to each edge of $G$); and $w$ is a
function $w:V(G)\to\mathbb{N}$. In this case, $G$ is called the underlying
graph of $D$. The vertex set of $D$ is $V(D):=V(G)$, the edge set of $D$,
denoted by $E(D)$, is the set of oriented edges of the oriented graph
$(G,\mathcal{O})$. The _weight_ of $x\in V(D)$ is $w(x)$ and we denote the set
$\\{x\in V(D)\mid w(x)>1\\}$ by $V^{+}$. If $R=K[x_{1},\ldots,x_{n}]$ is a
polynomial ring over a field $K$, then the edge ideal of $D$ is
$I(D)=(x_{i}x_{j}^{w(x_{j})}\mid(x_{i},x_{j})\in E(D))$ where
$V(D)=\\{x_{1},\ldots,x_{n}\\}$. These ideals (introduced in [10]) generalize
the usual edge ideals of graphs (see [14]), since if $w(x)=1$ for each $x\in
V(D)$, then $I(D)$ is the edge ideal of $G$, i.e. $I(D)=I(G)$. An interest in
$I(D)$ comes from coding theory in some studies of Reed–Muller typed codes,
(see [1, 9]). Furthermore, some algebraic and combinatorial invariants and
properties of $I(D)$ have been studied in some papers [7, 8, 10, 11, 15]. In
particular, in [10] is given a characterization of the irredundant irreducible
decomposition of $I(D)$. This characterization permits studying when $I(D)$ is
unmixed, using the strong vertex covers (Definition 2.10 and Theorem 2.12).
The unmixed property of $I(D)$ have been studied when $G$ is one of the
following graphs: cycles in [10]; graphs with whiskers in [7, 10]; bipartite
graphs in [8, 10]; graphs without $3$\- $5$\- and $7$-cycles and König graphs
in [11].

In this paper, we study the unmixed property of $I(D)$ for some families of
weighted oriented graphs. In Section 2, we give the known results and
definitions that we will use in the following sections. In Section 3 (in
Theorem 3.10), we characterize when a subset of $V(D)$ is contained in a
strong vertex cover. Using this result, we characterize the unmixed property
of $I(D)$, when $G$ is a perfect graph (see Theorem 3.11). In Section 4 (in
Theorem 4.8), we characterize the unmixed property of $I(D)$ when $G$ is an
$SCQ$ graph (see Definition 2.27). These graphs generalize the graph defined
in [13] and in the context of this paper, they are important because if $G$ is
well–covered such that $G$ is simplicial, $G$ is chordal or $G$ has no some
small cycles, then $G$ is an $SCQ$ graph (see Remark 2.29 and Theorem 2.30).
In [3], using the $SCQ$ graphs the authors characterize the vertex
decomposable property of $G$ when each $5$-cycle of $G$ has at least $4$
chords. Also, in Section 4, we characterize the unmixed property of $I(D)$
when $G$ is Köning, $G$ is simplicial or $G$ is chordal (see Corollaries 4.2
and 4.9). In Section 5, we characterize the unmixed property of $I(D)$, when
$G$ has no $3$\- or $5$-cycles; or $G$ has no $4$\- or $5$-cycles; or $G$ has
girth greater than 4 (see Theorems 5.4, 5.10 and 5.13). Finally, in Section 6,
we give some examples. Our results generalize the results about the unmixed
property of $I(D)$ given in [7, 8, 10, 11], since if $G$ is well-covered and
$G$ is one of the following graphs: cycles, graphs with whiskers, bipartite
graphs, Köning graphs, or graphs without $3$-, $5$\- and $7$-cycles, then $G$
is an $SCQ$ graph.

##  2 Preliminaries

In this Section, we give some definitions and well-known results that we will
use in the following sections. Let $D=(G,\mathcal{O},w)$ be a weighted
oriented graph, recall that $V^{+}=\\{x\in V(D)\mid w(x)>1\\}$ and
$I(D)=\big{(}x_{i}x_{j}^{w(x_{j})}\mid(x_{i},x_{j})\in E(D)\big{)}$.

###### Definition 2.1

Let $x$ be a vertex of $D$, the sets

$N_{D}^{+}(x):=\\{y\mid(x,y)\in E(D)\\}\quad{\rm and}\quad
N_{D}^{-}(x):=\\{y\mid(y,x)\in E(D)\\}$

are called the out-neighbourhood and the in-neighbourhood of $x$,
respectively. The neighbourhood of $x$ is the set $N_{D}(x):=N_{D}^{+}(x)\cup
N_{D}^{-}(x)$. Furthermore, $N_{D}[x]:=N_{D}(x)\cup\\{x\\}$. Also, if
$A\subseteq V(D)$ then $N_{D}(A):=\\{b\in V(D)\mid b\in N_{D}(a)\ {\rm for\
some}\ a\in A\\}$.

###### Definition 2.2

Let $x$ be a vertex of $D$. If $N_{D}^{+}(x)=\emptyset$, then $x$ is called a
sink. On the other hand, $x$ is a source if $N_{D}^{-}(x)=\emptyset$.

###### Remark 2.3

Consider the weighted oriented graph $\tilde{D}=(G,\mathcal{O},\tilde{w})$
with $\tilde{w}(x)=1$ if $x$ is a source and $\tilde{w}(x)=w(x)$ if $x$ is not
a source. Hence, $I(\tilde{D})=I(D)$. Therefore, in this paper, we assume that
if $x$ is a source, then $w(x)=1$.

###### Definition 2.4

The degree of $x\in V(D)$ is $deg_{G}(x):=|N_{D}(x)|$ and
$N_{G}(x):=N_{D}(x)$.

###### Definition 2.5

A vertex cover $\mathcal{C}$ of $D$ (resp. of $G$) is a subset of $V(D)$
(resp. of $V(G)$), such that if $(x,y)\in E(D)$ (resp. $\\{x,y\\}\in E(G)$),
then $x\in\mathcal{C}$ or $y\in\mathcal{C}$. A vertex cover $\mathcal{C}$ of
$D$ is minimal if each proper subset of $\mathcal{C}$ is not a vertex cover of
$D$.

###### Remark 2.6

Let $\mathcal{C}$ be a vertex cover of $D$ and $e\in E(G)$. Then,
$\mathcal{C}\cap e\neq\emptyset$. Furthermore, $e\cap(\mathcal{C}\setminus
a)\neq\emptyset$ if $a\notin e$, $b\in N_{D}(a)$ and $e=\\{a,b\\}$. Hence,
$(\mathcal{C}\setminus a)\cup N_{D}(a)$ is a vertex cover of $D$.

###### Definition 2.7

Let $\mathcal{C}$ be a vertex cover of $D$, we define the following three
sets:

  * •

$L_{1}(\mathcal{C}):=\\{x\in\mathcal{C}\mid
N_{D}^{+}(x)\cap\mathcal{C}^{c}\neq\emptyset\\}$ where
$\mathcal{C}^{c}=V(D)\setminus\mathcal{C}$,

  * •

$L_{2}(\mathcal{C}):=\\{x\in\mathcal{C}\mid\mbox{$x\notin L_{1}(\mathcal{C})$
and $N^{-}_{D}(x)\cap\mathcal{C}^{c}\neq\emptyset$}\\}$,

  * •

$L_{3}(\mathcal{C}):=\mathcal{C}\setminus(L_{1}(\mathcal{C})\cup
L_{2}(\mathcal{C}))$.

###### Remark 2.8

If $\mathcal{C}$ is a vertex cover of $G$, $x\in V(G)\setminus\mathcal{C}$ and
$y\in N_{G}(x)$, then $e:=\\{x,y\\}\in E(G)$ and
$e\cap\mathcal{C}\neq\emptyset$. So, $y\in\mathcal{C}$, since
$x\notin\mathcal{C}$. Hence, $N_{G}(x)\subseteq\mathcal{C}$.

###### Remark 2.9

Let $\mathcal{C}$ be a vertex cover of $D$, then $x\in L_{3}(\mathcal{C})$ if
and only if $N_{D}[x]\subseteq\mathcal{C}$. Hence,
$L_{3}(\mathcal{C})=\emptyset$ if and only if $\mathcal{C}$ is minimal.

###### Definition 2.10

A vertex cover $\mathcal{C}$ of $D$ is strong if for each $x\in
L_{3}(\mathcal{C})$ there is $(y,x)\in E(D)$ such that $y\in
L_{2}(\mathcal{C})\cup L_{3}(\mathcal{C})=\mathcal{C}\setminus
L_{1}(\mathcal{C})$ with $y\in V^{+}$ (i.e. $w(y)>1$).

###### Definition 2.11

An ideal $I$ of a ring $R$ is unmixed if each one of its associated primes has
the same height.

###### Theorem 2.12

[10, Theorem 31] The following conditions are equivalent:

  1. (1)

$I(D)$ is unmixed.

  2. (2)

Each strong vertex cover of $D$ has the same cardinality.

  3. (3)

$I(G)$ is unmixed and $L_{3}(\mathcal{C})=\emptyset$ for each strong vertex
cover $\mathcal{C}$ of $D$.

###### Definition 2.13

The cover number of $G$ is $\tau(G):={\rm min\ }\\{|\mathcal{C}|\
\mid\mathcal{C}\ {\rm\ is\ a\ vertex\ cover\ of\ }G\\}$. Furthermore, a
$\tau$-reduction of $G$ is a collection of pairwise disjoint induced subgraphs
$H_{1},\ldots,H_{s}$ of $G$ such that $V(G)=\cup_{i=1}^{s}V(H_{i})$ and
$\tau(G)=\sum_{i=1}^{s}\tau(H_{i})$.

###### Remark 2.14

We have $\tau(G)=|\mathcal{C}_{1}|$, for some vertex cover $\mathcal{C}_{1}$.
So, $\mathcal{C}_{1}$ is minimal. Thus, by Remark 2.9,
$L_{3}(\mathcal{C}_{1})=\emptyset$. Hence, $\mathcal{C}_{1}$ is strong. Now,
if $I(D)$ is unmixed, then by (2) in Theorem 2.12,
$|\mathcal{C}|=|\mathcal{C}_{1}|=\tau(G)$ for each strong vertex cover
$\mathcal{C}$ of $D$.

###### Definition 2.15

A stable set of $G$ is a subset of $V(G)$ containing no edge of $G$. The
stable number of $G$, denoted by $\beta(G)$, is $\beta(G):={\rm max\ }\\{|S|\
\mid S{\rm\ is\ a\ stable\ set\ of\ }G\\}$. Furthermore $G$ is well–covered if
$|S|=\beta(G)$ for each maximal stable set $S$ of $G$.

###### Remark 2.16

$S$ is a stable set of $G$ if and only if $V(G)\setminus S$ is a vertex cover.
Hence, $\tau(G)=|V(G)|-\beta(G)$.

###### Remark 2.17

[11, Remark 2.12] $G$ is well-covered if and only if $I(G)$ is unmixed.

###### Definition 2.18

A collection of pairwise disjoint edges of $G$ is called a matching. A perfect
matching is a matching whose union is $V(G)$. On the other hand, $G$ is a
König graph if $\tau(G)=\nu(G)$ where $\nu(G)$ is the maximum cardinality of a
matching of $G$.

###### Definition 2.19

Let $e$ be an edge of $G$. If $\\{a,a^{\prime}\\}\in E(G)$ for each pair of
edges, $\\{a,b\\}$, $\\{a^{\prime},b^{\prime}\\}\in E(G)$ and
$e=\\{b,b^{\prime}\\}$, then we say that $e$ has the property (P). On the
other hand, we say that a matching $P$ of $G$ has the property (P) if each
edge of $P$ has the property (P).

###### Theorem 2.20

[2, Proposition 15] If $G$ is a Köning graph without isolated vertices, then
$G$ is well–covered if and only if $G$ has a perfect matching with the
property (P).

###### Definition 2.21

$\mathcal{P}=(x_{1},\ldots,x_{n})$ is a walk (resp. an oriented walk) if
$\\{x_{i},x_{i+1}\\}\in E(G)$ for $i=1,\ldots,n-1$. In this case,
$\mathcal{P}$ is a path (resp. an oriented path) if $x_{1},\ldots,x_{n}$ are
different. On the other hand, a walk (resp. an oriented walk),
$C=(z_{1},z_{2},\ldots,z_{n},z_{1})$ is a $n$-cycle (resp. an oriented
$n$-cycle) if $(z_{1},\ldots,z_{n})$ is a path (resp. is an oriented path).

###### Definition 2.22

Let $A$ be a subset of $V(G)$, then the graph induced by $A$, denoted by
$G[A]$, is the subgraph $G_{1}$ of $G$ with $V(G_{1})=A$ and $E(G_{1})=\\{e\in
E(G)\mid e\subseteq A\\}$. On the other hand, a subgraph $H$ of $G$ is induced
if there is $B\subseteq V(G)$ such that $H=G[B]$.

A cycle $C$ of $G$ is induced if $C$ is an induced subgraph of $G$.

###### Definition 2.23

A weighted oriented graph
$D^{\prime}=(G^{\prime},\mathcal{O}^{\prime},w^{\prime})$ is a weighted
oriented subgraph of $D=(G,\mathcal{O},w)$, if
$(G^{\prime},\mathcal{O}^{\prime})$ is an oriented subgraph of
$(G,\mathcal{O})$ and $w^{\prime}(x)=w(x)$ for each $x\in V(G^{\prime})$.
Furthermore, $D^{\prime}$ is an induced weighted oriented subgraph of $D$ if
$G^{\prime}$ is an induced subgraph of $G$.

###### Definition 2.24

A vertex $v$ is called simplicial if the induced subgraph $H=G[N_{G}[v]]$ is a
complete graph with $k=|V(H)|-1$, in this case, $H$ is called $k$-simplex (or
simplex). The set of simplexes of $G$ is denoted by $S_{G}$. $G$ is a
simplicial graph if every vertex of $G$ is a simplicial vertex of $G$ or is
adjacent to a simplicial vertex of $G$.

###### Definition 2.25

The minimum length of a cycle (contained) in a graph $G$, is called the girth
of $G$. On the other hand, $G$ is a chordal graph if the induced cycles are
$3$-cycles.

###### Theorem 2.26

[12, Theorems 1 and 2] If $G$ is a chordal or simplicial graph, then $G$ is
well-covered if and only if every vertex of $G$ belongs to exactly one simplex
of $G$.

###### Definition 2.27

An induced $5$-cycle $C$ of $G$ is called basic if $C$ does not contain two
adjacent vertices of degree three or more in $G$. $G$ is an $SCQ$ graph (or
$G\in SCQ$) if $G$ satisfies the following conditions:

  1. $(i)$

There is $Q_{G}$ such that $Q_{G}=\emptyset$ or $Q_{G}$ is a matching of $G$
with the property (P).

  2. $(ii)$

$\\{V(H)\mid H\in S_{G}\cup C_{G}\cup Q_{G}\\}$ is a partition of $V(G)$,
where $C_{G}$ is the set of basic $5$-cycles.

In the following three results, we use the graphs of Figure 1.

$\mathbf{C_{7}}$$d_{\tiny 1}$$d_{\tiny 2}$$b_{\tiny 2}$$a_{\tiny 2}$$a_{\tiny
1}$$b_{\tiny 1}$$c_{\tiny 1}$$c_{\tiny 2}$$g_{\tiny 2}$$g_{\tiny
1}$$\mathbf{P_{10}}$$C_{1}$$C_{2}$$\mathbf{\tilde{e}_{\tiny
1}}$$\mathbf{\tilde{e}_{\tiny 2}}$$\mathbf{\tilde{e}_{\tiny 3}}$$b_{\tiny
4}$$b_{\tiny 3}$$b_{\tiny 2}$$b_{\tiny 1}$$a_{\tiny 4}$$a_{\tiny 3}$$a_{\tiny
2}$$a_{\tiny 1}$$d_{\tiny 2}$$d_{\tiny 1}$$c_{\tiny 1}$$c_{\tiny
2}$$v$$\mathbf{P_{13}}$$C_{1}$$C_{2}$$\mathbf{\tilde{e}_{\tiny
1}}$$\mathbf{\tilde{e}_{\tiny 2}}$$v$$a_{\tiny 1}$$a_{\tiny 3}$$a_{\tiny
2}$$b_{\tiny 1}$$c_{\tiny 1}$$b_{\tiny 3}$$c_{\tiny 3}$$b_{\tiny 2}$$c_{\tiny
2}$$\mathbf{T_{10}}$$\mathbf{\tilde{e}_{\tiny 1}}$$\mathbf{\tilde{e}_{\tiny
2}}$$\mathbf{\tilde{e}_{\tiny 3}}$$a_{\tiny 1}$$a_{\tiny 2}$$a_{\tiny
7}$$a_{\tiny 6}$$a_{\tiny 3}$$a_{\tiny 4}$$a_{\tiny 5}$$b_{\tiny 1}$$b_{\tiny
7}$$b_{\tiny 2}$$b_{\tiny 6}$$b_{\tiny 3}$$b_{\tiny 5}$$b_{\tiny
4}$$\mathbf{P_{14}}$$\mathbf{Q_{13}}$$a_{\tiny 1}$$a_{\tiny 2}$$d_{\tiny
1}$$d_{\tiny 2}$$h$$g_{\tiny 1}$$g_{\tiny 2}$$h^{\prime}$$b_{\tiny
1}$$b_{\tiny 2}$$v$$c_{\tiny 1}$$c_{\tiny 2}$$C_{1}$$\mathbf{\tilde{e}_{\tiny
1}}$$\mathbf{\tilde{e}_{\tiny 2}}$$\mathbf{\tilde{e}_{\tiny 3}}$ Figure 1:

###### Theorem 2.28

[6, Theorem 1.1] If $G$ is connected without $4$\- and $5$-cycles, then $G$ is
well-covered if and only if $G\in\\{C_{7},T_{10}\\}$ or $\\{V(H)\mid H\in
S_{G}\\}$ is a partition of $V(G)$.

###### Remark 2.29

Suppose $G$ is well-covered. If $G$ is simplicial, or $G$ is chordal or $G$ is
a graph without $4$\- and $5$-cycles and $G\notin\\{C_{7},T_{10}\\}$. Then, by
Theorems 2.26 and 2.28, $\\{V(H)\mid H\in S_{G}\\}$ is a partition of $V(G)$.
Therefore, $G$ is an $SCQ$ graph with $C_{G}=Q_{G}=\emptyset$.

###### Theorem 2.30

[5, Theorem 2 and Theorem 3] If $G$ is a connected graph without $3$\- and
$4$-cycles, then $G$ is well-covered if and only if
$G\in\\{K_{1},C_{7},P_{10},P_{13},P_{14},Q_{13}\\}$ or $\\{V(H)\mid H\in
S_{G}\cup C_{G}\\}$ is a partition of $V(G)$.

###### Definition 2.31

The complement of $G$, denoted by $\overline{G}$, is the graph with
$V(\overline{G})=V(G)$ such that for each pair of different vertices $x$ and
$y$ of $D$, we have that $\\{x,y\\}\in E(\overline{G})$ if and only if
$\\{x,y\\}\notin E(G)$.

###### Definition 2.32

A $k$-colouring of $G$ is a function $c:V(G)\rightarrow\\{1,2,\ldots,k\\}$
such that $c(u)\neq c(v)$ if $\\{u,v\\}\notin E(G)$. The smallest integer $k$
such that $G$ has a $k$-colouring is called the chromatic number of $G$ and it
is denoted by $\chi(G)$. On the other hand, the clique number, denoted by
$\omega(G)$ is the size of the largest complete subgraph of $G$. Finally, $G$
is perfect if $\chi(H)=\omega(H)$ for every induced subgraph $H$ of $G$.

###### Remark 2.33

Let $A$ be a subset of $V(G)$, then $A$ is a stable set of $G$ if and only if
$\overline{G}[A]$ is a complete subgraph of $\overline{G}$. Hence,
$\beta(G)=\omega(\overline{G})$.

###### Theorem 2.34

[4, Theorem 5.5.3] $G$ is perfect if and only if $\overline{G}$ is perfect.

##  3 Strong vertex cover and $\star$-semi-forest

Let $D=(G,\mathcal{O},w)$ be a weighted oriented graph. In this Section, we
introduce the unicycle oriented subgraphs (Definition 3.2), the root oriented
trees (Definition 3.3), and the $\star$-semi-forests of $D$ (Definition 3.4).
With this definitions, we characterize when a subset of $V(G)$ is contained in
a strong vertex cover (see Theorem 3.10). Using this result, we characterize
when $I(D)$ is unmixed if $G$ is a perfect graph (see Definition 2.32 and
Theorem 3.11).

###### Proposition 3.1

If $\mathcal{C}$ is a vertex cover of $D$ such that
$N_{D}^{+}(A)\subseteq\mathcal{C}$ and $A\subseteq V^{+}$, then there is a
strong vertex cover $\mathcal{C}^{\prime}$ of $D$, such that
$N_{D}^{+}(A)\subseteq\mathcal{C}^{\prime}\subseteq\mathcal{C}$.

Proof. First, we prove that there is a vertex cover $\mathcal{C}^{\prime}$
such that $L_{3}(\mathcal{C}^{\prime})\subseteq
N_{D}^{+}(A)\subseteq\mathcal{C}^{\prime}\subseteq\mathcal{C}$. We take
$L:=N_{D}^{+}(A)$. If $L_{3}(\mathcal{C})\subseteq L$, then we take
$\mathcal{C}^{\prime}=\mathcal{C}$. Now, we suppose there is $a_{1}\in
L_{3}(\mathcal{C})\setminus L$, then by Remark 2.9,
$N_{D}[a_{1}]\subseteq\mathcal{C}$. Thus,
$\mathcal{C}_{1}=\mathcal{C}\setminus\\{a_{1}\\}$ is a vertex cover and
$L\subseteq\mathcal{C}_{1}$, since $L\subseteq\mathcal{C}$ and $a_{1}\notin
L$. Now, we suppose that there are vertex covers
$\mathcal{C}_{0},\ldots,\mathcal{C}_{k}$, such that
$L\subseteq\mathcal{C}_{i}=\mathcal{C}_{i-1}\setminus\\{a_{i}\\}$ and
$a_{i}\in L_{3}(\mathcal{C}_{i-1})\setminus L$ for $i=1,\ldots,k$ where
$\mathcal{C}_{0}=\mathcal{C}$ and we give the following recursively process:
If $L_{3}(\mathcal{C}_{k})\subseteq L$, then we take
$\mathcal{C}^{\prime}=\mathcal{C}_{k}$. Now, if there is $a_{k+1}\in
L_{3}(\mathcal{C}_{k})\setminus L$, then by Remark 2.9,
$N_{D}[a_{k+1}]\subseteq\mathcal{C}_{k}$. Consequently,
$\mathcal{C}_{k+1}:=\mathcal{C}_{k}\setminus\\{a_{k+1}\\}$ is a vertex cover.
Also, $L\subseteq\mathcal{C}_{k+1}$, since $L\subseteq\mathcal{C}_{k}$ and
$a_{k+1}\not\in L$. This process is finite, since $|V(D)|$ is finite. Hence,
there is $m$ such that $L_{3}(\mathcal{C}_{m})\subseteq
L\subseteq\mathcal{C}_{m}\subseteq\mathcal{C}$. Therefore, we take
$\mathcal{C}^{\prime}=\mathcal{C}_{m}$.

Now, we prove that $\mathcal{C}^{\prime}$ is strong. We take $x\in
L_{3}(\mathcal{C}^{\prime})$, then $x\in L=N_{D}^{+}(A)$, since
$L_{3}(\mathcal{C}^{\prime})\subseteq L$. Thus, $(y,x)\in E(D)$ for some $y\in
A\subseteq V^{+}$. Hence, $y\in\mathcal{C}^{\prime}$, since $x\in
L_{3}(\mathcal{C}^{\prime})$. Also, $y\not\in L_{1}(\mathcal{C}^{\prime})$,
since $N_{D}^{+}(y)\subseteq N_{D}^{+}(A)\subseteq\mathcal{C}^{\prime}$.
Hence, $y\in\big{(}\mathcal{C}^{\prime}\setminus
L_{1}(\mathcal{C}^{\prime})\big{)}\cap V^{+}$. Therefore,
$\mathcal{C}^{\prime}$ is strong.  $\Box$

###### Definition 3.2

If $B$ is a weighted oriented subgraph of $D$ with exactly one cycle $C$, then
$B$ is called unicycle oriented graph when $B$ satisfies the following
conditions:

  1. $(i)$

$C$ is an oriented cycle in $B$ and there is an oriented path from $C$ to $y$
in $B$, for each $y\in V(B)\setminus V(C)$.

  2. $(ii)$

If $x\in V(B)$ with $w(x)=1$, then $deg_{B}(x)=1$.

###### Definition 3.3

A weighted oriented subgraph $T$ of $D$ without cycles, is a root oriented
tree (ROT) with parent $v\in V(T)$ when $T$ satisfies the following
properties:

  1. $(i)$

If $x\in V(T)\setminus\\{v\\}$, there is an oriented path $\mathcal{P}$ in $T$
from $v$ to $x$.

  2. $(ii)$

If $x\in V(T)$ with $w(x)=1$, then $deg_{T}(x)=1$ and $x\neq v$ or
$V(T)=\\{v\\}$ and $x=v$.

###### Definition 3.4

A weighted oriented subgraph $H$ of $D$ is a $\star$-semi-forest if there are
root oriented trees $T_{1},\ldots,T_{r}$ whose parents are
$v_{1},\ldots,v_{r}$ and unicycle oriented subgraphs $B_{1},\ldots,B_{s}$ such
that $H=\big{(}\cup_{i=1}^{r}\ T_{i}\big{)}\cup\big{(}\cup_{j=1}^{s}\
B_{j}\big{)}$ with the following conditions:

  1. $(i)$

$V(T_{1}),\ldots,V(T_{r}),V(B_{1}),\ldots,V(B_{s})$ is a partition of $V(H)$.

  2. $(ii)$

There is $W=\\{w_{1},\ldots,w_{r}\\}\subseteq V(D)\setminus V(H)$ such that
$w_{i}\in N_{D}(v_{i})$ for $i=1,\ldots,r$ (it is possible that $w_{i}=w_{j}$
for some $1\leqslant i<j\leqslant r$).

  3. $(iii)$

There is a partition $W_{1}$, $W_{2}$ of $W$ such that $W_{1}$ is a stable set
of $D$, $W_{2}\subseteq V^{+}$ and $(w_{i},v_{i})\in E(D)$ if $w_{i}\in
W_{2}$. Also, $N_{D}^{+}(W_{2}\cup\tilde{H})\cap W_{1}=\emptyset$, where

$\tilde{H}=\\{x\in V(H)\mid deg_{H}(x)\geqslant 2\\}\cup\\{v_{i}\mid
deg_{H}(v_{i})=1\\}.$

###### Remark 3.5

By Definition 3.2 and Definition 3.3, we have $\tilde{H}\subseteq V^{+}$.
Furthermore, if $v_{i}$ is a parent vertex of $T_{i}$, with
$deg_{H}(v_{i})\geqslant 1$, then $v_{i}\in\tilde{H}$.

###### Lemma 3.6

If $H$ is a $\star$-semi-forest of $D$, then

$V(H)\subseteq N_{D}(W_{1})\cup N_{D}^{+}(W_{2}\cup\tilde{H})$.

Proof. We take $x\in V(H)$. Since $H=\big{(}\cup_{i=1}^{r}\
T_{i}\big{)}\cup\big{(}\cup_{j=1}^{s}\ B_{j}\big{)}$, we have two cases:

Case 1) $x\in V(B_{j})$ for some $1\leqslant j\leqslant s$. Let $C$ be the
oriented cycle of $B_{j}$. If $x\in V(C)$, then there is $y_{1}\in V(C)$ such
that $(y_{1},x)\in E(C)$. Furthermore, $deg_{H}(y_{1})\geqslant
deg_{C}(y_{1})=2$, then $y_{1}\in\tilde{H}$. Hence, $x\in
N_{D}^{+}(y_{1})\subseteq N_{D}^{+}(\tilde{H})$. Now, if $x\in
V(B_{j})\setminus V(C)$, then there is an oriented path $\mathcal{P}$ in
$B_{j}$ from $C$ to $x$. Thus, there is $y_{2}\in V(\mathcal{P})$ such that
$(y_{2},x)\in E(\mathcal{P})$. If $|V(\mathcal{P})|>2$, then
$deg_{H}(y_{2})\geqslant deg_{\mathcal{P}}(y_{2})=2$. If $|V(\mathcal{P})|=2$,
then $y_{2}\in V(C)$ and $deg_{H}(y_{2})>deg_{C}(y_{2})=2$. Therefore,
$y_{2}\in\tilde{H}$ and $x\in N_{D}^{+}(\tilde{H})$.

Case 2) $x\in V(T_{i})$ for some $1\leqslant i\leqslant r$. First, assume
$x=v_{i}$, then there is $w_{i}\in W$ such that $x\in N_{D}(w_{i})$.
Consequently, $x\in N_{D}(W_{1})$ if $w_{i}\in W_{1}$ and, by $(iii)$ of
Definition 3.4, $x\in N_{D}^{+}(w_{i})\subseteq N_{D}^{+}(W_{2})$ if $w_{i}\in
W_{2}$. Now, we suppose $x\neq v_{i}$, then there is an oriented path
$\mathcal{L}$, from $v_{i}$ to $x$. Consequently, there is $y_{3}\in
V(\mathcal{L})$ such that $(y_{3},x)\in E(D)$. If $y_{3}\neq v_{i}$, then
$deg_{H}(y_{3})\geqslant deg_{\mathcal{L}}(y_{3})=2$. Thus,
$y_{3}\in\tilde{H}$ and $x\in N_{D}^{+}(\tilde{H})$. Finally, if
$y_{3}=v_{i}$, then $deg_{H}(y_{3})\geqslant 1$. Hence, by Remark 3.5,
$y_{3}\in\tilde{H}$ and $x\in N_{D}^{+}(\tilde{H})$.  $\Box$

###### Remark 3.7

Sometimes to stress the relation between $W$ and $H$ in Definition 3.4, $W$ is
denoted by $W^{H}$. Similarly, $W_{1}^{H}$ and $W_{2}^{H}$. If
$\\{T_{1},\ldots,T_{r}\\}=\emptyset$, then
$W^{H}=W_{1}^{H}=W_{2}^{H}=\emptyset$.

###### Lemma 3.8

Let $K$ be a weighted oriented subgraph of $D$. If $H$ is a maximal ROT in $K$
with parent $v$, or $H$ is a maximal unicycle oriented subgraph in $K$ whose
cycle is $C$, then there is no $(y,x)\in E(K)$ with $x\in V(K)\setminus V(H)$
and $y\in V^{+}\cap V(H)$.

Proof. By contradiction suppose there is $(y,x)\in E(K)$ with $x\in
V(K)\setminus V(H)$ and $y\in V^{+}\cap V(H)$. Thus, $H\subsetneq
H_{1}:=H\cup\\{(y,x)\\}\subseteq K$. If $H$ is a unicycle oriented subgraph
with cycle $C$ (resp. $H$ is a ROT), then there is an oriented path
$\mathcal{P}$ from $C$ (resp. from $v$) to $y$. Consequently,
$\mathcal{P}\cup\\{(y,x)\\}$ is an oriented path from $C$ (resp. from $v$) to
$x$ in $H_{1}$. Furthermore, $H_{1}$ has exactly one cycle (resp. has no
cycles), since $deg_{H_{1}}(x)=1$ and $V(H_{1})\setminus V(H)=\\{x\\}$.

Now, we take $z\in V(H_{1})$ with $w(z)=1$, then $z=x$ or $z\in V(H)$. We
prove $deg_{H_{1}}(z)=1$. If $z=x$, then $deg_{H_{1}}(x)=1$. Now, if $z\in
V(H)$, then $z\neq y$, since $y\in V^{+}$. So, $deg_{H_{1}}(z)=deg_{H}(z)$,
since $N_{H_{1}}(x)=\\{y\\}$. If $H$ is a ROT with $V(H)=\\{v\\}$, then
$y=z=v$. A contradiction, since $w(z)=1$ and $y\in V^{+}$. Consequently, by
$(ii)$ in Definitions 3.2 and 3.3, $deg_{H_{1}}(z)=deg_{H}(z)=1$. Hence,
$H_{1}$ is a unicycle oriented subgraph with cycle $C$ (resp. is a ROT with
parent $v$) of $K$. This is a contradiction, since $H\subsetneq H_{1}\subseteq
K$ and $H$ is maximal.  $\Box$

###### Definition 3.9

Let $K$ be a weighted oriented subgraph of $D$ and $H$ a $\star$-semi-forest
of $D$. We say $H$ is a generating $\star$-semi-forest of $K$ if $V(K)=V(H)$.

###### Theorem 3.10

Let $K$ be an induced weighted oriented subgraph of $D$. Hence, the following
conditions are equivalent:

  1. (1)

There is a strong vertex cover $\mathcal{C}$ of $D$, such that
$V(K)\subseteq\mathcal{C}$.

  2. (2)

There is a generating $\star$-semi-forest $H$ of $K$.

Proof. ${\rm(2)}\Rightarrow{\rm(1)}$ Let $\mathcal{C}_{1}$ be a minimal vertex
cover of $D$. By (2), $K$ has a generating $\star$-semi-forest $H$. Now, using
the notation of Definition 3.4, we take
$\mathcal{C}_{2}=\big{(}\mathcal{C}_{1}\setminus W_{1}\big{)}\cup
N_{D}(W_{1})\cup N_{D}^{+}(W_{2}\cup\tilde{H})$. By Remark 2.6,
$\mathcal{C}_{2}$ is a vertex cover of $D$. Since $W_{1}$ is a stable set,
$N_{D}(W_{1})\cap W_{1}=\emptyset$. Then, $\mathcal{C}_{2}\cap
W_{1}=\emptyset$, since $N_{D}^{+}(W_{2}\cup\tilde{H})\cap W_{1}=\emptyset$.
By Remark 3.5 and $(iii)$ in Definition 3.4, $\tilde{H}\cup W_{2}\subseteq
V^{+}$. So, by Proposition 3.1, there is a strong vertex cover $\mathcal{C}$
of $D$ such that
$N_{D}^{+}(W_{2}\cup\tilde{H})\subseteq\mathcal{C}\subseteq\mathcal{C}_{2}$.
Consequently, $\mathcal{C}\cap W_{1}=\emptyset$, since $\mathcal{C}_{2}\cap
W_{1}=\emptyset$. Thus, $N_{D}(W_{1})\subseteq\mathcal{C}$, since
$\mathcal{C}$ is a vertex cover. Then, by Lemma 3.6, $V(H)\subseteq
N_{D}(W_{1})\cup N_{D}^{+}(W_{2}\cup\tilde{H})\subseteq\mathcal{C}$. Hence,
$V(K)\subseteq\mathcal{C}$, since $H$ is a generating $\star$-semi-forest of
$K$.

${\rm(1)}\Rightarrow{\rm(2)}$ We have, $\mathcal{C}$ is a strong vertex cover
such that $V(K)\subseteq\mathcal{C}$. If $A:=L_{1}(\mathcal{C})\cap
V(K)=\\{v_{1},\ldots,v_{s}\\}$, then there is $w_{i}\in
V(D)\setminus\mathcal{C}\subseteq V(D)\setminus V(K)$ such that
$(v_{i},w_{i})\in E(D)$. We take the ROT’s
$M_{1}=\\{v_{1}\\},\ldots,M_{s}=\\{v_{s}\\}$ and sets $W_{1}^{i}=\\{w_{i}\\}$
and $W_{2}^{i}=\emptyset$ for $i=1,\ldots,s$.

Now, we will give a recursive process to obtain a generating $\star$-semi-
forest of $K$. For this purpose, suppose we have connected $\star$-semi-
forests $M_{s+1},\ldots,M_{l}$ of $K\setminus A$ with subsets
$W_{1}^{s+1},\ldots,W_{1}^{l},W_{2}^{s+1},\ldots,W_{2}^{l}\subseteq
V(D)\setminus V(K)$ and $V^{s+1},\ldots,V^{l}\subseteq V(K)$ such that for
each $s<j\leqslant l$, they satisfies the following conditions:

  * (a)

$V^{j}=\\{v_{j}\\}$ if $M_{j}$ is a ROT with parent $v_{j}$ or $V^{j}$ is the
cycle of $M_{j}$ if $M_{j}$ is a unicycle oriented subgraph,

  * (b)

$M_{j}$ is a maximal ROT in $K^{j}:=K\setminus\cup_{i=1}^{j-1}V(M_{i})$ with
parent in $V^{j}$ or $M_{j}$ is a maximal unicycle oriented subgraph in
$K^{j}$ with cycle $V^{j}$.

  * (c)

$W_{1}^{j}\cap\mathcal{C}=\emptyset$ and
$W_{2}^{j}\subseteq\big{(}\mathcal{C}\setminus(L_{1}(\mathcal{C})\cup
V(K))\big{)}\cap V^{+}$.

Hence, we take $K^{l+1}:=K\setminus\big{(}\cup_{i=1}^{l}V(M_{i})\big{)}$. This
process starts with $l=s$; in this case,
$K^{s+1}:=K\setminus\big{(}\cup_{i=1}^{s}V(M_{i})\big{)}=K\setminus A$;
furthermore, if $A=\emptyset$, then $K^{1}=K$. Continuing with the recursive
process, if $K^{l+1}=\emptyset$, then $V(K)=\cup_{i=1}^{l}V(M_{i})$ and we
stop the process. Now, if $K^{l+1}\neq\emptyset$, then we will construct a
connected $\star$-semi-forest $M_{l+1}$ of $K^{l+1}$ in the following way:

Case (1) $L_{2}(\mathcal{C})\cap V(K^{l+1})\neq\emptyset$. Then, there is
$z\in L_{2}(\mathcal{C})\cap V(K^{l+1})$. Thus, there is $(z^{\prime},z)\in
E(D)$ with $z^{\prime}\notin\mathcal{C}$. We take a maximal ROT $M_{l+1}$ in
$K^{l+1}$, whose parent is $z$. Also, we take $V^{l+1}=\\{v_{l+1}\\}=\\{z\\}$,
$W_{1}^{l+1}=\\{w_{l+1}\\}=\\{z^{\prime}\\}$ and $W_{2}^{l+1}=\emptyset$.
Hence, $M_{l+1}$ satisfies (a), (b) and (c), since
$z^{\prime}\notin\mathcal{C}$ and $W_{2}^{l+1}=\emptyset$.

Case (2) $L_{2}(\mathcal{C})\cap V(K^{l+1})=\emptyset$. Then,
$V(K^{l+1})\subseteq L_{3}(\mathcal{C})$, since $K^{l+1}\subseteq K\setminus
A\subseteq\mathcal{C}\setminus L_{1}(\mathcal{C})$. We take $x\in V(K^{l+1})$,
then there is $x_{1}\in\big{(}\mathcal{C}\setminus
L_{1}(\mathcal{C})\big{)}\cap V^{+}$ such that $(x_{1},x)\in E(D)$, since
$\mathcal{C}$ is strong. If $x_{1}\in V(K^{l+1})$, then there is
$x_{2}\in\big{(}\mathcal{C}\setminus L_{1}(\mathcal{C})\big{)}\cap V^{+}$ such
that $(x_{2},x_{1})\in E(D)$, since $\mathcal{C}$ is strong. Continuing with
this process we obtain a maximal path
$\mathcal{P}=(x_{r},x_{r-1},\ldots,x_{1},x)$ such that
$x_{r-1},\ldots,x_{1},x$ are different in $V(K^{l+1})$ and
$x_{1},\ldots,x_{r}\in\big{(}\mathcal{C}\setminus
L_{1}(\mathcal{C})\big{)}\cap V^{+}$. Thus,
$x_{r}\notin\cup_{j=1}^{s}V(M_{j})$, since $x_{r}\notin L_{1}(\mathcal{C})$.
Now, suppose $x_{r}\in V(M_{j})$ for some $s<j\leqslant l$. So,
$(x_{r},x_{r-1})\in E(K^{j})$, $x_{r-1}\in V(K^{j})\setminus V(M_{j})$ and
$x_{r}\in V^{+}\cap V(M_{j})$. Furthermore, $N_{D}^{+}(x_{r})\cap
W_{1}^{j}=\emptyset$, since $x_{r}\in\mathcal{C}\setminus L_{1}(\mathcal{C})$
and $\mathcal{C}\cap W_{1}^{j}=\emptyset$. A contradiction, by Lemma 3.8,
since $W^{j}\cap V(K^{j})=\emptyset$. Hence,
$x_{r}\notin\cup_{j=1}^{l}V(M_{j})$. Consequently, $x_{r}\notin V(K)$ or
$x_{r}\in V(K^{l+1})$.

Case (2.a) $x_{r}\notin V(K)$. Then, take a maximal ROT $M_{l+1}$ in $K^{l+1}$
whose parent is $x_{r-1}$. Also, we take
$V^{l+1}=\\{v_{l+1}\\}=\\{x_{r-1}\\}$, $W_{1}^{l+1}=\emptyset$; and
$W_{2}^{l+1}=\\{w_{l+1}\\}=\\{x_{r}\\}$. Thus, $M_{l+1}$ satisfies (a), (b)
and (c), since $W_{1}^{l+1}=\emptyset$, $x_{r}\in\big{(}\mathcal{C}\setminus
L_{1}(\mathcal{C})\big{)}\cap V^{+}$ and $x_{r}\notin V(K)$.

Case (2.b) $x_{r}\in V(K^{l+1})$. Then, $x_{r}\in L_{3}(\mathcal{C})$, since
$V(K^{l+1})\subseteq L_{3}(\mathcal{C})$. Hence, there is
$x_{r+1}\in\big{(}\mathcal{C}\setminus L_{1}(\mathcal{C})\big{)}\cap V^{+}$
such that $(x_{r+1},x_{r})\in E(D)$, Then
$\tilde{\mathcal{P}}=(x_{r+1},x_{r},\ldots,x_{1},x)$ is an oriented walk. By
the maximality of $\mathcal{P}$, we have that
$x_{r}\in\\{x_{r-1},\ldots,x_{1},x\\}$. Thus,
$\mathcal{P}=(x_{r},\ldots,x_{1},x)$ contains an oriented cycle $C$. We take a
maximal unicycle oriented subgraph $M_{l+1}$ of $K^{l+1}$ with cycle $C$,
$V^{l+1}=C$ and $W_{1}^{l+1}=W_{2}^{l+1}=\emptyset$. Then, $M_{l+1}$ satisfies
(a), (b) and (c).

Since $K$ is finite, with this proceeding we obtain
$M_{1},\ldots,M_{t}\subseteq K$ such that $V(K)=\cup_{i=1}^{t}\ V(M_{i})$,
$W_{1}^{i}\cap\mathcal{C}=\emptyset$ and
$W_{2}^{i}\subseteq\big{(}\mathcal{C}\setminus L_{1}(\mathcal{C})\big{)}\cap
V^{+}$ for $i=1,\ldots t$. We take $H:=\cup_{i=1}^{t}\ M_{i}$ with
$W_{j}=\cup_{i=1}^{t}\ W_{j}^{i}$ for $j=1,2$. So, $V(H)=V(K)$. Also,
$W_{1}\cap\mathcal{C}=\emptyset$, then $W_{1}$ is a stable set, since
$\mathcal{C}$ is a vertex cover. Furthermore, $W_{2}\subseteq V^{+}$ and
$W_{2}\subseteq\mathcal{C}\setminus L_{1}(\mathcal{C})$, then
$N_{D}^{+}(W_{2})\subseteq\mathcal{C}$. Then, $N_{D}^{+}(W_{2})\cap
W_{1}=\emptyset$, since $\mathcal{C}\cap W_{1}=\emptyset$. If $x\in
L_{1}(\mathcal{C})\cap V(K)$, then there is $1\leqslant i\leqslant s$ such
that $x=v_{i}$ and $M_{i}=\\{v_{i}\\}$. Consequently,
$deg_{H}(x)=deg_{M_{i}}(v_{i})=0$. Thus, $\tilde{H}\cap
L_{1}(\mathcal{C})=\emptyset$ implying
$N_{D}^{+}(\tilde{H})\subseteq\mathcal{C}$, since $V(H)\subseteq\mathcal{C}$.
Hence, $N_{D}^{+}(\tilde{H})\cap W_{1}=\emptyset$, since
$W_{1}\cap\mathcal{C}=\emptyset$. Therefore, $H$ is a generating $\star$-semi-
forest of $K$.  $\Box$

###### Theorem 3.11

Let $D=(G,\mathcal{O},w)$ be a weighted oriented graph where $G$ is a perfect
graph, then $G$ has a $\tau$-reduction $H_{1},\ldots,H_{s}$ in complete
subgraphs. Furthermore, $I(D)$ is unmixed if and only if each $H_{i}$ has no
generating $\star$-semi-forests.

Proof. First, we prove $G$ has a $\tau$-reduction in complete graphs. By
Theorem 2.34, $\overline{G}$ is perfect. Thus,
$s:=w(\overline{G})=\chi(\overline{G})$. So, there is a $s$-colouring
$c:V(\overline{G})\rightarrow\\{1,\ldots,s\\}$. We take $V_{i}:=c^{-1}(i)$ for
$i=1,\ldots,s$. Then, $V_{i}$ is a stable set in $\overline{G}$, since $c$ is
a $s$-colouring. Hence, by Remark 2.33, $H_{i}:=G[V_{i}]$ is a complete graph
in $G$ and $s=\omega(\overline{G})=\beta(G)$. Furthermore,
$V_{1},\ldots,V_{s}$ is a partition of $V(\overline{G})=V(G)$, since $c$ is a
function. Consequently,

$\sum\limits_{i=1}^{s}\tau(H_{i})=\sum\limits_{i=1}^{s}\big{(}|V_{i}|-1\big{)}=\Big{(}\sum\limits_{i=1}^{s}|V_{i}|\Big{)}-s=|V(G)|-\beta(G)=\tau(G)$.

Finally, by Remark 2.16, $|V(G)|-\beta(G)=\tau(G)$, then, $H_{1},\ldots,H_{s}$
is a $\tau$-reduction of $G$.

Now, we prove that $I(D)$ is unmixed if and only if each $H_{i}$ has no
generating $\star$-semi-forests.

$\Rightarrow)$ By contradiction, assume $H_{j}$ has a generating $\star$-semi-
forest, then by Theorem 3.10 there is a strong vertex $\mathcal{C}$ such that
$V_{j}\subseteq\mathcal{C}$. Furthermore, $\mathcal{C}\cap V_{i}$ is a vertex
cover of $H_{i}$, then $|\mathcal{C}\cap V_{i}|\geqslant\tau(H_{i})=|V_{i}|-1$
for $i\neq j$. Thus, $|\mathcal{C}|=\sum_{i=1}^{s}|\mathcal{C}\cap
V_{i}|\geqslant|V_{j}|+\sum_{\begin{subarray}{c}i=1\\\ i\neq
j\end{subarray}}^{s}(|V_{i}|-1)$, since $V_{1},\ldots,V_{s}$ is a partition of
$V(G)$. Hence, by Remark 2.16, $|\mathcal{C}|>|V(G)|-s=\tau(G)$, since
$s=\beta(G)$. A contradiction, by Remark 2.14, since $I(D)$ is unmixed.

$\Leftarrow)$ Let $\mathcal{C}$ be a strong vertex cover, then
$\mathcal{C}\cap V_{i}$ is a vertex cover of $H_{i}$. So, $|\mathcal{C}\cap
V_{i}|\geqslant\tau(H_{i})=|V_{i}|-1$ for $i=1,\ldots,s$. Furthermore, by
Theorem 3.10, $V_{i}\not\subseteq\mathcal{C}$. Consequently, $|\mathcal{C}\cap
V_{i}|=|V_{i}|-1$. Thus,
$|\mathcal{C}|=\sum_{i=1}^{s}\big{(}|V_{i}|-1\big{)}$, since
$V_{1},\ldots,V_{s}$ is a partition of $V(G)$. Therefore, by (2) in Theorem
2.12, $I(D)$ is unmixed.  $\Box$

##  4 Unmixedness of weighted oriented $SCQ$ graphs

Let $D=(G,\mathcal{O},w)$ be a weighted oriented graph. If $P$ is a perfect
matching of $G$ with the property (P), then in Proposition 4.1, we
characterize when $|\mathcal{C}\cap e|=1$, for each strong vertex cover
$\mathcal{C}$ of $D$ and each $e\in P$. Using Proposition 4.1 in Corollary
4.2, we characterize when $I(D)$ is unmixed if $G$ is Köning. In Proposition
4.6, we characterize the basic $5$-cycles, $C$ such that $|\mathcal{C}\cap
V(C)|=3$ for each strong vertex cover $\mathcal{C}$ of $D$. Furthermore, in
Theorem 4.8, we characterize when $I(D)$ is unmixed if $G$ is an $SCQ$ graph
(see Definition 2.27). Finally, using this result we characterize the unmixed
property of $I(D)$, when $G$ is simplicial or $G$ is chordal (see Corollary
4.9).

###### Proposition 4.1

Let $e$ be an edge of $G$. Hence, the following conditions are equivalent:

  1. (1)

$|\mathcal{C}\cap e|=1$ for each strong vertex cover $\mathcal{C}$ of $D$.

  2. (2)

$e$ has the property (P) and $N_{D}(b)\subseteq N_{D}^{+}(a)$ if
$(a,b^{\prime})\in E(D)$ with $a\in V^{+}$ and $e=\\{b,b^{\prime}\\}$.

Proof. ${\rm(1)}\Rightarrow{\rm(2)}$ First, we show $e$ has the property (P).
By contradiction, suppose there are $\\{a,b\\},\\{a^{\prime},b^{\prime}\\}\in
E(G)$ such that $\\{a,a^{\prime}\\}\notin E(G)$. This implies, there is a
maximal stable set $S$ such that $\\{a,a^{\prime}\\}\subseteq S$. So,
$\tilde{\mathcal{C}}=V(G)\setminus S$ is a minimal vertex cover. Consequently,
$\tilde{\mathcal{C}}$ is strong. Furthermore,
$a,a^{\prime}\notin\tilde{\mathcal{C}}$, then
$b,b^{\prime}\in\tilde{\mathcal{C}}$, since
$\\{a,b\\},\\{a^{\prime},b^{\prime}\\}\in E(G)$. A contradiction by (1). Now,
assume $(a,b^{\prime})\in E(D)$ with $a\in V^{+}$ and $e=\\{b,b^{\prime}\\}$,
then we will prove that $N_{D}(b)\subseteq N_{D}^{+}(a)$. By contradiction,
suppose there is $c\in N_{D}(b)\setminus N_{D}^{+}(a)$. We take a maximal
stable set $S$ such that $b\in S$. Thus, $\mathcal{C}_{1}=V(G)\setminus S$ is
a minimal vertex cover such that $b\notin\mathcal{C}_{1}$. By Remark 2.6,
$\mathcal{C}=\big{(}\mathcal{C}_{1}\setminus\\{c\\}\big{)}\cup N_{D}(c)\cup
N_{D}^{+}(a)$ is a vertex cover. Furthermore, $c\notin\mathcal{C}$, since
$c\notin N_{D}^{+}(a)$. By Proposition 3.1, there is a strong vertex cover
$\mathcal{C}^{\prime}$ such that
$N_{D}^{+}(a)\subseteq\mathcal{C}^{\prime}\subseteq\mathcal{C}$, since $a\in
V^{+}$. Also, $b^{\prime}\in N_{D}^{+}(a)\subseteq\mathcal{C}^{\prime}$ and
$c\notin\mathcal{C}^{\prime}$, since $(a,b^{\prime})\in E(D)$ and
$c\notin\mathcal{C}$. Then, $b\in N_{D}(c)\subseteq\mathcal{C}^{\prime}$.
Hence, $\\{b,b^{\prime}\\}\subseteq\mathcal{C}^{\prime}$. This is a
contradiction, by (1).

${\rm(2)}\Rightarrow{\rm(1)}$ By contradiction, assume there is a strong
vertex cover $\mathcal{C}$ of $D$ such that $|\mathcal{C}\cap e|\neq 1$. So,
$|\mathcal{C}\cap e|=2$, since $\mathcal{C}$ is a vertex cover. Hence, by
Theorem 3.10, there is a generating $\star$-semi-forest $H$ of $e$. We set
$e=\\{z,z^{\prime}\\}$. First, assume $H$ is not connected. Then, using the
Definition 3.4, we have $H=M_{1}\cup M_{2}$ where $M_{1}=\\{v_{1}\\}$,
$M_{2}=\\{v_{2}\\}$ and $w_{1},w_{2}\in W$ such that $w_{i}\in N_{D}(v_{i})$
for $i=1,2$. Thus, $\\{z,z^{\prime}\\}=\\{v_{1},v_{2}\\}$ and
$\\{w_{1},w_{2}\\}\in E(G)$, since $e$ satisfies the property (P). This
implies $|W_{1}\cap\\{w_{1},w_{2}\\}|\leqslant 1$, since $W_{1}$ is a stable
set. Hence, we can suppose $w_{2}\in W_{2}$, then $w_{2}\in V^{+}$ and
$(w_{2},z^{\prime})\in E(D)$. Consequently, by (2), $w_{1}\in
N_{D}(z)\subseteq N_{D}^{+}(w_{2})$, then $(w_{2},w_{1})\in E(D)$.
Furthermore, by $(iii)$ in Definition 3.4, $N_{D}^{+}(W_{2})\cap
W_{1}=\emptyset$, then $w_{1}\in W_{2}$. So, $w_{1}\in V^{+}$ and
$(w_{1},z)\in E(D)$. By (1) with $a=w_{1}$, we have $(w_{1},w_{2})\in E(D)$. A
contradiction, then $H$ is connected. Thus, $H$ is a ROT with
$V(H)=\\{z,z^{\prime}\\}$. We can suppose $v_{1}=z$ and $W^{H}=\\{w_{1}\\}$,
then $(z,z^{\prime})\in E(D)$, $w_{1}\in N_{D}(z)$ and $z=v_{1}\in\tilde{H}$,
since $deg_{H}(v_{1})=1$. If $w_{1}\in N_{D}^{+}(z)$, then $w_{1}\in W_{1}$,
since $z=v_{1}$. A contradiction, since $N_{D}^{+}(\tilde{H})\cap
W_{1}=\emptyset$. Then, $w_{1}\notin N_{D}^{+}(z)$. By Remark 3.5,
$z=v_{1}\in\tilde{H}\subseteq V^{+}$. Therefore, by (1) (taking $a=b=z$ and
$b^{\prime}=z^{\prime}$), we have $N_{D}(z)\subseteq N_{D}^{+}(z)$, since
$e=\\{z,z^{\prime}\\}$ and $z^{\prime}\in N_{D}^{+}(z)$. A contradiction,
since $w_{1}\in N_{D}(z)\setminus N_{D}^{+}(z)$.  $\Box$

###### Corollary 4.2

[11, Theorem 3.4] Let $D=(G,\mathcal{O},w)$ be a weighted oriented graph,
where $G$ is Köning without isolated vertices. Hence, $I(D)$ is unmixed if and
only if $D$ satisfies the following two conditions:

  1. (a)

G has a perfect matching $P$ with the property (P).

  2. (b)

$N_{D}(b)\subseteq N_{D}^{+}(a)$, when $a\in V^{+}$, $\\{b,b^{\prime}\\}\in P$
and $b^{\prime}\in N_{D}^{+}(a)$.

Proof. $\Rightarrow)$ By Theorem 2.12, $I(G)$ is unmixed. Thus, by Remark 2.17
and Theorem 2.20, $G$ has a perfect matching $P$ with the property (P).
Consequently, $\nu(G)=|P|$. Also, $\tau(G)=\nu(G)$, since $G$ is Köning. So,
$\tau(G)=|P|$. Now, we take a strong vertex cover $\mathcal{C}$ of $D$ and
$e\in P$. Then, $|\mathcal{C}\cap e|\geqslant 1$. Furthermore, by Remark 2.14,
$|\mathcal{C}|=\tau(G)=|P|$. Hence, $|\mathcal{C}\cap e|=1$, since
$\mathcal{C}=\cup_{\tilde{e}\in P}\ \mathcal{C}\cap\tilde{e}$. Therefore, by
Proposition 4.1, $D$ satisfies (b).

$\Leftarrow)$ We take a strong vertex cover $\mathcal{C}$ of $D$. By
Proposition 4.1, $|\mathcal{C}\cap e|=1$ for each $e\in P$, since $D$
satisfies (a) and (b). This implies $|\mathcal{C}|=|P|$, since $P$ is a
perfect matching. Therefore, by $(2)$ in Theorem 2.12, $I(D)$ is unmixed.
$\Box$

###### Lemma 4.3

If there is a basic $5$-cycle $C=(z_{1},z_{2},z_{3},z_{4},z_{5},z_{1})$ with
$(z_{1},z_{2})$, $(z_{2},z_{3})\in E(D)$, $z_{2}\in V^{+}$ and $C$ satisfies
one of the following conditions:

  1. (a)

$(z_{3},z_{4})\in E(D)$ with $z_{3}\in V^{+}$.

  2. (b)

$(z_{1},z_{5})$, $(z_{5},z_{4})\in E(D)$ with $z_{5}\in V^{+}$.

then there is a strong vertex cover $\tilde{\mathcal{C}}$ such that
$|\tilde{\mathcal{C}}\cap V(C)|=4$.

Proof. We take $\mathcal{C}=\big{(}\mathcal{C}_{0}\setminus V(C)\big{)}\cup
N_{D}(z_{1})\cup N_{D}^{+}(z_{2},x)$ where $\mathcal{C}_{0}$ is a vertex cover
and $x=z_{3}$ if $C$ satisfies (a) or $x=z_{5}$ if $C$ satisfies (b). Thus,
$x\in V^{+}$. Furthermore, $z_{2},z_{3},z_{5}\in N_{D}(z_{1})\cup
N_{D}^{+}(z_{2})$ and $z_{4}\in N_{D}^{+}(z_{3})$ if $C$ satisfies (a) or
$z_{4}\in N_{D}^{+}(z_{5})$ if $C$ satisfies (b). Hence,
$\\{z_{2},z_{3},z_{4},z_{5}\\}\subseteq N_{D}(z_{1})\cup N_{D}^{+}(z_{2},x)$.
Consequently, $\\{z_{2},z_{3},z_{4},z_{5}\\}\subseteq\mathcal{C}$, implying
$\mathcal{C}$ is a vertex cover, since $\mathcal{C}_{0}$ is vertex cover and
$N_{D}(z_{1})\subseteq\mathcal{C}$. Also, $z_{1}\notin\mathcal{C}$, since
$z_{1}\notin N_{D}(z_{1})\cup N_{D}^{+}(z_{2},z_{3})$ and $z_{1}\notin
N_{D}^{+}(z_{5})$ if $C$ satisfies (b). By Proposition 3.1, there is a strong
vertex cover $\mathcal{C}^{\prime}$ such that
$N_{D}^{+}(z_{2},x)\subseteq\mathcal{C}^{\prime}\subseteq\mathcal{C}$, since
$\\{z_{2},x\\}\subseteq V^{+}$. So, $z_{1}\notin\mathcal{C}^{\prime}$, since
$z_{1}\notin\mathcal{C}$. Then, by Remark 2.8,
$N_{D}(z_{1})\subseteq\mathcal{C}^{\prime}$. Hence,
$\\{z_{2},z_{3},z_{4},z_{5}\\}\subseteq N_{D}(z_{1})\cup
N_{D}^{+}(z_{2},x)\subseteq\mathcal{C}^{\prime}$. Therefore,
$|\mathcal{C}^{\prime}\cap V(C)|=4$, since $z_{1}\notin\mathcal{C}^{\prime}$.
$\Box$

###### Definition 4.4

Let $C$ be an induced $5$-cycle, we say that $C$ has the $\star$-property if
for each $(a,b)\in E(C)$ where $a\in V^{+}$, then
$C=(a^{\prime},a,b,b^{\prime},c,a^{\prime})$ with the following properties:

  1. $(\star.1)$

$(a^{\prime},a)\in E(D)$ and $w(a^{\prime})=1$.

  2. $(\star.2)$

$N_{D}^{-}(a)\subseteq N_{D}(c)$ and $N_{D}^{-}(a)\cap V^{+}\subseteq
N_{D}^{-}(c)$.

  3. $(\star.3)$

$N_{D}(b^{\prime})\subseteq N_{D}(a^{\prime})\cup N_{D}^{+}(a)$ and
$N_{D}^{-}(b^{\prime})\cap V^{+}\subseteq N_{D}^{-}(a^{\prime})$.

###### Lemma 4.5

Let $C=(a_{1}^{\prime},a_{1},b_{1},b_{1}^{\prime},c_{1},a_{1}^{\prime})$ be a
basic $5$-cycle of $D$, such that $(a_{1}^{\prime},a_{1})\in E(D)$,
$deg_{D}(a_{1})\geqslant 3$, $deg_{D}(c_{1})\geqslant 3$ and $w(b_{1})=1$. If
there is a strong vertex cover $\mathcal{C}$ of $D$, such that
$V(C)\subseteq\mathcal{C}$, then $C$ has no the $\star$-property.

Proof. By contradiction, suppose $C$ has the $\star$-property and there is a
strong vertex cover $\mathcal{C}$, such that $V(C)\subseteq\mathcal{C}$. Then,
$deg_{D}(a_{1}^{\prime})=deg_{D}(b_{1}^{\prime})=2$, since $C$ is a basic
cycle, $deg_{D}(a_{1})\geqslant 3$ and $deg_{D}(c_{1})\geqslant 3$. Hence,
$a_{1}^{\prime},b_{1}^{\prime}\in L_{3}(\mathcal{C})$, since
$V(C)\subseteq\mathcal{C}$. Thus, $(c_{1},a_{1}^{\prime})\in E(D)$ and
$w(c_{1})\neq 1$, since $a_{1}^{\prime}\in L_{3}(\mathcal{C})$,
$deg_{D}(a_{1}^{\prime})=2$, $(a_{1}^{\prime},a_{1})\in E(D)$ and
$\mathcal{C}$ is strong. By ($\star.1$) with $(a,b)=(c_{1},a_{1}^{\prime})$,
we have that $(b_{1}^{\prime},c_{1})\in E(D)$. Hence,
$N_{D}^{-}(b_{1}^{\prime})\subseteq\\{b_{1}\\}$, since
$deg_{D}(b_{1}^{\prime})=2$. This is a contradiction, since $b_{1}^{\prime}\in
L_{3}(\mathcal{C})$ and $w(b_{1})=1$.  $\Box$

###### Proposition 4.6

Let $C$ be a basic $5$-cycle, then $C$ has the $\star$-property if and only if
$|\mathcal{C}\cap V(C)|=3$ for each strong vertex cover $\mathcal{C}$ of $D$.

Proof. $\Rightarrow)$ By contradiction, we suppose there is a strong vertex
cover $\mathcal{C}$ such that $|\mathcal{C}\cap V(C)|\geqslant 4$. Thus, there
is a path $L=(d_{1},d_{2},d_{3},d_{4})\subseteq C$ such that
$V(L)\subseteq\mathcal{C}$. Then, $deg_{D}(d_{2})=2$ or $deg_{D}(d_{3})=2$,
since $C$ is basic. We can suppose $deg_{D}(d_{2})=2$, then
$N_{D}(d_{2})\subseteq\mathcal{C}$. This implies $b_{1}:=d_{2}\in
L_{3}(\mathcal{C})$. So, there is $(a_{1},b_{1})\in E(D)$ with
$a_{1}\in\big{(}\mathcal{C}\setminus L_{1}(\mathcal{C})\big{)}\cap V^{+}$,
since $\mathcal{C}$ is strong. Since, $N_{D}(b_{1})\subseteq C$, we can set
$C=(a_{1}^{\prime},a_{1},b_{1},b_{1}^{\prime},c_{1},a_{1}^{\prime})$.
Consequently,
$\\{a_{1},b_{1}^{\prime}\\}=N_{D}(b_{1})=N_{D}(d_{2})=\\{d_{1},d_{3}\\}\subseteq\mathcal{C}$.
By ($\star.1$), $(a_{1}^{\prime},a_{1})\in E(D)$ and $w(a_{1}^{\prime})=1$. If
$b_{1}\in V^{+}$, then by Remark 2.3, $b_{1}$ is not a sink. This implies,
$(b_{1},b_{1}^{\prime})\in E(D)$. Then, by ($\star.1$) with
$(a,b)=(b_{1},b_{1}^{\prime})$, $w(a_{1})=1$. A contradiction, since $a_{1}\in
V^{+}$. Hence, $w(b_{1})=1$.

We prove $a_{1}^{\prime}\in\mathcal{C}$. By contradiction assume
$a_{1}^{\prime}\not\in\mathcal{C}$, then
$\\{b_{1},a_{1},c_{1},b_{1}^{\prime}\\}\subseteq\mathcal{C}$, since
$|\mathcal{C}\cap V(C)|\geqslant 4$. Suppose $b_{1}^{\prime}\in
L_{3}(\mathcal{C})$, then there is $y\in\big{(}N_{D}^{-}(b_{1}^{\prime})\cap
V^{+}\big{)}\setminus L_{1}(\mathcal{C})$. Then, by ($\star.3$) with
$(a,b)=(a_{1},b_{1})$, $y\in N_{D}^{-}(a_{1}^{\prime})$, i.e.
$(y,a_{1}^{\prime})\in E(D)$. Consequently, $y\in L_{1}(\mathcal{C})$, since
$a_{1}^{\prime}\notin\mathcal{C}$. This is a contradiction. Hence,
$b_{1}^{\prime}\notin L_{3}(\mathcal{C})$, i.e. there is $y^{\prime}\in
N_{D}(b_{1}^{\prime})\setminus\mathcal{C}$, since
$b_{1}^{\prime}\in\mathcal{C}$. By ($\star.3$), $y^{\prime}\in
N_{D}(a_{1}^{\prime})\cup N_{D}^{+}(a_{1})$. Furthermore,
$a_{1}^{\prime}\notin\mathcal{C}$, then
$N_{D}(a_{1}^{\prime})\subseteq\mathcal{C}$ and $y^{\prime}\notin
N_{D}(a_{1}^{\prime})$, since $\mathcal{C}$ is a vertex cover and
$y^{\prime}\notin\mathcal{C}$. This implies $y^{\prime}\in N_{D}^{+}(a_{1})$,
then $a_{1}\in L_{1}(\mathcal{C})$, since $a_{1}\in\mathcal{C}$ and
$y^{\prime}\notin\mathcal{C}$. A contradiction, since $a_{1}\notin
L_{1}(\mathcal{C})$. Therefore, $a_{1}^{\prime}\in\mathcal{C}$.

Thus, $\\{b_{1},a_{1},a_{1}^{\prime},b_{1}^{\prime}\\}\subseteq\mathcal{C}$.
Now, we prove $c_{1}\in\mathcal{C}$, $deg_{D}(a_{1})\geqslant 3$ and
$deg_{D}(c_{1})\geqslant 3$.

Case (1) $a_{1}\in L_{3}(\mathcal{C})$. Consequently, there is $z\in
N_{D}^{-}(a_{1})\cap V^{+}$ such that $z\in\mathcal{C}\setminus
L_{1}(\mathcal{C})$. Then, $z\notin V(C)$, since $N_{D}^{-}(a_{1})\cap
V(C)=\\{a_{1}^{\prime}\\}$ and $w(a_{1}^{\prime})=1$. By ($\star.2$), $z\in
N_{D}^{-}(c_{1})$. Thus, $(z,c_{1})\in E(D)$. Consequently,
$c_{1}\in\mathcal{C}$, $deg_{D}(a_{1})\geqslant 3$ and
$deg_{D}(c_{1})\geqslant 3$, since $z\in\mathcal{C}\setminus
L_{1}(\mathcal{C})$ and $z\in N_{D}(a_{1})\cap N_{D}(c_{1})$.

Case (2) $a_{1}\notin L_{3}(\mathcal{C})$. This implies, there is
$z^{\prime}\in N_{D}(a_{1})$ such that $z^{\prime}\notin\mathcal{C}$. Then,
$z^{\prime}\notin V(C)$, since $N_{D}(a_{1})\cap
V(C)=\\{a_{1}^{\prime},b_{1}\\}\subseteq\mathcal{C}$. Consequently,
$z^{\prime}\in N_{D}^{-}(a_{1})$, since $a_{1}\in\mathcal{C}\setminus
L_{1}(\mathcal{C})$. By ($\star.2$), we have $z^{\prime}\in
N_{D}^{-}(a_{1})\subseteq N_{D}(c_{1})$. Hence, $c_{1}\in\mathcal{C}$,
$deg_{D}(a_{1})\geqslant 3$ and $deg_{D}(c_{1})\geqslant 3$, since
$z^{\prime}\notin\mathcal{C}$ and $z^{\prime}\in N_{D}(a_{1})\cap
N_{D}(c_{1})$.

This implies, $V(C)\subseteq\mathcal{C}$. A contradiction, by Lemma 4.5, since
$C$ has the $\star$-property.

$\Leftarrow)$ Assume $C=(a^{\prime},a,b,b^{\prime},c,a^{\prime})$ with
$(a,b)\in E(C)$ such that $w(a)\neq 1$. We take a minimal vertex cover
$\mathcal{C}$ of $D$. We will prove ($\star.1$), ($\star.2$) and ($\star.3$).

$\mathbf{(\star.1)}$ First we will prove $(a^{\prime},a)\in E(D)$. By
contradiction, suppose $(a,a^{\prime})\in E(D)$. By Remark 2.3, there is $y\in
N_{D}^{-}(a)$, since $a\in V^{+}$. Thus, $y\notin V(C)$ and $deg_{D}(a)\geq
3$. Consequently, $deg_{D}(a^{\prime})=deg_{D}(b)=2$, since $C$ is basic.
Also, $deg_{D}(b^{\prime})=2$ or $deg_{D}(c)=2$, since $C$ is basic. We can
assume $deg_{D}(c)=2$, then $N_{D}(c)=\\{a^{\prime},b^{\prime}\\}$. So, by
Remark 2.6, $\mathcal{C}_{1}=\big{(}\mathcal{C}\setminus\\{y,c\\}\big{)}\cup
N_{D}(y,b)\cup N_{D}^{+}(a)$ is a vertex cover, since $\mathcal{C}$ is a
vertex cover, $\\{a^{\prime},b^{\prime}\\}\subseteq N_{D}(b)\cup
N_{D}^{+}(a)\subseteq\mathcal{C}_{1}$. Since $deg_{D}(c)=2$, we have $c\not\in
N_{D}(y)$. Furthermore, $c\notin N_{D}(b)\cup N_{D}^{+}(a)$, since $C$ is
induced. Then, $c\not\in\mathcal{C}_{1}$. Also, $N_{D}(b)=\\{b^{\prime},a\\}$,
implies $y\not\in\mathcal{C}_{1}$, since $y\not\in N_{D}^{+}(a)$. By
Proposition 3.1 there is a strong vertex cover $\mathcal{C}_{1}^{\prime}$ such
that $N_{D}^{+}(a)\subseteq\mathcal{C}_{1}^{\prime}\subseteq\mathcal{C}_{1}$,
since $a\in V^{+}$. Thus, $c,y\notin\mathcal{C}_{1}^{\prime}$, since
$c,y\notin\mathcal{C}_{1}$. By Remark 2.8, $a^{\prime},b^{\prime},a\in
N_{D}(c)\cup N_{D}(y)\subseteq\mathcal{C}_{1}^{\prime}$. Furthermore, $b\in
N_{D}^{+}(a)\subseteq\mathcal{C}_{1}^{\prime}$. Hence,
$|\mathcal{C}_{1}^{\prime}\cap V(C)|=4$. A contradiction.

Now, we prove $w(a^{\prime})=1$. By contradiction, assume $w(a^{\prime})\neq
1$. By the last argument, $(c,a^{\prime})\in E(D)$, since $(a^{\prime},a)\in
E(D)$ and $a\in V^{+}$. A contradiction, by (a) in Lemma 4.3.

$\mathbf{(\star.2)}$ We will prove $N_{D}^{-}(a)\subseteq N_{D}(c)$. By
contradiction, suppose there is $y\in N_{D}^{-}(a)\setminus N_{D}(c)$. Also,
$N_{D}^{-}(a)\cap V(C)\subseteq\\{a^{\prime}\\}\subseteq N_{D}(c)$, since
$b\in N_{D}^{+}(a)$. Hence, $y\notin V(C)$. By Remark 2.6,
$\mathcal{C}_{2}=\big{(}\mathcal{C}\setminus\\{y,c\\}\big{)}\cup
N_{D}(y,c)\cup N_{D}^{+}(a)$ is a vertex cover. Furthermore,
$y,c\notin\mathcal{C}_{2}$, since $y\in N_{D}^{-}(a)\setminus N_{D}(c)$ and
$c\notin N_{D}(a,y)$. By Proposition 3.1, there is a strong vertex cover
$\mathcal{C}_{2}^{\prime}$ such that
$N_{D}^{+}(a)\subseteq\mathcal{C}_{2}^{\prime}\subseteq\mathcal{C}_{2}$, since
$a\in V^{+}$. Thus, $y,c\notin\mathcal{C}_{2}^{\prime}$ since
$y,c\notin\mathcal{C}_{2}$. By Remark 2.8, $a,a^{\prime},b^{\prime}\in
N_{D}(y,c)\subseteq\mathcal{C}_{2}^{\prime}$. Hence,
$|\mathcal{C}_{2}^{\prime}\cap V(C)|=4$, since $b\in
N_{D}^{+}(a)\subseteq\mathcal{C}_{2}^{\prime}$. A contradiction.

Now, we prove $N_{D}^{-}(a)\cap V^{+}\subseteq N_{D}^{-}(c)$. By
contradiction, suppose there is $y\in N_{D}^{-}(a)\cap V^{+}\setminus
N_{D}^{-}(c)$. By Remark 2.6,
$\mathcal{C}_{3}=(\mathcal{C}\setminus\\{c\\})\cup N_{D}(c)\cup
N_{D}^{+}(a,y)$ is a vertex cover. Furthermore, $c\notin N_{D}^{+}(a,y)$, then
$c\notin\mathcal{C}_{3}$. By Proposition 3.1, there is a strong vertex cover
$\mathcal{C}_{3}^{\prime}$ such that
$N_{D}^{+}(a,y)\subseteq\mathcal{C}_{3}^{\prime}\subseteq\mathcal{C}_{3}$
since $\\{a,y\\}\subseteq V^{+}$. So, $c\notin\mathcal{C}_{3}^{\prime}$, since
$c\notin\mathcal{C}_{3}$. Thus, by Remark 2.8 $a^{\prime},b^{\prime}\in
N_{D}(c)\subseteq\mathcal{C}_{3}^{\prime}$. Also, $a,b\in
N_{D}^{+}(a,y)\subseteq\mathcal{C}_{3}^{\prime}$. Hence,
$|\mathcal{C}^{\prime}_{3}\cap V(C)|=4$, a contradiction.

$\mathbf{(\star.3)}$ We prove $N_{D}(b^{\prime})\subseteq
N_{D}(a^{\prime})\cup N_{D}^{+}(a)$. By contradiction, we suppose there is
$y\in N_{D}(b^{\prime})\setminus\big{(}N_{D}(a^{\prime})\cup
N_{D}^{+}(a)\big{)}$. Thus, $y\notin C$, since $N_{D}(b^{\prime})\cap
V(C)=\\{c,b\\}\subseteq N_{D}(a^{\prime})\cup N_{D}^{+}(a)$. By Remark 2.6,
$\mathcal{C}_{4}=\big{(}\mathcal{C}\setminus\\{y,a^{\prime}\\})\big{)}\cup
N_{D}(y,a^{\prime})\cup N_{D}^{+}(a)$. Furthermore, $y\notin\mathcal{C}_{4}$,
since $y\notin N_{D}(a^{\prime})\cup N_{D}^{+}(a)$. By ($\star.1$),
$(a^{\prime},a)\in E(D)$, then $a^{\prime}\notin\mathcal{C}_{4}$, since
$a^{\prime}\notin N_{D}(y)\cup N_{D}^{+}(a)$. By Proposition 3.1, there is a
strong vertex cover $\mathcal{C}_{4}^{\prime}$ such that
$N_{D}^{+}(a)\subseteq\mathcal{C}_{4}^{\prime}\subseteq\mathcal{C}_{4}$, since
$a\in V^{+}$. So, $y,a^{\prime}\notin\mathcal{C}_{4}^{\prime}$, since
$y,a^{\prime}\notin\mathcal{C}_{4}$. Thus, by Remark 2.8 $b^{\prime},a,c\in
N_{D}(y)\cup N_{D}(a^{\prime})\subseteq\mathcal{C}_{4}^{\prime}$. Also, $b\in
N_{D}^{+}(a)\subseteq\mathcal{C}_{4}^{\prime}$. Hence,
$|\mathcal{C}_{4}^{\prime}\cap V(C)|=4$, a contradiction.

Finally, we prove $N_{D}^{-}(b^{\prime})\cap V^{+}\subseteq
N_{D}^{-}(a^{\prime})$. By contradiction, we suppose there is
$y\in\big{(}N_{D}^{-}(b^{\prime})\cap V^{+}\big{)}\setminus
N_{D}^{-}(a^{\prime})$. By $(\star.1)$, $a^{\prime}\in N_{D}^{-}(a)$.
Furthermore, by (a) in Lemma 4.3, $y\neq b$, since $y\in V^{+}$. If $y=c$,
then $(c,b^{\prime})\in E(D)$. Thus, by $(\star.1)$, with the edge
$(a^{\prime},c)\in E(D)$. A contradiction by (b) in Lemma 4.3, since $c=y\in
V^{+}$. Hence, $y\notin V(C)$. By Remark 2.6,
$\mathcal{C}_{5}=\big{(}\mathcal{C}\setminus\\{a^{\prime}\\}\big{)}\cup
N_{D}(a^{\prime})\cup N_{D}^{+}(y,a)$ is a vertex cover. By Remark 2.6,
$a^{\prime}\notin N_{D}^{+}(y,a)$, since $(a^{\prime},a)\in E(D)$ and $y\notin
N_{D}^{-}(a^{\prime})$. Consequently, $a^{\prime}\notin\mathcal{C}_{5}$. By
Proposition 3.1, there is a strong vertex cover $\mathcal{C}_{5}^{\prime}$
such that
$N_{D}^{+}(a,y)\subseteq\mathcal{C}_{5}^{\prime}\subseteq\mathcal{C}_{5}$,
since $\\{a,y\\}\subseteq V^{+}$. So,
$a^{\prime}\notin\mathcal{C}_{5}^{\prime}$, since
$a^{\prime}\notin\mathcal{C}_{5}$. Then, by Remark 2.8 $a,c\in
N_{D}(a^{\prime})\subseteq\mathcal{C}_{5}^{\prime}$. Furthermore,
$b,b^{\prime}\in N_{D}^{+}(a,y)\subseteq\mathcal{C}_{5}^{\prime}$. Hence,
$|\mathcal{C}_{5}^{\prime}\cap V(C)|=4$, a contradiction.  $\Box$

###### Lemma 4.7

Let $\mathcal{C}$ be a vertex cover of $D$ where $G$ is an $SCQ$ graph. Hence,
$|\mathcal{C}|=\tau(G)$ if and only if $|\mathcal{C}\cap V(K)|=|V(K)|-1$,
$|\mathcal{C}\cap V(C)|=3$ and $|\mathcal{C}\cap e|=1$ for each $K\in S_{G}$,
$C\in C_{G}$ and $e\in Q_{G}$, respectively.

Proof. We set $\mathcal{C}$ a vertex cover of $D$, $K\in S_{G}$, $C\in C_{G}$
and $e\in Q_{G}$. Then, there are $y\in V(G)$ and $a,a^{\prime}\in V(C)$ such
that $K=G[N_{G}[y]]$, $deg_{G}(a)=deg_{G}(a^{\prime})=2$ and
$\\{a,a^{\prime}\\}\notin E(G)$. We set $A_{K}:=V(K)\setminus\\{y\\}$ and
$B_{C}:=V(C)\setminus\\{a,a^{\prime}\\}$. Also, $\mathcal{C}\cap V(K)$ is a
vertex cover of $K$, so $|\mathcal{C}\cap V(K)|\geqslant\tau(K)=|V(K)|-1$.
Similarly, $|\mathcal{C}\cap V(C)|\geqslant\tau(C)=3$ and $|\mathcal{C}\cap
e|\geqslant\tau(e)=1$. Thus,

$|\mathcal{C}|=\sum\limits_{K\in S_{G}}|\mathcal{C}\cap
V(K)|+\sum\limits_{C\in C_{G}}|\mathcal{C}\cap V(C)|+\sum\limits_{e\in
Q_{G}}|\mathcal{C}\cap e|\geqslant\sum\limits_{K\in
S_{G}}\big{(}|V(K)|-1\big{)}+3|C_{G}|+|Q_{G}|,$ (4.1)

since $\mathcal{H}=\\{V(H)\mid H\in S_{G}\cup C_{G}\cup Q_{G}\\}$ is a
partition of $V(G)$. Now, we take a maximal stable set $S$ contained in
$V(Q_{G}):=\\{x\in V(G)\mid x\in e\ {\rm and}\ e\in Q_{G}\\}$. Then, $|S\cap
e|\leqslant 1$ for each $e\in Q_{G}$, since $S$ is stable. If $S\cap
e=\emptyset$ for some $e=\\{x_{1},x_{2}\\}\in Q_{G}$, then there are
$y_{1},y_{2}\in S$ such that $\\{x_{1},y_{1}\\}$, $\\{x_{2},y_{2}\\}\in E(G)$,
since $S$ is maximal. But $Q_{G}$ satisfies the property (P), then
$\\{y_{1},y_{2}\\}\in E(G)$. A contradiction, since $S$ is stable. Hence,
$|S\cap e|=1$ for each $e\in Q_{G}$. Consequently, $|S|=|Q_{G}|$ and
$|S^{\prime}|=|Q_{G}|$, where $S^{\prime}=V(Q_{G})\setminus S$. Now, we take

$\mathcal{C}(S^{\prime})=\Big{(}\bigcup\limits_{K\in
S_{G}}A_{K}\Big{)}\bigcup\Big{(}\bigcup\limits_{C\in C_{G}}B_{C}\Big{)}\bigcup
S^{\prime}$.

We prove $\mathcal{C}(S^{\prime})$ is a vertex cover of $D$. By contradiction,
suppose there is $\hat{e}\in E(G)$ such that
$\hat{e}\cap\mathcal{C}(S^{\prime})=\emptyset$. We set $z\in\hat{e}$, then
$\hat{e}=\\{z,z^{\prime}\\}$. If $z\in V(\tilde{K})$ for some $\tilde{K}\in
S_{G}$, then $\tilde{K}=G[N_{G}[z]]$, since
$A_{\tilde{K}}\subseteq\mathcal{C}(S^{\prime})$ and
$z\notin\mathcal{C}(S^{\prime})$. So, $z^{\prime}\in
N_{G}(z)\subseteq\tilde{K}\setminus\\{z\\}=A_{\tilde{K}}\subseteq\mathcal{C}(S^{\prime})$.
A contradiction, since $\hat{e}\cap\mathcal{C}(S^{\prime})=\emptyset$. Now, if
$z\in V(\tilde{C})$ for some $\tilde{C}\in C_{G}$, then $z\notin
B_{\tilde{C}}$. Thus, $deg_{G}(z)=2$ implying $z^{\prime}\in
B_{\tilde{C}}\subseteq\mathcal{C}(S^{\prime})$, since $\\{z,z^{\prime}\\}\in
E(G)$. A contradiction. Then, $\hat{e}\subseteq V(Q_{G})$, since $\mathcal{H}$
is a partition of $V(G)$. Also, $\hat{e}\cap S^{\prime}=\emptyset$, this
implies $\hat{e}\subseteq V(Q_{G})\setminus S^{\prime}=S$. But $S$ is stable.
This is a contradiction. Hence, $\mathcal{C}(S^{\prime})$ is a vertex cover of
$D$. Furthermore,

$|\mathcal{C}(S^{\prime})|=\sum\limits_{K\in S_{G}}|A_{K}|+\sum\limits_{C\in
C_{G}}|B_{C}|+|S^{\prime}|=\sum\limits_{K\in
S_{G}}\big{(}|V(K)|-1\big{)}+3|C_{G}|+|Q_{G}|$.

Thus, $\tau(G)=\sum_{K\in S_{G}}\big{(}|V(K)|-1\big{)}+3|C_{G}|+|Q_{G}|$.
Therefore, by (4.1), $|\mathcal{C}|=\tau(G)$ if and only if $|\mathcal{C}\cap
V(K)|=|K|-1$, $|\mathcal{C}\cap V(C)|=3$ and $|\mathcal{C}\cap e|=1$ for each
$K\in S_{G}$, $C\in C_{G}$ and $e\in Q_{G}$, respectively.  $\Box$

###### Theorem 4.8

Let $D=(G,\mathcal{O},w)$ be a weighted oriented graph where $G$ is an $SCQ$
graph. Hence, $I(D)$ is unmixed if and only if $D$ satisfies the following
conditions:

  1. (a)

Each basic $5$-cycle of $G$ has the $\star$-property.

  2. (b)

Each simplex of $D$ has no generating $\star$-semi-forests.

  3. (c)

$N_{D}(b)\subseteq N_{D}^{+}(a)$ when $a\in V^{+}$, $\\{b,b^{\prime}\\}\in
Q_{G}$ and $b^{\prime}\in N_{D}^{+}(a)$.

Proof. $\Rightarrow)$ We take a strong vertex cover $\mathcal{C}$ of $D$, then
by Remark 2.14, $|\mathcal{C}|=\tau(G)$. Consequently, by Lemma 4.7,
$|\mathcal{C}\cap V(K)|=|V(K)|-1$, $|\mathcal{C}\cap V(C)|=3$ and
$|\mathcal{C}\cap e|=1$ for each $K\in S_{G}$, $C\in C_{G}$ and $e\in Q_{G}$.
Thus, $V(K)\not\subseteq\mathcal{C}$. Consequently, by Theorem 3.10, $D$
satisfies (b). Furthermore, by Propositions 4.6 and 4.1, $D$ satisfies (a) and
(c).

$\Leftarrow)$ Let $\mathcal{C}$ be a strong vertex cover of $D$. By (a) and
Proposition 4.6, we have $|\mathcal{C}\cap V(C)|=3$ for each $C\in C_{G}$.
Furthermore, by (b) and Theorem 3.10, $V(K)\not\subseteq\mathcal{C}$ for each
$K\in S_{G}$. Consequently, $|V(K)|>|\mathcal{C}\cap
V(K)|\geqslant\tau(K)=|V(K)|-1$. So, $|\mathcal{C}\cap V(K)|=|V(K)|-1$. Now,
if $e\in Q_{G}$, then $e$ has the property (P), since $Q_{G}$ has the property
(P). Thus, by (c) and Proposition 4.1, $|\mathcal{C}\cap e|=1$. Hence, by
Lemma 4.7, $|\mathcal{C}|=\tau(G)$. Therefore $I(D)$ is unmixed, by $(2)$ in
Theorem 2.12.  $\Box$

###### Corollary 4.9

Let $D=(G,\mathcal{O},w)$ be a weighted oriented graph where $G$ is a
simplicial or chordal graph. Hence, $I(D)$ is unmixed if and only if $D$
satisfies the following conditions:

  1. (a)

Each vertex is in exactly one simplex of $D$.

  2. (b)

Each simplex of $D$ has not a generating $\star$-semi-forest.

Proof. $\Rightarrow)$ By $(3)$ in Theorem 2.12 and Remark 2.17, $G$ is well-
covered. Thus, by Theorem 2.26, $G$ satisfies (a). Furthermore, by Remark
2.29, $G$ is an $SCQ$ graph with $C_{G}=Q_{G}=\emptyset$. Hence, by Theorem
4.8, $D$ satifies (b).

$\Leftarrow)$ By (a), $\\{V(H)\mid H\in S_{G}\\}$ is a partition of $V(G)$.
Hence, $G$ is an $SCQ$ graph with $C_{G}=\emptyset$ and $Q_{G}=\emptyset$.
Therefore, by (b) and Theorem 4.8, $I(D)$ is unmixed.  $\Box$

##  5 Unmixedness of weighted oriented graphs without some small cycles

Let $D=(G,\mathcal{O},w)$ be a weighted oriented graph. In this Section, we
study and characterize the unmixed property of $I(D)$ when $G$ has no $3$\- or
$5$\- cycles (Theorem 5.4), or $G$ is a graph without $4$\- or $5$-cycles
(Theorem 5.10), or $girth(G)\geqslant 5$ (Theorem 5.13). In other words, in
this Section, we characterize the unmixed property of $I(D)$ when $G$ has at
most one of the following types of cycles: $3$-cycles, $4$-cycles and
$5$-cycles.

###### Proposition 5.1

If for each $(y,x)\in E(D)$ with $y\in V^{+}$, we have that
$N_{D}(y^{\prime})\subseteq N_{D}^{+}(y)$ for some $y^{\prime}\in
N_{D}(x)\setminus y$, then $L_{3}(\mathcal{C})=\emptyset$ for each strong
vertex cover $\mathcal{C}$ of $D$.

Proof. By contradiction, suppose there is a strong vertex cover $\mathcal{C}$
of $D$ and $x\in L_{3}(\mathcal{C})$. Hence, there is
$y\in\big{(}\mathcal{C}\setminus L_{1}(\mathcal{C})\big{)}\cap V^{+}$ with
$(y,x)\in E(D)$. Then, $N_{D}(x)\subseteq\mathcal{C}$ and
$N_{D}^{+}(y)\subseteq\mathcal{C}$, since $x\in L_{3}(\mathcal{C})$ and
$y\in\mathcal{C}\setminus L_{1}(\mathcal{C})$. By hypothesis, there is a
vertex $y^{\prime}\in N_{D}(x)\setminus y\subseteq\mathcal{C}$ such that
$N_{D}(y^{\prime})\subseteq N_{D}^{+}(y)\subseteq\mathcal{C}$. Thus,
$y^{\prime}\in L_{3}(\mathcal{C})$. Since $\mathcal{C}$ is strong, there is
$(y_{1},y^{\prime})\in E(D)$ with $y_{1}\in V^{+}$. So, $y_{1}\in
N_{D}(y^{\prime})\subseteq N_{D}^{+}(y)$. On the other hand, $(y_{1},x_{1})\in
E(D)$ where $x_{1}:=y^{\prime}$ and $y_{1}\in V^{+}$, then by hypothesis,
there is $y_{1}^{\prime}\in N_{D}(x_{1})\setminus y_{1}$ such that
$N_{D}(y_{1}^{\prime})\subseteq N_{D}^{+}(y_{1})$. Hence, $y_{1}^{\prime}\in
N_{D}(x_{1})=N_{D}(y^{\prime})\subseteq N_{D}^{+}(y)$. Consequently, $y\in
N_{D}(y_{1}^{\prime})\subseteq N_{D}^{+}(y_{1})$. A contradiction, since
$y_{1}\in N_{D}^{+}(y)$.  $\Box$

###### Corollary 5.2

If $G$ is well-covered and $V^{+}$ is a subset of sinks, then $I(D)$ is
unmixed.

Proof. If $y\in V^{+}$, then $y$ is a sink. Thus, $(y,x)\notin E(D)$ for each
$x\in V(D)$. Hence, by Proposition 5.1, $L_{3}(\mathcal{C})=\emptyset$, for
each strong vertex cover $\mathcal{C}$ of $D$. Furthermore, by Remark 2.17,
$I(G)$ is unmixed. Therefore $I(D)$ is unmixed, by $(3)$ in Theorem 2.12.
$\Box$

###### Lemma 5.3

Let $(z,y),(y,x)$ be edges of $D$ with $y\in V^{+}$ and
$N_{D}(x)=\\{y,x_{1},\ldots,x_{s}\\}$. If there are $z_{i}\in
N_{D}(x_{i})\setminus N_{D}^{+}(y)$ such that $\\{z,x,z_{1},\ldots,z_{s}\\}$
is a stable set, then $I(D)$ is mixed.

Proof. We take $A:=\\{z,z_{1},\ldots,z_{s}\\}$, then $A\cup\\{x\\}$ is a
stable set. We can take a maximal stable set $S$ of $V(G)$, such that
$A\cup\\{x\\}\subseteq S$. So, $\tilde{\mathcal{C}}=V(G)\setminus S$ is a
minimal vertex cover of $D$. Hence, $\mathcal{C}=\tilde{\mathcal{C}}\cup
N_{D}^{+}(y)$ is a vertex cover of $D$. Also $A\cap\mathcal{C}=\emptyset$,
since $A\subseteq S$, $z\in N_{D}^{-}(y)$ and $z_{i}\notin N_{D}^{+}(y)$. By
Proposition 3.1, there is a strong vertex cover $\mathcal{C}^{\prime}$ of $D$
such that $N_{D}^{+}(y)\subseteq\mathcal{C}^{\prime}\subseteq\mathcal{C}$,
since $y\in V^{+}$. Thus, $A\cap\mathcal{C}^{\prime}=\emptyset$, since
$A\cap\mathcal{C}=\emptyset$. Then, by Remark 2.8,
$N_{D}(A)\subseteq\mathcal{C}^{\prime}$. Furthermore
$N_{D}(x)=\\{y,x_{1},\ldots,x_{s}\\}\subseteq N_{D}(A)$. Consequently,
$N_{D}(x)\subseteq\mathcal{C}^{\prime}$. Hence, $x\in
L_{3}(\mathcal{C}^{\prime})$, since $x\in
N_{D}^{+}(y)\subseteq\mathcal{C}^{\prime}$. Therefore, by (3) in Theorem 2.12,
$I(D)$ is mixed.  $\Box$

###### Theorem 5.4

Let $D=(G,\mathcal{O},w)$ be a weighted oriented graph such that $G$ has no
$3$\- or $5$-cycles. Hence, $I(D)$ is unmixed if and only if $D$ satisfies the
following conditions:

  1. (a)

$G$ is well-covered.

  2. (b)

If $(y,x)\in E(D)$ with $y\in V^{+}$, then $N_{D}(y^{\prime})\subseteq
N_{D}^{+}(y)$ for some $y^{\prime}\in N_{D}(x)\setminus y$.

Proof. $\Leftarrow)$ By Proposition 5.1 and (b), we have that
$L_{3}(\mathcal{C})=\emptyset$ for each strong vertex cover $\mathcal{C}$ of
$D$. Furthermore, by (a) and Remark 2.17, $I(G)$ is unmixed. Therefore, by
$(3)$ in Theorem 2.12, $I(D)$ is unmixed.

$\Rightarrow)$ By (3) in Theorem 2.12 and Remark 2.17, $D$ satisfies (a). Now,
we take $(y,x)\in E(D)$ with $y\in V^{+}$. Then, by Remark 2.3, there is $z\in
N_{D}^{-}(y)$. Furthermore $z\notin N_{D}(x)$, since $G$ has no $3$-cycles. We
set $N_{D}(x)\setminus y=\\{x_{1},\ldots,x_{s}\\}$. We will prove (b). By
contradiction, suppose there is $z_{i}\in N_{D}(x_{i})\setminus N_{D}^{+}(y)$
for each $i=1,\ldots,s$. If $\\{z_{i},z_{j}\\}\in E(G)$ for some $1\leqslant
i<j\leqslant s$, then $(x,x_{i},z_{i},z_{j},x_{j},x)$ is a $5$-cycle. But $G$
has no $5$-cycles, then $\\{z_{1},\ldots,z_{s}\\}$ is a stable set. Now, if
$\\{x,z_{k}\\}\in E(G)$ or $\\{z,z_{k}\\}\in E(G)$ for some
$k\in\\{1,\ldots,s\\}$, then $(x,x_{k},z_{k},x)$ is a $3$-cycle or
$(z,y,x,x_{k},z_{k},z)$ is a $5$-cycle. Hence, $\\{x,z,z_{1},\ldots,z_{s}\\}$
is a stable set. A contradiction, by Lemma 5.3, since $I(D)$ is unmixed.
$\Box$

In the following results, we use the notation of Figure 1.

###### Remark 5.5

Let $G$ be a graph in $\\{C_{7},T_{10},P_{10},P_{13},P_{14},Q_{13}\\}$. Hence,

  1. (a)

$G$ does not contain $4$-cycles. Furthermore, if $G$ has a $3$-cycle, then
$G=T_{10}$.

  2. (b)

If $deg_{G}(x)=2$, then $x$ is not in a $3$-cycle of $G$.

  3. (c)

If $G\neq C_{7}$ and $\tilde{e}=\\{v,u\\}\in E(G)$ with
$deg_{D}(v)=deg_{D}(u)=2$, then
$\tilde{e}\in\\{\tilde{e}_{1},\tilde{e}_{2},\tilde{e}_{3}\\}$. Also, if
$\tilde{e}$ is in a $5$-cycle $C$, then $G\in\\{P_{10},P_{13}\\}$,
$\tilde{e}\in\\{\tilde{e}_{1},\tilde{e}_{2}\\}$ and $C\in\\{C_{1},C_{2}\\}$ or
$G=Q_{13}$, $\tilde{e}=\tilde{e}_{1}$ and $C=C_{1}$.

  4. (d)

If $P=(y_{1},y_{2},y_{3})$ is a path in $G$ with $deg_{G}(y_{i})=2$ for
$i=1,2,3$, then $G=C_{7}$.

Proof. (a) By Theorems 2.28 and 2.30, $G$ has no $4$-cycles. Now, if $G$ has a
$3$-cycle then, by Theorem 2.30, $G=T_{10}$.

(b) By (a), the unique $3$-cycle is $(c_{1},c_{2},c_{3},c_{1})$ in $T_{10}$
and $deg_{T_{10}}(c_{i})=3$ for $i=1,2,3$.

(c) By Figure 1, $\tilde{e}\in\\{\tilde{e}_{1},\tilde{e}_{2},\tilde{e}_{3}\\}$
and $G\in\\{T_{10},P_{10},P_{13},Q_{13}\\}$, since $G\neq C_{7}$. Now, assume
$\tilde{e}$ is in a $5$-cycle $C$. By Theorem 2.28, $G\neq T_{10}$. If
$G=P_{10}$, then $\tilde{e}_{3}$ is not in a $5$-cycle. Thus,
$\tilde{e}\in\\{\tilde{e}_{1},\tilde{e}_{2}\\}$ and $C\in\\{C_{1},C_{2}\\}$.
Now, if $G=P_{13}$, then $\tilde{e}\in\\{\tilde{e}_{1},\tilde{e}_{2}\\}$ and
$C\in\\{C_{1},C_{2}\\}$. Finally, if $G=Q_{13}$, then
$\tilde{e}_{2},\tilde{e}_{3}$ are not in a $5$-cycle. Hence,
$\tilde{e}=\tilde{e}_{1}$ and $C=C_{1}$.

(d) By contradiction, suppose $G\neq C_{7}$. If $e\in E(P)$, then by (c),
$e\in\\{e_{1},e_{2},e_{3}\\}$. But, $e_{i}\cap e_{j}=\emptyset$ for $i\neq j$.
A contradiction, since $P$ is a path.  $\Box$

###### Lemma 5.6

Let $G$ be a graph in $\\{C_{7},T_{10},P_{10},P_{13},P_{14},Q_{13}\\}$ with
$I(D)$ unmixed. If $(z,y),(y,x)\in E(D)$ with $y\in V^{+}$ and
$N_{D}(x)\setminus\\{y\\}=\\{x_{1}\\}$, then $deg_{D}(x_{1})=2$.

Proof. By contradiction, suppose $deg_{D}(x_{1})\geqslant 3$. Hence, there are
$z_{1},z_{1}^{\prime}\in N_{D}(x_{1})\setminus\\{x\\}$. By hypothesis,
$deg_{D}(x)=2$. Then, by (b) in Remark 5.5, $x$ is not in a $3$-cycle. So,
$x_{1}\neq z$. Furthermore, by (a) in Remark 5.5, $G$ has no $4$-cycles. Thus,
$z\notin\\{z_{1}^{\prime},z_{1}\\}$ and $z_{1},z_{1}^{\prime}\notin N_{D}(y)$.
If $z_{1}^{\prime},z_{1}\in N_{D}(z)$, then
$(x_{1},z_{1}^{\prime},z,z_{1},x_{1})$ is a $4$-cycle. A contradiction, then
we can assume $z_{1}\notin N_{D}(z)$. Consequently, $\\{x,z,z_{1}\\}$ is a
stable set, since $x$ is not in a $3$-cycle. A contradiction, by Lemma 5.3,
since $I(D)$ is unmixed.  $\Box$

###### Lemma 5.7

If $I(D)$ is unmixed, $G\in\\{C_{7},T_{10},P_{10},P_{13},P_{14},Q_{13}\\}$ and
$\tilde{e}=(y,x)\in E(D)$ with $deg_{D}(x)=2$ and $y\in V^{+}$, then
$G=P_{10}$ and $\tilde{e}=(d_{i},b_{j})$ with $\\{i,j\\}=\\{1,2\\}$.

Proof. By Remark 2.3, there is $z\in N_{D}^{-}(y)$. We set
$N_{D}(x)=\\{y,x_{1}\\}$, then by (b) in Remark 5.5, $z\neq x_{1}$. Thus, by
Lemma 5.6, $deg_{D}(x_{1})=2$. Now, we set $N_{D}(x_{1})=\\{x,z_{1}\\}$. By
(b) in Remark 5.5, $x$ is not in a $3$-cycle. So, $z,z_{1}\notin N_{D}(x)$ and
$z_{1}\neq y$. Also, by (a) in Remark 5.5, $G$ has no $4$-cycles. Then,
$z_{1}\neq z$ and $z_{1}\notin N_{D}(y)$. If $z\notin N_{D}(z_{1})$, then
$\\{x,z,z_{1}\\}$ is a stable set. A contradiction, by Lemma 5.3, since $I(D)$
is unmixed. Hence, $\\{z_{1},z\\}\in E(G)$ and $C:=(z,y,x,x_{1},z_{1},z)$ is a
$5$-cycle. Suppose $y^{\prime}\in N_{D}^{-}(y)\setminus\\{z\\}$, then
$y^{\prime}\notin N_{D}(z_{1})$, since $(z_{1},z,y,y^{\prime},z_{1})$ is not
in a $4$-cycle in $G$. Consequently, $\\{y^{\prime},x,z_{1}\\}$ is a stable
set, since $deg_{D}(x)=2$. A contradiction, by Lemma 5.3, since
$(y^{\prime},y),(y,x)\in E(D)$, $y\in V^{+}$, $N_{D}(x)=\\{y,x_{1}\\}$ and
$z_{1}\in N_{D}(x_{1})\setminus N_{D}^{+}(y)$. Hence, $N_{D}^{-}(y)=\\{z\\}$.
Now, by (c) in Remark 5.5 and by symmetry of $P_{10}$ and $P_{13}$, we can
assume $\\{x,x_{1}\\}=\tilde{e}_{1}$, $C=C_{1}$ and
$G\in\\{P_{10},P_{13},Q_{13}\\}$.

First, assume $G=P_{13}$. By symmetry and notation of Figure 1, we can suppose
$x_{1}=a_{1}$ and $x=a_{2}$, since $\tilde{e}_{1}=\\{x,x_{1}\\}$. Then,
$y=b_{2}$, $z=c_{1}$ and $z_{1}=b_{1}$. Thus, $(b_{2},d_{2})\in E(D)$, since
$y=b_{2}$ and $N_{D}^{-}(y)=\\{z\\}=\\{c_{1}\\}$. By Figure 1,
$(c_{1},b_{2})=(z,y)\in E(D)$, $(b_{2},d_{2})\in E(D)$, $b_{2}=y\in V^{+}$ and
$N_{D}(d_{2})=\\{b_{2},b_{4},v\\}$. Also, $a_{4}\in N_{D}(b_{4})$, $d_{1}\in
N_{D}(v)\setminus N_{D}(b_{2})$ and $\\{c_{1},d_{2},a_{4},d_{1}\\}$ is a
stable set. A contradiction, by Lemma 5.3, since $I(D)$ is unmixed.

Now, suppose $G=Q_{13}$. By the symmetry of we can suppose $x=a_{2}$ and
$x_{1}=a_{1}$, then $d_{2}=y\in V^{+}$, $z=h$ and $(h,d_{2})=(z,y)\in E(D)$.
So, $(d_{2},c_{2})\in E(D)$, since
$N_{D}^{-}(d_{2})=N_{D}^{-}(y)=\\{z\\}=\\{h\\}$. A contradiction, by Lemma
5.3, since $(h,d_{2}),(d_{2},c_{2})\in E(D)$, $d_{2}\in V^{+}$,
$N_{D}(c_{2})=\\{d_{2},b_{1}\\}$, $g_{1}\in N_{D}(b_{1})\setminus
N_{D}^{+}(d_{2})$ and $\\{h,c_{2},g_{1}\\}$ is a stable set.

Hence, $G=P_{10}$ and $\\{x,x_{1}\\}=\tilde{e}_{1}=\\{a_{1},b_{1}\\}$. If
$x=a_{1}$ and $x_{1}=b_{1}$, then $g_{1}=y\in V^{+}$, $(d_{1},g_{1})=(z,y)\in
E(D)$, since $C=C_{1}$. Furthermore, $(g_{1},c_{1})\in E(D)$, since
$N_{D}^{-}(g_{1})=N_{D}^{-}(y)=\\{z\\}=\\{d_{1}\\}$. A contradiction by Lemma
5.3, since $(d_{1},g_{1}),(g_{1},c_{1})\in E(D)$, $g_{1}\in V^{+}$,
$N_{D}(c_{1})=\\{g_{1},c_{2}\\}$, $g_{2}\in N_{D}(c_{2})$ and
$\\{d_{1},c_{1},g_{2}\\}$ is stable. Therefore, $x=b_{1}$ and $x_{1}=a_{1}$,
implying $y=d_{2}$ and $(y,x)=(d_{2},b_{1})$, since $C=C_{1}$.  $\Box$

###### Remark 5.8

Assume $I(D)$ is unmixed, $G\in\\{C_{7},T_{10},Q_{13},P_{13},P_{14}\\}$,
$\mathcal{C}$ is a strong vertex cover of $D$ and $y\in\mathcal{C}\cap V^{+}$
such that $N_{G}(y)\setminus\mathcal{C}\subseteq V_{2}:=\\{a\in V(G)\mid
deg_{G}(a)=2\\}$. We take $b\in N_{G}(y)\setminus\mathcal{C}$. If $(y,b)\in
E(D)$, then by Lemma 5.7, $G=P_{10}$. A contradiction, then $(b,y)\in E(D)$.
Consequently, $N_{D}(y)\setminus\mathcal{C}\subseteq N_{D}^{-}(y)$, i.e.
$N_{D}^{+}(y)\subseteq\mathcal{C}$. Hence, $y\in\mathcal{C}\setminus
L_{1}(\mathcal{C})$.

###### Proposition 5.9

If $I(D)$ is unmixed, with $G\in\\{C_{7},T_{10},Q_{13},P_{13},P_{14}\\}$, then
the vertices of $V^{+}$ are sinks.

Proof. By contradiction, suppose there is $(y,x)\in E(D)$ with $y\in V^{+}$.
Then, by Lemma 5.7, $deg_{D}(x)\geqslant 3$. Thus, $G\neq C_{7}$. By Remark
2.3, $y$ is not a source. So, there is $(z,y)\in E(D)$. We set $V_{2}:=\\{a\in
V(G)\mid deg_{G}(a)=2\\}$. By Theorem 2.12,
$L_{3}(\tilde{\mathcal{C}})=\emptyset$ for each strong vertex cover
$\tilde{\mathcal{C}}$ of $D$, since $I(D)$ is unmixed. Hence, to obtain a
contradiction, we will give a vertex cover $\mathcal{C}$ of $D$ such that
$L_{3}(\mathcal{C})=\\{x\\}$ and $y\in\mathcal{C}\setminus
L_{1}(\mathcal{C})$, since with these conditions $\mathcal{C}$ is strong. We
will use the notation of Figure 1.

Case (1) If $D=T_{10}$, then $x\in\\{c_{1},c_{2},c_{3},v\\}$, since
$deg_{G}(x)\geqslant 3$.

Case (1.a) $x\in\\{c_{1},c_{2},c_{3}\\}$. By symmetry of $P_{10}$, we can
assume $x=c_{1}$ and $y\in\\{b_{1},c_{2}\\}$. Thus,
$\mathcal{C}_{1}=\\{v,a_{2},a_{3},b_{1},c_{1},c_{2},c_{3}\\}$ is a vertex
cover with $L_{3}(\mathcal{C}_{1})=\\{x\\}$. If $y=b_{1}$, then $y\in C_{1}$
and $z=a_{1}$, since $N_{D}(b_{1})=\\{a_{1},c_{1}\\}$. So,
$N_{D}^{+}(y)=\\{c_{1}\\}\subseteq\mathcal{C}_{1}$. Now, if $y=c_{2}$, then
$y\in\mathcal{C}_{1}$. Furthermore, by Lemma 5.7, $(b_{2},c_{2})\in E(D)$,
since $c_{2}=y\in V^{+}$, $b_{2}\in V_{2}$ and $I(D)$ is unmixed.
Consequently,
$N_{D}^{+}(y)\subseteq\\{c_{1},c_{3}\\}\subseteq\mathcal{C}_{1}$. Hence,
$y\in\mathcal{C}_{1}\setminus L_{1}(\mathcal{C}_{1})$ and we take
$\mathcal{C}=\mathcal{C}_{1}$.

Case (1.b) $x=v$. Then,
$\mathcal{C}_{2}=\\{v,a_{1},a_{2},a_{3},c_{1},c_{2},c_{3}\\}$ is a vertex
cover with $L_{3}(\mathcal{C}_{2})=\\{x\\}$. By symmetry of $P_{10}$, we can
suppose $y=a_{1}$. Consequently, $z=b_{1}$ and
$N_{D}^{+}(y)=\\{v\\}\subseteq\mathcal{C}_{2}$, since $a_{1}\in V_{2}$. Hence,
$y\in\mathcal{C}_{2}\setminus L_{1}(\mathcal{C}_{2})$ and we take
$\mathcal{C}=\mathcal{C}_{2}$.

Case (2) If $D=P_{14}$, then, by symmetry, we can assume $y=a_{1}$ and
$x\in\\{a_{2},b_{1}\\}$.

Case (2.a) $x=a_{2}$. Thus, $z\in\\{a_{7},b_{1}\\}$. We take
$\mathcal{C}_{3}=\\{a_{1},a_{2},a_{3},a_{4},a_{6},b_{1},b_{2},b_{5},b_{6},b_{7}\\}$
if $z=a_{7}$ or
$\mathcal{C}_{3}=\\{a_{1},a_{2},a_{3},a_{5},a_{7},b_{2},b_{3},b_{4},b_{5},b_{6}\\}$
if $z=b_{1}$. So, $\mathcal{C}_{3}$ is a vertex cover of $D$,
$y\in\mathcal{C}_{3}$ and $L_{3}(\mathcal{C}_{3})=\\{x\\}$. Furthermore,
$N_{D}(y)\setminus\mathcal{C}_{3}=\\{z\\}$ and $z\in N_{D}^{-}(y)$, then
$y\in\mathcal{C}_{3}\setminus L_{1}(\mathcal{C}_{3})$ and we take
$\mathcal{C}=\mathcal{C}_{3}$.

Case (2.b) $x=b_{1}$. By symmetry of $P_{14}$, we can suppose $z=a_{2}$. Then,
$\mathcal{C}_{4}=\\{a_{1},a_{3},a_{4},a_{5},a_{7},b_{1},b_{2},b_{3},b_{6},b_{7}\\}$
is a vertex cover of $D$ with $L_{3}(\mathcal{C}_{4})=\\{x\\}$. Also,
$N_{D}(y)=\setminus\mathcal{C}_{4}=\\{a_{2}\\}$ and $a_{2}=z\in N_{D}^{-}(y)$.
Hence, $y\in\mathcal{C}_{4}\setminus L_{1}(\mathcal{C}_{4})$ and we take
$\mathcal{C}=\mathcal{C}_{4}$.

Case (3) If $D=P_{13}$, then we can assume $x\in\\{b_{1},c_{2},d_{1}\\}$,
since $deg_{G}(x)\geqslant 3$.

Case (3.a) $x=c_{2}$. Then, $y\in N_{D}(c_{2})=\\{b_{3},b_{4},c_{1}\\}$.
Without loss of generality, we can suppose $y\in\\{b_{3},c_{1}\\}$. If
$y=c_{1}$, then $z\in\\{b_{1},b_{2}\\}$. By symmetry, we can assume $z=b_{1}$
so $N_{D}^{+}(y)=N_{D}^{+}(c_{1})\subseteq\\{b_{2},c_{2}\\}$. We take
$\mathcal{C}_{5}=\\{a_{1},a_{4},b_{2},b_{3},b_{4},c_{1},c_{2},d_{1},v\\}$.
Thus, $\mathcal{C}_{5}$ is a vertex cover of $D$ with
$L_{3}(\mathcal{C}_{5})=\\{x\\}$, $y\in\mathcal{C}_{5}$ and
$N_{D}^{+}(y)\subseteq\\{b_{2},c_{2}\\}\subseteq\mathcal{C}_{5}$. Now, if
$y=b_{3}$, then $b_{3}\in V^{+}\cap\mathcal{C}_{5}$. Hence, by Lemma 5.7,
$(a_{3},b_{3})\in E(D)$, since $a_{3}\in V_{2}$ and $I(D)$ is unmixed.
Consequently, $N_{D}^{+}(y)\subseteq\\{c_{2},d_{1}\\}\subset\mathcal{C}_{5}$.
Therefore, $y\in\mathcal{C}_{5}\setminus L_{1}(\mathcal{C}_{5})$ and we take
$\mathcal{C}=\mathcal{C}_{5}$.

Case (3.b) $x=b_{1}$. Hence,
$\mathcal{C}_{6}=\\{a_{1},a_{3},b_{1},b_{2},b_{3},b_{4},c_{1},d_{1},d_{2}\\}$
is a vertex cover of $D$ with $L_{3}(\mathcal{C}_{6})=\\{x\\}$ and $y\in
N_{D}(b_{1})=\\{a_{1},c_{1},d_{1}\\}$. Also, $y\in\mathcal{C}_{6}$. If
$y\in\\{a_{1},d_{1}\\}$, then
$N_{D}(y)\setminus\mathcal{C}_{6}\subseteq\\{a_{2},v\\}\subseteq V_{2}$.
Consequently, by Lemma 5.7, $(b,y)\in E(D)$ for each $b\in
N_{D}(y)\setminus\mathcal{C}_{6}$, since $y\in V^{+}$. So,
$N_{D}^{+}\subseteq\mathcal{C}_{6}$ implying $y\in\mathcal{C}_{6}\setminus
L_{1}(\mathcal{C}_{6})$. Now, if $y=c_{1}$. We can assume $(c_{2},c_{1})\in
E(D)$, since in another case we have the case (3.a) with $x=c_{2}$ and
$y=c_{1}$. Thus, $y=c_{1}\in\mathcal{C}_{6}\setminus L_{1}(\mathcal{C}_{6})$,
since $N_{D}^{+}(c_{1})\subseteq\\{b_{1},b_{2}\\}\subset\mathcal{C}_{6}$.
Therefore, we take $\mathcal{C}=\mathcal{C}_{6}$.

Case (3.c) $x=d_{1}$. Then, $y\in N_{G}(d_{1})=\\{b_{1},b_{3},v\\}$. By
symmetry, we can assume $y\in\\{b_{1},v\\}$. Furthermore,
$\mathcal{C}_{7}=\\{a_{2},a_{4},b_{1},b_{2},b_{3},b_{4},c_{1},d_{1},v\\}$ is a
vertex cover of $D$ with $L_{3}(\mathcal{C}_{7})=\\{x\\}$ and
$y\in\mathcal{C}_{7}$. If $y=b_{1}$, then
$N_{D}(y)\setminus\mathcal{C}_{7}\subseteq\\{a_{1}\\}$. Also, by Lemma 5.7,
$N_{D}(y)\setminus\mathcal{C}_{7}\subseteq N_{D}^{-}(y)$, since $a_{1}\in
V_{2}$ and $y\in V^{+}$. Thus, $y\in\mathcal{C}_{7}\setminus
L_{1}(\mathcal{C}_{7})$. Now, if $y=v$, then $z=d_{2}$, since
$N_{D}(v)=\\{d_{1},d_{2}\\}$. This implies
$N_{D}^{+}(v)=\\{d_{1}\\}\subseteq\mathcal{C}_{7}$. So,
$y\in\mathcal{C}_{7}\setminus L_{1}(\mathcal{C}_{7})$ and we take
$\mathcal{C}=\mathcal{C}_{7}$.

Case (4) $D=Q_{13}$. Hence, $x\in\\{d_{1},d_{2},g_{1},g_{2},h,h^{\prime}\\}$,
since $deg_{D}(x)\geqslant 3$. By symmetry, we can suppose
$x\in\\{d_{2},g_{2},h,h^{\prime}\\}$.

Case (4.a) $x\in\\{d_{2},g_{2}\\}$. We take
$\mathcal{C}_{8}=\\{a_{2},c_{1},c_{2},d_{1},d_{2},g_{1},g_{2},h,h^{\prime}\\}$
if $x=d_{2}$ or
$\mathcal{C}_{8}=\\{a_{1},b_{2},c_{2},d_{1},d_{2},g_{1},g_{2},h,h^{\prime}\\}$
if $x=g_{2}$. Thus, $\mathcal{C}_{8}$ is a vertex cover of $D$ with
$L_{3}(\mathcal{C}_{8})=\\{x\\}$ and
$V(G)\setminus\mathcal{C}_{8}=\\{a_{1},b_{1},b_{2},v\\}\cup\\{a_{2},b_{1},c_{1},v\\}\subseteq
V_{2}$. Consequently, by Lemma 5.7, $N_{D}(y)\setminus\mathcal{C}_{8}\subseteq
N_{D}^{-}(y)$, since $y\in V^{+}$. This implies
$N_{D}^{+}(y)\subseteq\mathcal{C}_{8}$. Therefore
$y\in\mathcal{C}_{8}\setminus L_{1}(\mathcal{C}_{8})$ and we take
$\mathcal{C}=\mathcal{C}_{8}$.

Case (4.b) $x\in\\{h,h^{\prime}\\}$. We take
$\mathcal{C}_{9}=\\{a_{2},b_{1},b_{2},d_{1},d_{2},g_{1},g_{2},h,v\\}$ if $x=h$
or
$\mathcal{C}_{9}=\\{a_{2},c_{1},c_{2},d_{1},d_{2},g_{1},g_{2},h^{\prime},v\\}$
if $x=h^{\prime}$. Thus, $\mathcal{C}_{9}$ is a vertex cover of $D$ with
$L_{3}(\mathcal{C}_{9})=\\{x\\}$. Also, $y\in
N_{G}(x)\subseteq\\{v,d_{1},d_{2},g_{1},g_{2}\\}$. If $y=v$, then
$\\{x,z\\}\subseteq N_{D}(y)=\\{h,h^{\prime}\\}$. Hence,
$N_{D}^{+}(y)=\\{x\\}\subseteq\mathcal{C}_{9}$, then
$y\in\mathcal{C}_{9}\setminus L_{1}(\mathcal{C}_{9})$. Now, if $y\neq v$, then
$y\in\\{d_{1},d_{2}\\}$ when $x=h$ or $y\in\\{g_{1},g_{2}\\}$ when
$x=h^{\prime}$. Then,
$N_{D}(y)\setminus\mathcal{C}_{9}\subseteq\\{a_{1},c_{1},c_{2}\\}\subseteq
V_{2}$ if $x=h$ or
$N_{D}(y)\setminus\mathcal{C}_{9}\subseteq\\{b_{1},b_{2}\\}\subseteq V_{2}$ if
$x=h^{\prime}$. Consequently, by Lemma 5.7,
$N_{D}(y)\setminus\mathcal{C}_{9}\subseteq N_{D}^{-}(y)$, since $y\in V^{+}$.
Thus, $N_{D}^{+}(y)\subseteq\mathcal{C}_{9}$ and $y\in\mathcal{C}_{9}\setminus
L_{1}(\mathcal{C}_{9})$. Therefore, we take $\mathcal{C}=\mathcal{C}_{9}$.
$\Box$

###### Theorem 5.10

Let $D=(G,\mathcal{O},w)$ be a connected weighted oriented graph without $4$\-
and $5$-cycles. Hence, $I(D)$ is unmixed if and only if $D$ satisfies one of
the following conditions:

  1. (a)

$G\in\\{C_{7},T_{10}\\}$ and the vertices of $V^{+}$ are sinks.

  2. (b)

Each vertex is in exactly one simplex of $D$ and each simplex of $D$ has no
generating $\star$-semi-forests.

Proof. $\Rightarrow)$ By (3) in Theorem 2.12 and Remark 2.17, $G$ is well-
covered. Thus, by Theorem 2.28, $G\in\\{C_{7},T_{10}\\}$ or $\\{V(H)\mid H\in
S_{G}\\}$ is a partition of $V(G)$. If $G\in\\{C_{7},T_{10}\\}$, then by
Proposition 5.9, $D$ satisfies (a). Now, if $\\{V(H)\mid H\in S_{G}\\}$ is a
partition of $V(G)$, then $G$ is an $SCQ$ graph with $C_{G}=Q_{G}=\emptyset$.
Hence, by Theorem 4.8, $D$ satisfies (b).

$\Leftarrow)$ If $D$ satisfies (a), then by Theorem 2.28, $G$ is well-covered.
Consequently, by Corollary 5.2, $I(D)$ is unmixed. Now, if $D$ satisfies (b),
then $G$ is an $SCQ$ graph, with $C_{G}=Q_{G}=\emptyset$. Therefore, by (b)
and Theorem 4.8, $I(D)$ is unmixed.  $\Box$

###### Corollary 5.11

Let $D$ be a weighted oriented graph without isolated vertices and
$girth(G)\geqslant 6$. Hence, $I(D)$ is unmixed if and only if $D$ satisfies
one of following properties:

  1. (a)

$G=C_{7}$ and the vertices of $V^{+}$ are sinks.

  2. (b)

$G$ has a perfect matching
$e_{1}=\\{x_{1},x_{1}^{\prime}\\},\ldots,e_{r}=\\{x_{r},x_{r}^{\prime}\\}$
where $deg_{D}(x_{1}^{\prime})=\cdots=deg_{D}(x_{r}^{\prime})=1$ and
$(x_{j}^{\prime},x_{j})\in E(D)$ if $x_{j}\in V^{+}$.

Proof. $\Leftarrow)$ If $D$ satisfies (a), then $I(D)$ is unmixed by (a) in
Theorem 5.10. Now, assume $D$ satisfies (b). Assume $b^{\prime}\in
N_{D}^{+}(a)$ with $a\in V^{+}$ such that
$\\{b,b^{\prime}\\}=e_{j}=\\{x_{j},x_{j}^{\prime}\\}$ for some $1\leqslant
j\leqslant r$. If $b^{\prime}=x_{j}^{\prime}$, then $x_{j}=a\in V^{+}$, since
$deg_{D}(x_{j}^{\prime})=1$. So, $x_{j}^{\prime}=b^{\prime}\in
N_{D}^{+}(a)=N_{D}^{+}(x_{j})$. But by hypothesis, $(x_{j}^{\prime},x_{j})\in
E(D)$, since $x_{j}\in V^{+}$. A contradiction, then $b^{\prime}=x_{j}$. Thus,
$b=x_{j}^{\prime}$ implies $N_{D}(b)=\\{x_{j}\\}=\\{b^{\prime}\\}\subseteq
N_{D}^{+}(a)$. Hence, by Proposition 4.1, $|\mathcal{C}\cap e_{j}|=1$ where
$\mathcal{C}$ is a strong vertex cover. So, $|\mathcal{C}|=r$. Therefore, by
(2) in Theorem 2.12, $I(D)$ is unmixed.

$\Rightarrow)$ $G\neq T_{10}$, since $T_{10}$ has $3$-cycles. Hence, by
Theorem 5.10, $D$ satisfies (a) or $\\{V(H)\mid H\in S_{G}\\}$ is a partition
of $V(G)$. Furthermore, $S_{G}\subseteq E(G)$, since $G$ has not isolated
vertices and $girth(G)\geqslant 6$. Thus, we can assume
$S_{G}=\\{e_{1},\ldots,e_{r}\\}$ where $e_{i}=\\{x_{i},x_{i}^{\prime}\\}$ and
$deg_{D}(x_{i}^{\prime})=1$ for $i=1,\ldots,s$. Also, by Theorem 5.10, each
$e_{i}$ has no generating $\star$-semi-forests. So, by Theorem 3.10,
$e_{i}\not\subseteq\mathcal{C}$ for each strong vertex cover $\mathcal{C}$.
Consequently, $|e_{i}\cap\mathcal{C}|=1$, since $\mathcal{C}$ is a vertex
cover. Then, $e_{i}$ satisfies (2) of Proposition 4.1. Now, suppose
$(x_{j},x_{j}^{\prime})\in E(D)$ and $x_{j}\in V^{+}$. We take $a=b=x_{j}$ and
$b^{\prime}=x_{j}^{\prime}$, then by (2) of Proposition 4.1,
$N_{D}(x_{j})=N_{D}(b)\subseteq N_{D}^{+}(a)=N_{D}^{+}(x_{j})$. Hence, $x_{j}$
is a source. A contradiction, by Remark 2.3, since $x_{j}\in V^{+}$.
Therefore, $D$ satisfies (b).  $\Box$

###### Proposition 5.12

If $G=P_{10}$, then the following properties are equivalent:

  1. (1)

$I(D)$ is unmixed.

  2. (2)

If $y\in V^{+}$ and $y$ is not a sink, then $y=d_{1}$ with
$N_{D}^{+}(y)=\\{g_{1},b_{2}\\}$ or $y=d_{2}$ with
$N_{D}^{+}(y)=\\{g_{2},b_{1}\\}$.

Proof. ${\rm(2)}\Rightarrow{\rm(1)}$ Let $\mathcal{C}$ be a strong vertex
cover of $D$. Suppose $x\in L_{3}(\mathcal{C})$. Then, there is
$y\in\big{(}\mathcal{C}\setminus L_{1}(\mathcal{C})\big{)}\cap V^{+}$ such
that $x\in N_{D}^{+}(y)$. Thus, by (2), $y\in\\{d_{1},d_{2}\\}$ and $x\in
N_{D}^{+}(y)\subseteq\\{b_{1},b_{2},g_{1},g_{2}\\}$. Hence,
$L_{3}(\mathcal{C})\subseteq\\{b_{1},b_{2},g_{1},g_{2}\\}$. By symmetry of
$P_{10}$, we can assume $y=d_{1}$. Then by (2), $x\in
N_{D}^{+}(y)=\\{g_{1},b_{2}\\}$. Also,
$\\{g_{1},d_{1},b_{2}\\}=N_{D}^{+}[y]\subseteq\mathcal{C}$, since
$y\in\mathcal{C}\setminus L_{1}(\mathcal{C})$. But $y=d_{1}\notin
L_{3}(\mathcal{C})$, then $N_{D}(y)\not\subseteq\mathcal{C}$. Thus,
$d_{2}\notin\mathcal{C}$. So, by Remark 2.8,
$\\{b_{1},d_{1},g_{2}\\}=N_{D}(d_{2})\subseteq\mathcal{C}$. Furthermore,
$\\{a_{1},a_{2}\\}\cap L_{3}(\mathcal{C})=\emptyset$, since
$L_{3}(\mathcal{C})\subseteq\\{b_{1},b_{2},g_{1},g_{2}\\}$. Consequently,
$\\{a_{1},a_{2}\\}\cap\mathcal{C}=\emptyset$, since
$N_{D}(a_{1},a_{2})=\\{g_{1},b_{1},g_{2},b_{2}\\}\subseteq\mathcal{C}$. But,
$x\in\\{g_{1},b_{2}\\}\cap L_{3}(\mathcal{C})$, then $a_{1}\in
N_{D}(g_{1})\subseteq\mathcal{C}$ or $a_{2}\in
N_{D}(b_{2})\subseteq\mathcal{C}$. Hence,
$\\{a_{1},a_{2}\\}\cap\mathcal{C}\neq\emptyset$. A contradiction, then
$L_{3}(\mathcal{C})=\emptyset$. Also, by Theorem 2.28 and Remark 2.17, $I(G)$
is unmixed. Therefore, by (3) in Theorem 2.12, $I(D)$ is unmixed.

${\rm(1)}\Rightarrow{\rm(2)}$ We take $V_{2}:=\\{a\in V(G)\mid
deg_{G}(a)=2\\}$ and $y\in V^{+}$, such that $y$ is not a sink, then there is
$(y,x)\in E(D)$. Also, by Remark 2.3, there is $z\in N_{D}^{-}(y)$. We will
prove $y\in\\{d_{1},d_{2}\\}$. If $deg_{D}(x)=2$, then by Lemma 5.7,
$y\in\\{d_{1},d_{2}\\}$. Now, we assume $deg_{D}(x)\geqslant 3$, then by
symmetry of $P_{10}$, we can suppose $x\in\\{g_{1},d_{1}\\}$.

First suppose $x=g_{1}$. Thus, $y\in N_{D}(g_{1})=\\{a_{1},c_{1},d_{1}\\}$. If
$y\in\\{a_{1},c_{1}\\}$, then $deg_{D}(y)=2$ and
$y\in\mathcal{C}_{1}=\\{a_{1},a_{2},c_{1},d_{1},d_{2},g_{1},g_{2}\\}$ is a
vertex cover of $D$ with $L_{3}(\mathcal{C}_{1})=\\{x\\}$. Hence,
$N_{D}(y)=\\{x,z\\}$ implies
$N_{D}^{+}(y)=\\{x\\}=\\{g_{1}\\}\subseteq\mathcal{C}_{1}$. Consequently,
$y\in\mathcal{C}_{1}\setminus L_{1}(\mathcal{C}_{1})$. Hence,
$\mathcal{C}_{1}$ is strong, since $L_{3}(\mathcal{C}_{1})=\\{x\\}$. A
contradiction, by Theorem 2.12, then $y=d_{1}$.

Now, suppose $x=d_{1}$. Then,
$\mathcal{C}_{2}=\\{a_{1},b_{2},c_{2},d_{1},d_{2},g_{1},g_{2}\\}$ is a vertex
cover of $D$ with $L_{3}(\mathcal{C}_{2})=\\{x\\}$. Also, $y\in
N_{D}(x)=\\{g_{1},b_{2},d_{2}\\}$. If $y\in\\{g_{1},b_{2}\\}$, then
$N_{D}(y)\setminus\\{d_{1}\\}\subseteq
N_{D}(g_{1},b_{2})\setminus\\{d_{1}\\}=\\{a_{1},a_{2},c_{1}\\}\subseteq
V_{2}$. Hence, by Lemma 5.7, $N_{D}(y)\setminus\\{d_{1}\\}\subseteq
N_{D}^{-}(y)$, since $y\notin\\{b_{1},b_{2}\\}$. Thus,
$N_{D}^{+}(y)=\\{d_{1}\\}=\\{x\\}\subseteq\mathcal{C}_{2}$ implying
$y\in\mathcal{C}_{2}\setminus L_{1}(\mathcal{C}_{2})$. Consequently,
$\mathcal{C}_{2}$ is strong with $L_{3}(\mathcal{C}_{2})\neq\emptyset$. A
contradiction, by Theorem 2.12, then $y=d_{2}$.

Therefore $y\in\\{d_{1},d_{2}\\}$. By symmetry of $P_{10}$, we can assume
$y=d_{1}$. Now, we will prove $N_{D}^{+}(y)=\\{g_{1},b_{2}\\}$. By
contradiction, in each one of the following cases, we give a strong vertex
cover $\mathcal{C}^{\prime}$ with $L_{3}(\mathcal{C}^{\prime})\neq\emptyset$,
since $I(D)$ is unmixed and $z\in N_{D}^{-}(y)$.

Case (1) $g_{1}\notin N_{D}^{+}(d_{1})$ and $b_{2}\in N_{D}^{+}(d_{1})$. So,
$N_{D}^{+}(d_{1})\subseteq\\{b_{2},d_{2}\\}$ and $\mathcal{C}_{1}^{\prime}=$
$\\{a_{1},a_{2},b_{2},c_{1},c_{2},d_{1},d_{2}\\}$ is a vertex cover of $D$
with $L_{3}(\mathcal{C}_{1}^{\prime})=\\{b_{2}\\}$. Also, $(d_{1},b_{2})\in
E(D)$ and $y=d_{1}\in\big{(}\mathcal{C}_{1}^{\prime}\setminus
L_{1}(\mathcal{C}_{1}^{\prime})\big{)}\cap V^{+}$, since $b_{2}\in
N_{D}^{+}[d_{1}]\subseteq\\{d_{1},b_{2},d_{2}\\}\subset\mathcal{C}_{1}^{\prime}$.
Hence, $\mathcal{C}_{1}^{\prime}$ is a strong vertex cover of $D$.

Case (2) $b_{2}\notin N_{D}^{+}(d_{1})$ and $g_{1}\in N_{D}^{+}(d_{1})$. Then,
$N_{D}^{+}(d_{1})\subseteq\\{g_{1},d_{2}\\}$ and $\mathcal{C}_{2}^{\prime}=$
$\\{a_{1},a_{2},c_{1},d_{1},d_{2},g_{1},g_{2}\\}$ is a vertex cover of $D$
with $L_{3}(\mathcal{C}_{2}^{\prime})=\\{g_{1}\\}$. Furthermore
$(d_{1},g_{1})\in E(D)$ and
$d_{1}=y\in\big{(}\mathcal{C}_{2}^{\prime}\setminus
L_{1}(\mathcal{C}_{2}^{\prime})\big{)}\cap V^{+}$, since $g_{1}\in
N_{D}^{+}[d_{1}]\subseteq\\{d_{1},g_{1},d_{2}\\}\subset\mathcal{C}_{2}^{\prime}$.
Hence, $\mathcal{C}_{2}^{\prime}$ is a strong vertex cover of $D$.

Case (3) $b_{2},g_{1}\notin N_{D}^{+}(d_{1})$. Thus, $z=d_{1}$,
$N_{D}^{+}(d_{1})=\\{d_{2}\\}$ and $\mathcal{C}_{3}^{\prime}=$
$\\{a_{2},b_{1},c_{1},d_{1},d_{2},g_{1},g_{2}\\}$ is a vertex cover of $D$
with $L_{6}(\mathcal{C}_{3}^{\prime})=\\{d_{2}\\}$. Also, $(d_{1},d_{2})\in
E(D)$ and $d_{1}=y\in\big{(}\mathcal{C}_{3}^{\prime}\setminus
L_{1}(\mathcal{C}_{3}^{\prime})\big{)}\cap V^{+}$, since
$N_{D}^{+}[d_{1}]=\\{d_{1},d_{2}\\}\subset\mathcal{C}_{3}^{\prime}$. Hence,
$\mathcal{C}_{3}^{\prime}$ is a strong vertex cover of $D$.  $\Box$

###### Theorem 5.13

Let $D=(G,\mathcal{O},w)$ be a connected weighted oriented graph, with ${\rm
girth}(G)\geqslant 5$. Hence, $I(D)$ is unmixed if and only if $D$ satisfies
one of the following properties:

  1. (a)

$G\in\\{K_{1},C_{7},Q_{13},P_{13},P_{14}\\}$ and the vertices of $V^{+}$ are
sinks.

  2. (b)

$G=P_{10}$, furthermore if $y$ is not a sink in $V^{+}$, then $y=d_{1}$ with
$N_{D}^{+}(y)=\\{g_{1},b_{2}\\}$ or $y=d_{2}$ with
$N_{D}^{+}(y)=\\{g_{2},b_{1}\\}$.

  3. (c)

Each vertex is in exactly one simplex of $G$ or in exactly one basic $5$-cycle
of $G$. Furthermore, each simplex of $D$ has not a generating $\star$-semi-
forest and each basic $5$-cycle of $D$ has the $\star$-property.

Proof. $\Rightarrow)$ By (3) in Theorem 2.12 and Remark 2.17, $G$ is well-
covered. By Theorem 2.30, $G\in\\{K_{1},C_{7},P_{10},P_{13},P_{14},Q_{13}\\}$
or $\\{V(H)\mid H\in S_{G}\cup C_{G}\\}$ is a partition of $V(G)$. If
$\\{V(H)\mid H\in S_{G}\cup C_{G}\\}$ is a partition of $V(G)$, then $G$ is an
$SCQ$ graph with $Q_{G}=\emptyset$. Hence, by Theorem 4.8, $D$ satisfies (c).
Now, if $G=P_{10}$, then by Proposition 5.12, $D$ satisfies (b). Furthermore,
if $G\in\\{C_{7},Q_{13},P_{13},P_{14}\\}$, then by Proposition 5.9, $D$
satisfies (a). Finally, if $G=K_{1}$, then by Remark 2.3, $V^{+}=\emptyset$.

$\Leftarrow)$ If $D$ satisfies (b), then by Proposition 5.12, $I(D)$ is
unmixed. Now, if $D$ satisfies (c), then $G$ is an $SCQ$ graph with
$Q_{G}=\emptyset$. Consequently, by Theorem 4.8, $I(D)$ is unmixed. Finally,
if $D$ satisfies (a), then by Theorem 2.30, $G$ is well-covered. Therefore, by
Corollary 5.2, $I(D)$ is unmixed.  $\Box$

###### Remark 5.14

A graph is well-covered if and only if each connected component is well-
covered. Hence, when $D$ is no connected in Theorem 5.10 (resp. 5.13), $I(D)$
is unmixed if and only if each connected component of $D$ satisfies (a) or (b)
(resp. (a), (b) or (c)).

##  6 Examples

###### Example 6.1

Let $D_{1}$ be the following weighted oriented graph.

$v_{\small 1}$$1$$w_{\small 1}$$2$$2$$2$$1$$2$$2$$2$$1$$1$$2$$2$$2$$v_{\small
2}$$2$$2$$2$$w_{\small 2}$$2$$1$$2$$1$$2$$2$$2$$2$$1$$2$$w_{\small
5}$$1$$1$$v_{\small 3}$$2$$v_{\small 4}$$2$$2$$2$$w_{\small
4}$$2$$2$$v_{\small 5}$$2$$2$$\mathbf{v_{\small
1}}$$1$$\mathbf{T_{1}}$$w_{\small
1}$$2$$2$$2$$1$$2$$2$$2$$1$$1$$2$$2$$2$$\mathbf{B_{1}}$$\mathbf{v_{\small
2}}$$2$$2$$2$$w_{\small 2}=w_{\small
3}$$2$$1$$2$$1$$2$$\mathbf{T_{2}}$$2$$2$$2$$1$$2$$w_{\small
5}$$1$$1$$\mathbf{v_{\small 3}}$$2$$\mathbf{T_{3}}$$\mathbf{v_{\small
4}}$$2$$2$$2$$w_{\small 4}$$2$$2$$\mathbf{v_{\small
5}}$$2$$2$$\mathbf{T_{4}}$$\mathbf{T_{5}}$

We take the weighted oriented subgraph $K$ of $D_{1}$ induced by
$V(D_{1})\setminus\\{w_{1},w_{2},w_{4},w_{5}\\}$. In the following figure,
$T_{1},\ldots,T_{5}$ are the ROT’s and $B_{1}$ is the unicycle oriented
subgraph such that the parent of $T_{i}$ is $v_{i}$ and
$W^{T_{i}}=\\{w_{i}\\}$ for $i=1,\ldots,5$. Furthermore, $H=\cup_{i=1}^{5}\
T_{i}\ \cup B_{1}$ is a $\star$-semi-forest with $W_{1}^{H}=\\{w_{1},w_{5}\\}$
$W_{2}^{H}=\\{w_{2},w_{4}\\}$ and $V(H)=V(K)$. Therefore, $H$ is a generating
$\star$-semi-forest of $K$.

###### Example 6.2

Let $D_{2}$ be an oriented weighted graph such as the Figure. Let
$K^{4}=H=D_{2}[x_{1},x_{2},x_{3}]$ be an induced weighted oriented subgraph of
$D_{2}$ and $H$ a generating $\star$-semi-forest of $K^{4}$ with
$\tilde{H}=H=\\{x_{1},x_{2},x_{3}\\}\subseteq V^{+}$ and
$W_{1}=W_{2}=\emptyset$. Then, by Theorem 3.10, there is a strong vertex cover
$\mathcal{C}$ of $D_{2}$, such that $V(K^{4})\subseteq\mathcal{C}$. For this
purpose, first we take a minimal vertex cover $\mathcal{C}_{i}$ of $D$ and
define $\mathcal{C}_{i}^{\prime}=(\mathcal{C}_{i}\setminus W_{1})\cup
N_{D}(W_{1})\cup N_{D}^{+}(W_{2}\cup\tilde{H})$. Finally, we use the algorithm
in the proof of the Proposition 3.1.

In this example, $\mathcal{C}_{i}^{\prime}=\mathcal{C}_{i}\cup
N_{D}^{+}(\tilde{H})=\mathcal{C}_{i}\cup
N_{D}^{+}(\\{x_{1},x_{2},x_{3}\\})=\mathcal{C}_{i}\cup\\{x_{1},x_{2},x_{3},y_{1},y_{2}\\}$.

$z_{\tiny 1}$$z_{\tiny 2}$$z_{\tiny 3}$$y_{\tiny 1}$$x_{\tiny
1}$$w>1$$y_{\tiny 2}$$x_{\tiny 2}$$w>1$$y_{\tiny 3}$$x_{\tiny 3}$$w>1$$H$

  * •

If we take $\mathcal{C}_{1}=\\{x_{1},x_{2},y_{1},y_{2},y_{3}\\}$ as a minimal
vertex cover of $D_{2}$, then
$\mathcal{C}_{1}^{\prime}=\\{x_{1},x_{2},x_{3},y_{1},y_{2},y_{3}\\}$ and
$L_{3}(\mathcal{C}_{1}^{\prime})\setminus N_{D}^{+}(\tilde{H})=\emptyset$.
Thus, by Proposition 3.1,
$\mathcal{C}=\mathcal{C}_{1}^{\prime}=\\{x_{1},x_{2},x_{3},y_{1},y_{2},y_{3}\\}$
is a strong vertex cover such that $V(K^{4})\subseteq\mathcal{C}$ and it is no
minimal. Furthermore, in this case it is enough to know the orientation of
$E(K^{4})$, since $L_{3}(\mathcal{C})=\\{x_{1},x_{2},x_{3}\\}$ and
$N_{D_{2}}(x_{i})\subseteq\mathcal{C}$ for $i=1,2,3$.

  * •

Now, if we take $\mathcal{C}_{2}=\\{x_{1},x_{2},x_{3},z_{1},z_{2},z_{3}\\}$ as
a minimal vertex cover of $D_{2}$, then
$\mathcal{C}_{2}^{\prime}=V(D_{2})\setminus\\{y_{3}\\}$ and
$L_{3}(\mathcal{C}_{2}^{\prime})\setminus
N_{D}^{+}(\tilde{H})=\\{z_{1},z_{2}\\}$. Thus, by the algorithm in the proof
of Proposition 3.1,
$\mathcal{C}^{\prime}=\mathcal{C}_{4}^{\prime}=\\{x_{1},x_{2},x_{3},y_{1},y_{2},z_{3}\\}$
is a strong vertex cover such that $V(K^{4})\subseteq\mathcal{C}^{\prime}$.

Since $\mathcal{C}$ and $\mathcal{C}^{\prime}$ are no minimal with
$L_{3}(\mathcal{C})=\\{x_{1},x_{2},x_{3}\\}$ and
$L_{3}(\mathcal{C}^{\prime})=\\{x_{1},x_{2}\\}$, then $D_{2}$ is mixed.
Furthermore, $V(D_{2})$ has a partition in complete graphs:
$K^{i}=D_{2}[y_{i},z_{i}]$ for $i=1,2,3$ and $K^{4}=D_{2}[x_{1},x_{2},x_{3}]$
.

###### Example 6.3

Let $D_{3}=(G,\mathcal{O},w)$ be the following oriented graph. Hence,

$w>1$$b^{\prime}$$d_{\small 1}^{\prime}$$b$$d_{\small
2}^{\prime}$$1$$c$$d_{\small 1}$$w>1$$w>1$$a$$d_{\small
2}$$w>1$$a^{\prime}$$1$

  * •

$G$ has no $3$\- and $4$-cycles.

  * •

The basic $5$-cycle $C=(a^{\prime},a,b,b^{\prime},c,a^{\prime})$ satisfies the
$\star$-property.

  * •

$D_{3}[\\{d_{1},d_{1}^{\prime}\\}]$ has not a generating $\star$-semi-forest.
But $T_{1}=\tilde{e}=(d_{2},d_{2}^{\prime})$ is a ROT with parent
$v_{1}=d_{2}$ and $W=W_{2}=\\{w_{1}=a\\}$. Furthermore, $H=T_{1}$ is a
$\star$-semi-forest with $V(H)=V(K)$, where
$K:=D_{3}[\\{d_{2},d_{2}^{\prime}\\}]$. Therefore, $H$ is a generating
$\star$-semi-forest of $K$ and $I(D_{3})$ is mixed.

###### Example 6.4

Let $D_{4}=(G,\mathcal{O},w)$ be the following oriented weighted graph. Hence,

$w>1$$d$$1$$1$$1$$1$$1$$1$$1$$1$$1$

  * •

$G=P_{10}$, then by Theorem 2.30 and Remark 2.17, $G$ is well-covered and
$I(G)$ is unmixed.

  * •

$d$ is not a sink and $d\in V^{+}$.

  * •

By Proposition 5.12, $I(D_{4})$ is unmixed.

## References

  * [1] C. Carvalho, V. G. Neumann and H. H. López. Projective nested cartesian codes. Bull. Braz. Math. Soc. (N.S.), 48, (2017), no. 2, 283–-302.
  * [2] I. D. Castrillón, R. Cruz, and E. Reyes. On well-covered, vertex decomposable and Cohen–Macaulay graphs. Electron. J. Combin., 23, (2016), no. 2, Paper 2.39, 17pp.
  * [3] I. Castrillón and E. Reyes, Pure vertex decomposable simplicial complex associated to graphs whose $5$-cycles are chorded, Bol. Soc. Mat. Mex. 23 (2017), 399–412.
  * [4] R. Diestel, Graph Theory, Second Edition, Graduate Texts in Mathematics, 173, Springer-Verlag, New York, 2000.
  * [5] A. Finbow, B. Hartnell and R. J. Nowakowski, A characterization of well-covered graphs of girth 5 or greater, J. of Combinatorial Theory B 57 (1993) 44-68.
  * [6] A. Finbow, B. Hartnell and R. J. Nowakowski, A characterization of well-covered graphs that contain neither 4- nor 5-cycles, J. Graph Theory 18 (1994) 713-721.
  * [7] P. Gimenez, J. Martínez-Bernal, A. Simis, R. H. Villarreal, and C. E. Vivares, Symbolic powers of monomial ideals and Cohen–Macaulay vertex-weighted digraphs, Singularities, Algebraic Geometry, Commutative Algebra, and Related Topics, Springer, Cham, (2018), 491–510.
  * [8] H. T. Há, K. N. Lin, S. Morey, E. Reyes and R. H. Villarreal, Edge ideals of oriented graphs, Internat. J. Algebra Comput., 29 (2019), no. 3, 535–559.
  * [9] J. Martínez-Bernal, Y. Pitones and R. H. Villarreal, Minimum distance functions of graded ideals and Reed-Muller-type codes. J. Pure Appl. Algebra 221 (2017), no. 2, 251–-275.
  * [10] Y. Pitones, E. Reyes and J. Toledo, Monomial ideals of weighted oriented graphs, Electronic. J. Combin., 26 (2019), no. 3, Paper 3.44, 18 pp.
  * [11] Y. Pitones, E. Reyes and R. H. Villarreal, Unmixed and Cohen–Macaulay weighted oriented König graphs, (2019), preprint, arxiv:1909.13295.
  * [12] E. Prisner, J. Topp and P. D. Vestergaard, Well Covered Simplicial, Chordal, and Circular Arc Graphs, J. Graph Theory, 21 (1996) 113-119.
  * [13] B. Randerath and L. Volkmann, A characterization of well-covered block-cactus graphs, Australas. J. Combin, 9 (1994) 307–-314.
  * [14] R. H. Villarreal, Monomial Algebras, Second Edition, Monographs ans Research Notes in Mathematics, Chapman and Hall/CRC, 2015.
  * [15] G. Zhu, L. Xu, H. Wang and Z. Tang, Projective dimensions and regularity of edge ideal of some weighted oriented graphs, Rocky Mountain J. Math., 49 (2019), no. 4, 1391-–1406.