Succession
In graph theory, the ascending order of the nodal degrees of all nodes of a graph is called the degree sequence (or also valence sequence or degree sequence ) of a simple graph.
definition
The degree result of a simple graph with nodes and node levels is the result of natural numbers
- ,
where for each indicates the degree of the node . An increasing sequence of natural numbers is called graphical if there is at least one simple graph that shows this degree sequence.
Examples
Succession
The House of Santa Claus has with node numbering in the picture alongside the node degrees and . Sorting by degree then results in the associated degree sequence .
Graphic sequences
The result is graphical, since the graph shown at the beginning has exactly these degrees. The consequence is not graphical, for example, since no simple graph with three vertices can exist that has a vertex with degree four.
use
Sequences of degrees are considered in graph theory with the Hamilton circle problem , especially in a theorem by Vašek Chvátal , which deduces statements about the existence of Hamilton circles by considering sequences of degrees.
literature
- Reinhard Diestel: graph theory . Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 pages).