📂Graph Theory

Distance, Neighborhood, Diameter, Perimeter in a Graph

Definition

In the graph $G$, the set of paths whose origin is $v \in V(G)$ and destination is $w \in V(G)$ is represented as $P(v,w)$, and let’s denote the set of cycles that include $v \in V(G)$ as $C(v)$. Also, let’s present the length of a walk $x$ as $l(x)$.

1. The distance $d$ between two vertices $v,w \in V(G)$ is defined as the smallest value among the lengths of paths where $v$ is the origin and $w$ is the destination. In other words, $$ d(v,w) := \min_{v,w \in V(G)} \left\{ l(x) : x \in P(v,w) \right\} $$
2. The set of vertices $N^{i} (v) \subset V(G)$ whose distance from vertex $v \in V(G)$ is exactly $i$ is called a $i$-neighborhood.
3. The diameter $\text{diam}$ of graph $G$ is defined as the largest distance among all pairs of vertices. In other words, $$ \text{diam} (G) := \sup_{v,w \in V(G)} \left\{ d(v,w) : v \ne w \right\} $$
4. The girth $\text{girth}$ of graph $G$ is defined as the smallest length among all cycles. In other words, $$ \text{girth}(G) := \min_{v \in V(G)} \left\{ l(x) : x \in C(v) \right\} $$

Description

The distance between vertices in a graph is also called a Geodesic Distance. This naming is considered valid because, unlike the Euclidean distance, it represents the actual number of steps taken to reach from one vertex to another. For instance, in the following graph, $d(v,w)$ cannot be less than $2$ in any case, and equals $d(v,w) = 2$.

The definition of diameter might seem odd at first glance. By analogy, consider a circle $x^2 + y^2 = r^2$. When any two points on the circle are chosen, the furthest distance between them occurs when the points are symmetrically positioned across the center of the circle. Obviously, this distance is $2r$, which is what we refer to as the diameter of the circle. For instance, the diameter of the graph above is $2$.

Girth, conceptually, refers to the size of the smallest cycle in a graph. Though not explicitly mentioned, if a graph does not contain any cycles, its girth is considered to be infinite. Also, it’s self-evident that the minimum value of girth in any graph cannot be less than $3$. For example, as shown in the diagram below, even though there are several cycles, the length of the smallest cycle is $3$, so the girth is $3$.