Global Properties
- If each vertex of the graph has the same degree k the graph is called a k-regular graph and the graph itself is said to have degree k. Similarly, a bipartite graph in which every two vertices on the same side of the bipartition as each other have the same degree is called a biregular graph.
- An undirected, connected graph has an Eulerian path if and only if it has either 0 or 2 vertices of odd degree. If it has 0 vertices of odd degree, the Eulerian path is an Eulerian circuit.
- A directed graph is a pseudoforest if and only if every vertex has outdegree at most 1. A functional graph is a special case of a pseudoforest in which every vertex has outdegree exactly 1.
- By Brooks' theorem, any graph other than a clique or an odd cycle has chromatic number at most Δ, and by Vizing's theorem any graph has chromatic index at most Δ + 1.
- A k-degenerate graph is a graph in which each subgraph has a vertex of degree at most k.
Read more about this topic: Degree (graph Theory)
Famous quotes containing the words global and/or properties:
“As the global expansion of Indian and Chinese restaurants suggests, xenophobia is directed against foreign people, not foreign cultural imports.”
—Eric J. Hobsbawm (b. 1917)
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)