Vertex Degree

The degree of a graph vertex  of a graph  is the number of graph edges which touch . The vertex degrees are illustrated above for a random graph. The vertex degree is also called the local degree or valency. The ordered list of vertex degrees in a given graph is called its degree sequence. A list of vertex degrees of a graph can be computed in the Wolfram Language using VertexDegree[g], and precomputed vertex degrees are available for particular embeddings of many named graphs via GraphData[graph, "VertexDegrees"].

The minimum vertex degree in a graph  is denoted , and the maximum vertex degree is denoted  (Skiena 1990, p. 157).

The graph vertex degree of a point  in a graph, denoted , satisfies

where  is the total number of graph edges.

In addition, a connected graph nodes satisfies

where the inequality can be made strict except in the case of the singleton graph . However, while this condition is necessary for a graph to be connected, it is not sufficient; an arbitrary graph satisfying the above inequality may be connected or disconnected. In fact, the criterion is not useful for connectedness testing since almost all disconnected graphs (with the exception of some disjoint unions of  and ) also satisfy the criterion.

Directed graphs have two types of degrees, known as the indegree and the outdegree.

---

REFERENCES

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength