Antipath in regard to a graph of transitive closure

19 Views Asked by At

I'm in the process of reading a paper that deals with graphs and their cliques. In the paper it uses graphs $G=(X,\Gamma)$ and their graph of transitive closure $G_t$. It then states:

It is not worth while to distinguish between the graph of transitive closure $G_t$ and the partially ordered set $(X,>)$. Therefore in the graph $G_t$ we will also consider antipaths.

This makes some sense to me, but despite by best efforts I cannot find what an antipath is.

So, what is an antipath in this context?

1

There are 1 best solutions below

0
On BEST ANSWER

According to Chudnovsky, an antipath is:

An antipath $Q$ in G is a sequence of distinct vertices $v_0- . . . -v_k$ where $v_i$ is non-adjacent to $v_j$ if and only if $|i − j| = 1$, and we call $k$ the length of the antipath

According to Klimošová, Stein, an antipath is:

...an oriented path (cycle, tree) where every vertex has either out-degree 0 or in-degree 0.