Degree matrix
{{Short description|Type of matrix in algebraic graph theory}}
In the mathematical field of algebraic graph theory, the degree matrix of an undirected graph is a diagonal matrix which contains information about the degree of each vertex—that is, the number of edges attached to each vertex.{{citation
| last1 = Chung | first1 = Fan | author1-link = Fan Chung
| last2 = Lu | first2 = Linyuan
| last3 = Vu | first3 = Van | author3-link = Van Vu
| doi = 10.1073/pnas.0937490100
| issue = 11
| journal = Proceedings of the National Academy of Sciences of the United States of America
| mr = 1982145
| pages = 6313–6318
| title = Spectra of random graphs with given expected degrees
| volume = 100
| year = 2003 | pmid=12743375 | pmc=164443| bibcode = 2003PNAS..100.6313C | doi-access = free }}. It is used together with the adjacency matrix to construct the Laplacian matrix of a graph: the Laplacian matrix is the difference of the degree matrix and the adjacency matrix.{{citation
| last = Mohar | first = Bojan | authorlink = Bojan Mohar
| editor1-last = Beineke | editor1-first = Lowell W.
| editor2-last = Wilson | editor2-first = Robin J.
| contribution = Graph Laplacians
| isbn = 0-521-80197-4
| mr = 2125091
| pages = 113–136
| publisher = Cambridge University Press, Cambridge
| series = Encyclopedia of Mathematics and its Applications
| title = Topics in algebraic graph theory
| url = https://books.google.com/books?id=z2K26gZLC1MC&pg=PA113
| volume = 102
| year = 2004}}.
Definition
Given a graph with , the degree matrix for is a diagonal matrix defined as
:
\begin{matrix}
\deg(v_i) & \mbox{if}\ i = j \\
0 & \mbox{otherwise}
\end{matrix}
\right.
where the degree of a vertex counts the number of times an edge terminates at that vertex. In an undirected graph, this means that each loop increases the degree of a vertex by two. In a directed graph, the term degree may refer either to indegree (the number of incoming edges at each vertex) or outdegree (the number of outgoing edges at each vertex).
Example
The following undirected graph has a 6x6 degree matrix with values:
| class="wikitable"
!Degree matrix |
| 175px
| 4 & 0 & 0 & 0 & 0 & 0\\ 0 & 3 & 0 & 0 & 0 & 0\\ 0 & 0 & 2 & 0 & 0 & 0\\ 0 & 0 & 0 & 3 & 0 & 0\\ 0 & 0 & 0 & 0 & 3 & 0\\ 0 & 0 & 0 & 0 & 0 & 1\\ \end{pmatrix} |
Note that in the case of undirected graphs, an edge that starts and ends in the same node increases the corresponding degree value by 2 (i.e. it is counted twice).
Properties
The degree matrix of a k-regular graph has a constant diagonal of .
According to the degree sum formula, the trace of the degree matrix is twice the number of edges of the considered graph.