Degree matrix
In graph theory, the degree matrix (also known as the valency matrix) of a graph G = (V, E) with vertex set V = \{v_1, \dots, v_n\} is a diagonal matrix D \in \mathbb{R}^{n \times n} where the diagonal entry D_{ii} equals the degree d(v_i) of vertex v_i, and all off-diagonal entries are zero.[1] For an undirected simple graph, the degree d(v_i) is the number of edges incident to v_i; in weighted graphs, it is the sum of the weights of edges adjacent to v_i.[2] For directed graphs, variants use either in-degrees or out-degrees on the diagonal, depending on the context.
The degree matrix plays a central role in spectral graph theory and matrix representations of graphs, particularly in the construction of the graph Laplacian matrix L = D - A, where A is the adjacency matrix of G.[2] This Laplacian is symmetric and positive semi-definite for undirected graphs, with eigenvalues that are real and non-negative, providing insights into graph connectivity, clustering, and spectral properties.[2] In weighted graphs, the formulation extends to L = D - W, where W is the weight matrix, and the quadratic form x^T L x = \frac{1}{2} \sum_{i,j} w_{ij} (x_i - x_j)^2 underscores its semi-definiteness.[2]
Key properties of the degree matrix include its diagonal structure, which simplifies computations in graph algorithms, and its dependence on vertex ordering, typically aligned with the rows and columns of the adjacency matrix.[1] It is also integral to the incidence matrix formulation of the Laplacian, where L = B B^T for the unoriented incidence matrix B, linking combinatorial and algebraic graph properties.[2]
Fundamentals
Definition
In graph theory, an undirected graph G = (V, E) consists of a finite set V of vertices and a set E of unordered pairs \{i, j\} with i, j \in V (possibly i = j) representing edges between vertices. The degree of a vertex i \in V, denoted d_i, is the number of edges incident to it. In simple graphs without loops or multiple edges, this equals the number of distinct neighbors of i. In general undirected graphs allowing loops and multiple edges, the degree is given by d_i = \sum_{j \neq i} m_{ij} + 2 m_{ii}, where m_{ij} is the multiplicity (number) of edges between distinct vertices i and j, and m_{ii} is the number of loops at i; each loop contributes 2 to the degree, while each multiple edge contributes once to each endpoint. In weighted graphs, the degree d_i is the sum of the weights of edges incident to v_i, with a loop's weight contributing twice.[3]
The degree matrix D of G with |V| = n is the n \times n diagonal matrix where the diagonal entry D_{ii} = d_i for each i = 1, \dots, n, and all off-diagonal entries are zero.[4] Formally,
D = \operatorname{diag}(d_1, d_2, \dots, d_n),
where the d_i are defined as above. This matrix encodes the degrees in a compact form, distinct from the adjacency matrix which captures direct connections between vertices.
Notation and prerequisites
In graph theory, the degree matrix is commonly introduced using undirected simple graphs, which consist of a finite nonempty set of vertices V = \{v_1, v_2, \dots, v_n\} and a set of edges E \subseteq \binom{V}{2}, where each edge connects exactly two distinct vertices without direction. These graphs assume no self-loops (edges from a vertex to itself) or multiple edges between the same pair of vertices, ensuring a straightforward counting of connections per vertex. However, the concept extends to multigraphs with loops and multiple edges, as well as weighted and directed graphs.[5] While the degree matrix is primarily defined for undirected graphs, directed graphs introduce asymmetries via in-degrees and out-degrees, typically requiring separate matrices rather than a single degree matrix.[5]
Standard notation denotes the degree matrix of a graph G as D(G) or simply D, represented in boldface as D to indicate its matrix form, with diagonal entries given by lowercase d_i, the degree of vertex v_i.[1] Formally, D is the n \times n diagonal matrix \diag(d_1, d_2, \dots, d_n), where each d_i counts the number of edges incident to v_i.[1] In the context of weighted graphs, degrees are computed as the sum of weights on incident edges, extending the diagonal entries accordingly while maintaining the diagonal structure.[6]
The concept of the degree matrix originated in early 20th-century graph theory as part of efforts to represent graph properties via matrices, with formalization in spectral graph theory during the 1950s and 1960s through analyses of adjacency and Laplacian matrices.[7]
Construction
From graph degrees
The degree matrix D of an undirected graph G = (V, E) with vertex set V = \{1, 2, \dots, n\} is constructed by first determining the degree d_i of each vertex i \in V, defined as the number of edges in E incident to i. The matrix D is then the n \times n diagonal matrix D = \operatorname{diag}(d_1, d_2, \dots, d_n), where all off-diagonal entries are zero.[8]
The construction proceeds in the following steps: (1) For each vertex i, compute d_i by counting the edges connected to i; (2) assign d_i to the (i,i)-th entry of D; (3) set all off-diagonal entries to 0. This direct method ensures D captures the local connectivity of each vertex without relying on other matrix representations.[9]
A pseudocode implementation for building D from the edge set E (assuming 1-based indexing and an undirected simple graph) is:
Initialize degrees array of size n to 0
For each edge {u, v} in E:
degrees[u] ← degrees[u] + 1
degrees[v] ← degrees[v] + 1
Initialize n × n matrix D to the [zero matrix](/page/Zero_matrix)
For i = 1 to n:
D[i, i] ← degrees[i]
Initialize degrees array of size n to 0
For each edge {u, v} in E:
degrees[u] ← degrees[u] + 1
degrees[v] ← degrees[v] + 1
Initialize n × n matrix D to the [zero matrix](/page/Zero_matrix)
For i = 1 to n:
D[i, i] ← degrees[i]
Equivalently, the diagonal entries can be expressed as D_{i,i} = \sum_{j \neq i} \mathbf{1}_{\{i,j\} \in E} for i = 1 to n, where \mathbf{1} is the indicator function.[8]
Isolated vertices, which have no incident edges, yield d_i = 0 and thus a zero entry on the corresponding diagonal position in D, preserving the matrix's diagonal structure and indicating no contribution to the graph's connectivity from that vertex.[10]
For sparse graph representations (e.g., adjacency lists or edge lists), computing the degrees requires scanning all edges once, incrementing counts for each endpoint, which takes O(|E|) time overall since \sum_i d_i = 2|E|; constructing the diagonal matrix then adds O(n) time.[9]
Relation to adjacency matrix
The degree matrix D of an undirected graph can be constructed directly from its adjacency matrix A by taking the diagonal matrix whose entries are the row sums of A.[11] Specifically, for a graph with n vertices, the i-th diagonal entry D_{ii} equals the degree d_i of vertex i, given by d_i = \sum_{j=1}^n A_{ij}.[12] This relation holds because the adjacency matrix A has entries A_{ij} = 1 if vertices i and j are adjacent and $0 otherwise, so the row sum counts the number of neighbors of vertex i. In matrix form, this is expressed as D = \operatorname{diag}(A \mathbf{1}), where \mathbf{1} is the n \times 1 all-ones vector.[12]
For weighted undirected graphs, the adjacency matrix A contains the weights w_{ij} of edges between vertices i and j (with A_{ij} = 0 if no edge exists), and the degree d_i is defined as the sum of the weights of all edges incident to vertex i, so d_i = \sum_{j=1}^n A_{ij}.[13] Thus, the degree matrix D is again the diagonal matrix with these weighted degrees on the diagonal, D = \operatorname{diag}(A \mathbf{1}).[14] This generalization preserves the structural connection between the adjacency matrix and vertex degrees while accounting for edge weights.
Examples
Path graph
A path graph P_n consists of n vertices labeled $1 through n, connected by edges between consecutive vertices, specifically the edge set E = \{\{i, i+1\} \mid 1 \leq i < n\}.[15]
In P_n, the two endpoint vertices (1 and n) each have degree 1, while the n-2 internal vertices (2 through n-1) each have degree 2.[4]
The degree matrix D of P_n is the n \times n diagonal matrix whose diagonal entries d_{ii} equal the degree of vertex i, with all off-diagonal entries zero.[16]
For the small path graph P_3, with vertices 1--2--3, the degrees are 1, 2, and 1, yielding
D = \begin{pmatrix}
1 & 0 & 0 \\
0 & 2 & 0 \\
0 & 0 & 1
\end{pmatrix}.
This structure reveals a clear diagonal pattern: 1's at the ends corresponding to the low-degree endpoints, and 2's in the middle for the higher-degree internal vertices.[16]
Cycle graph
A cycle graph C_n is an undirected graph consisting of n vertices labeled 1 through n, connected by edges between consecutive vertices \{i, i+1\} for i = 1 to n-1, and an additional edge between vertices n and 1, forming a closed loop.[4][15]
In C_n, every vertex has exactly two incident edges, resulting in a degree of 2 for all vertices; thus, C_n is a 2-regular graph.[4]
The degree matrix D for C_n is therefore the n \times n diagonal matrix with 2 on each diagonal entry, which can be expressed as D = 2I_n, where I_n is the n \times n identity matrix.[4][15]
This uniform structure contrasts with the degree matrix of a path graph, where endpoint degrees are 1 and interior degrees are 2; closing the path into a cycle equalizes all degrees to 2, yielding a simple scalar multiple of the identity matrix.[4]
Properties
Basic characteristics
The degree matrix D of an undirected graph G = (V, E) with vertex set V = \{v_1, \dots, v_n\} is defined as the n \times n diagonal matrix D = \operatorname{diag}(d(v_1), \dots, d(v_n)), where d(v_i) denotes the degree of vertex v_i.[12]
As a diagonal matrix, D is inherently symmetric, since all off-diagonal entries are zero.[12] Moreover, with non-negative diagonal entries (as degrees are non-negative integers), D is positive semi-definite, meaning the quadratic form \mathbf{x}^T D \mathbf{x} \geq 0 for all real vectors \mathbf{x} \in \mathbb{R}^n.[17]
The trace of D, given by \operatorname{tr}(D) = \sum_{i=1}^n d(v_i), equals twice the number of edges in G, i.e., \operatorname{tr}(D) = 2 |E|, by the handshaking lemma.[12][18] This relation underscores the matrix's connection to global graph structure. Due to its diagonal form, D has exactly n nonzero entries in an n \times n matrix, making it highly sparse and computationally efficient for storage and operations in sparse matrix representations.[12]
For a disconnected graph with multiple connected components, if the vertices are reordered to group those within each component, D takes a block-diagonal form, where each block corresponds to the degree matrix of an individual component. This structure reflects the independence of degree computations across components.[19]
Eigenvalues and trace
The degree matrix D of a graph is a diagonal matrix, and thus its eigenvalues are precisely the diagonal entries, which are the vertex degrees d_1, d_2, \dots, d_n. Each eigenvalue d_i has algebraic multiplicity one, assuming all degrees are distinct, though multiplicities increase if degrees repeat.
The corresponding eigenvectors are the standard basis vectors e_i of \mathbb{R}^n, where the i-th basis vector satisfies D e_i = d_i e_i, reflecting the matrix's diagonal structure. This simplicity arises directly from the properties of diagonal matrices in linear algebra, applied within the graph-theoretic context.
The trace of D, denoted \operatorname{tr}(D), equals the sum of its eigenvalues, which is \sum_{i=1}^n d_i. For an undirected graph, this sum is twice the number of edges, $2|E|, by the handshaking lemma.[18]
The determinant of D is the product of its eigenvalues, given by \det(D) = \prod_{i=1}^n d_i. Thus, D is singular if and only if the graph has at least one isolated vertex, where some d_i = 0.
Applications
Spectral graph theory
In spectral graph theory, the degree matrix D plays a crucial role in normalizing graph operators to account for varying vertex degrees, enabling the analysis of eigenvalues that reveal structural properties such as connectivity and expansion. One key application is in the construction of the normalized Laplacian \mathcal{L} = I - D^{-1/2} A D^{-1/2}, where A is the adjacency matrix and D^{-1/2} scales the rows and columns by the inverse square roots of the degrees; this normalization ensures that the eigenvalues of \mathcal{L} lie between 0 and 2, providing bounds on graph cuts and mixing times independent of degree irregularities.[7] This formulation, introduced by Fan Chung, facilitates the study of expander graphs and Cheeger's inequality, linking the second smallest eigenvalue to the graph's conductance.[7]
The degree matrix also features prominently in the spectral analysis of random walks on graphs, where the transition matrix P = D^{-1} A defines the probabilities of moving from one vertex to its neighbors, with D normalizing for the fact that higher-degree vertices have more outgoing edges and thus lower per-edge transition probabilities. The eigenvalues of P determine the walk's convergence rate to the stationary distribution, which is proportional to the degrees (i.e., the entries of D); this spectral gap, influenced by D's diagonal values, quantifies how quickly the walk mixes, with applications to sampling and approximation algorithms.[7] In irregular graphs, D's role ensures that the random walk behaves equitably across vertices of different degrees, avoiding bias toward high-degree nodes in the spectral decomposition.
In spectral partitioning and graph clustering, the degree matrix influences the eigenvectors used to identify balanced cuts, as seen in methods that leverage the normalized Laplacian to embed vertices into a lower-dimensional space where clustering algorithms like k-means can be applied. The degrees in D affect the weighting of edges in the cut objective, promoting partitions that minimize the normalized cut value, which balances the number of edges crossing the partition against the volumes (sum of degrees) of the clusters.[20] This approach, building on earlier work, ensures robustness to degree heterogeneity by scaling the similarity matrix appropriately.
Chung's work further expands the normalized Laplacian framework with variants such as the random-walk normalized Laplacian \mathcal{L}_{rw} = I - D^{-1} A and the signless version, both incorporating D to adapt spectral properties for directed or weighted graphs; these allow finer control over eigenvalue interpretations, particularly for directed walks where D's out-degrees normalize asymmetries.[7] For instance, the eigenvalues of \mathcal{L}_{rw} directly relate to the relaxation times of Markov chains, highlighting D's essential role in bridging combinatorial graph properties with probabilistic behaviors.[7]
Graph Laplacians
The graph Laplacian matrix is a fundamental operator in spectral graph theory, constructed using the degree matrix D and the adjacency matrix A. The unnormalized Laplacian is defined as L = D - A, where D is the diagonal matrix with the vertex degrees on its main diagonal, providing the necessary degree-based subtraction that ensures L captures the graph's connectivity structure.[7] This formulation highlights D's central role in balancing the adjacency contributions, transforming the simple edge connections in A into a differential operator analogous to the continuous Laplacian.[21]
A key property arising from D's construction is that the rows of L sum to zero, as each row i of D - A has d_i on the diagonal minus the sum of the i-th row of A, which equals d_i, yielding zero overall; this makes L singular with a kernel including the all-ones vector.[7] The eigenvalues of L are real and non-negative, with the smallest eigenvalue being zero (with multiplicity equal to the number of connected components), and the largest eigenvalue bounded above by twice the maximum degree \Delta = \max d_i, reflecting D's influence in scaling the spectrum relative to vertex degrees.[7] These spectral bounds underscore D's contribution to confining the operator's action within degree-dependent limits.
The quadratic form associated with L further illustrates D's enabling role: for a vector x \in \mathbb{R}^n,
x^T L x = \sum_{(i,j) \in E} (x_i - x_j)^2,
where the sum is over all edges, and this equality derives from expanding x^T (D - A) x = \sum_i d_i x_i^2 - 2 \sum_{(i,j) \in E} x_i x_j, which simplifies to the edge-difference sum; here, D weights the self-terms to match the degree-incidence structure.[7] This form measures the smoothness of x over the graph, with D's diagonal entries ensuring the quadratic penalizes variations proportionally to local connectivity.
In addition to the unnormalized form, normalized Laplacians incorporate D more explicitly to handle irregular degree distributions. The symmetric normalized Laplacian is \mathcal{L} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2}, where D^{-1/2} scales rows and columns by the inverse square roots of degrees, making \mathcal{L} suitable for non-regular graphs by degree-normalizing the operator.[7] The combinatorial Laplacian L emphasizes raw edge counts via D - A, while the normalized variant \mathcal{L} or the random-walk form D^{-1} L adjusts for degree heterogeneity, with D's inverse highlighting its pivotal diagonal role in achieving scale-invariance across vertices.[7] Both forms leverage D to derive positive semidefiniteness and bounded spectra (0 to 2 for \mathcal{L}), facilitating applications in partitioning and diffusion processes.[7]