
## 3.2 Graph-Theoretic Classification Of Gso-Structures

We will classify the relational models of T*spec* in a more well-understood combinatorial setting. But before that we will recall some definitions.

Definition 2. A directed graph G is a pair (V,E), where V is the set of vertices and E ⊆ V ×V \ {(v,v) ∈ V ×V} *is the set of edges.*

- *The transitive closure of G is a graph G*+ = (V,E
+) such that for all v,*w in V there* is an edge (v,w) in E+ *if and only if there is a nonempty path from v to w in G.*
- *The graph G is called a* transitive graph *if we have E* = E
+ \ {(v,v) ∈ E
+}*. In other* words, G is its own transitive-closure taken away all the self-loops.

- *We let* C(G) = (V,C(E)) *denote the* comparability graph *of G, i.e.,*
C(E) = {(u,v) : (u,v) ∈ E}.

- *We let* IC(G) = (V,IC(E)) *denote the* incomparability graph *of G, i.e.,*
IC(E) = {(u,v) : (u,v) 6∈ E}.

- *We let* G = (V,E) *denote the* complement graph of G, i.e.,
E = {(u,v) ∈V ×V : u 6= v ∧ (u,v) 6∈ E}.

In other words, we exclude the self-loops.

- *Given a directed graph H* = (V,E
′), we write G ⊆ *H if E* ⊆ E
′. We write G−*H to* denote the graph (V,E \E
′). And we write G ∪*H to denote the graph* (V,E ∪E
′).

In this paper, we will treat undirected graphs (or graphs) as a special case of directed graph, where the edge relations are symmetric. This explains why we defined C(G) and IC(G) as direct graphs. Also note that whenever we call something a graph or a directed graph, we already mean that it does not contain any self-loop.

Definition 3. Let Mspec denote the class of all possible models for Tspec. Then any model M ∈ Muniv *can be uniquely determined from the following three graphs:*
1. The graph G1 = (EO,E1) *is a* acyclic transitive graph.

2. The graph G2 = (EO,E2) *is a transitive graph satisfying the following two conditions:*
(a) G2 = G1 ∪G3, where G3 ⊆ IC(G1).

(b) the graph G2 *does not contain a triangle that has any of these two forms:*

![0_image_0.png](0_image_0.png)

where the solid edges are edges of G1 and the dashed edges are edges of G3.

16