2
$\begingroup$

For an undirected graph, we know that nodes are adjacent to each other if there is a link that connects them. What about adjacency for directed graphs? Is it based on:

  • outgoing links: node $n$ is adjacent to node $i$ if there is a link coming out from node $n$ to node $i$
  • ingoing links: node $n$ is adjacent to node $i$ if there is a link coming out from node $i$ to node $n$
  • either: mixed of both above options (like adjacency in undirected graphs)

Any references would be appreciated.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

It depends on the author.

Some authors use the outgoing link definition, e.g. this one: In a directed graph vertex v is adjacent to u, if there is an edge leaving v and coming to u.

Other authors use the ingoing link definition, e.g. this one:insert a 1 if vertex j is adjacent to vertex i (that is, if there is an arc from vertex i to vertex j).

There are even authors using "adjacent" as a symmetric relation, e.g.

this: We say that two vertices i and j of a directed graph are joined or adjacent if there is an edge from i to j or from j and i. and

that: if a path of length 1 exists from one vertex to another (ie. the two vertices are adjacent).

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ In addition, I have seen "adjacent to" and "adjacent from" for the two cases. $\endgroup$
    – Brendan McKay
    Commented May 2, 2019 at 12:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .