indegrees

Indegrees refer to the in-degree of a vertex in a directed graph. The in-degree of a vertex v is the number of edges that terminate at v, i.e., the number of incoming edges to v. It is usually denoted indeg(v) or din(v), and is often considered alongside the out-degree, which counts edges leaving v. In a directed graph, a vertex’s in-degree and out-degree together describe its total degree, though they measure different directions of connection.

In any finite directed graph, the sum of all in-degrees equals the number of edges. This mirrors the sum of all out-degrees. The possible range of in-degree depends on the graph’s conventions: in a simple directed graph (no loops, no multiple edges), the in-degree of a vertex is between 0 and |V|−1. If loops are allowed, a loop at a vertex contributes to both its in-degree and its out-degree, and the range can extend accordingly.

Computation of in-degree can be done in several ways. With an adjacency matrix A, the in-degree of vertex i is the sum of the entries in column i (i.e., indeg(i) = sum_j A[j,i]). With an adjacency list, it is the count of edges that list i as their destination. Efficiently, you can compute in-degrees for all vertices by scanning every edge once and incrementing the corresponding destination vertex’s counter.

Example: consider a directed graph with vertices {A, B, C} and edges A→B, A→C, B→C. The in-degrees are indeg(A)=0, indeg(B)=1, indeg(C)=2, and the total indegree sum is 3, equal to the number of edges.

Applications include network analysis, topological sorting, and measures of influence or popularity in directed networks; in-degree centrality is a common basic metric.