Definition:Adjacent (Graph Theory)
Contents |
Definition
Undirected Graph
Let $G = \left({V, E}\right)$ be an undirected graph.
Two vertices $u, v \in V$ of $G$ are adjacent or neighboring if there exists an edge $e = \left\{{u, v}\right\} \in E$ of $G$ to which they are both incident.
Two edges $e_1, e_2 \in E$ of $G$ adjacent or neighboring if there exists a vertex $v \in V$ to which they are both incident.
Otherwise they are non-adjacent.
Digraph
Let $G = \left({V, E}\right)$ be a digraph.
Two vertices $u, v \in V$ of $G$ are adjacent or neighboring if there exists an arc $e = \left({u, v}\right) \in E$ of $G$ to which they are both incident.
Otherwise they are non-adjacent.
Planar Graph
Let $G = \left({V, E}\right)$ be a planar graph.
Two faces are adjacent if they are both incident to the same edge (or edges).
Note that faces which are both incident to the same vertex are not considered adjacent unless they are also both incident to the same edge.
Sources
- Gary Chartrand: Introductory Graph Theory (1977): $\S 1.3$
