Degree (graph theory)

A graph with a loop having vertices labeled by degree

In graph theory, the degree (or valency) of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge.[1] The degree of a vertex is denoted or . The maximum degree of a graph is denoted by , and is the maximum of 's vertices' degrees. The minimum degree of a graph is denoted by , and is the minimum of 's vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0.

In a regular graph, every vertex has the same degree, and so we can speak of the degree of the graph. A complete graph (denoted , where is the number of vertices in the graph) is a special kind of regular graph where all vertices have the maximum possible degree, .

In a signed graph, the number of positive edges connected to the vertex is called positive deg and the number of connected negative edges is entitled negative deg.[2][3]

  1. ^ Diestel, Reinhard (2005). Graph Theory (3rd ed.). Berlin, New York: Springer-Verlag. pp. 5, 28. ISBN 978-3-540-26183-4.
  2. ^ Ciotti, Valerio; Bianconi, Giestra; Capocci, Andrea; Colaiori, Francesca; Panzarasa, Pietro (2015). "Degree correlations in signed social networks". Physica A: Statistical Mechanics and Its Applications. 422: 25–39. arXiv:1412.1024. Bibcode:2015PhyA..422...25C. doi:10.1016/j.physa.2014.11.062. S2CID 4995458. Archived from the original on 2021-10-02. Retrieved 2021-02-10.
  3. ^ Saberi, Majerid; Khosrowabadi, Reza; Khatibi, Ali; Misic, Bratislav; Jafari, Gholamreza (January 2021). "Topological impact of negative links on the stability of resting-state brain network". Scientific Reports. 11 (1): 2176. Bibcode:2021NatSR..11.2176S. doi:10.1038/s41598-021-81767-7. PMC 7838299. PMID 33500525.